当前位置: 首页 > news >正文

【代码随想录】day48

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 一、198打家劫舍
  • 二、213打家劫舍II
  • 三、337打家劫舍III


一、198打家劫舍

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size() + 2, 0);for (int i = 0; i < nums.size(); i ++) {dp[i+2] = max(dp[i+1], dp[i] + nums[i]);}return dp[nums.size()+1];}
};

二、213打家劫舍II

class Solution {
public:int helper(vector<int>& nums, int start, int end) {vector<int> dp(2, 0);for (int i = start; i < end; i ++) {dp.push_back(max(dp.back(), dp[dp.size()-2] + nums[i]));}return dp.back();}int rob(vector<int>& nums) {if (nums.size() == 1) {return nums.back();}int res1 = helper(nums, 0, nums.size() - 1);int res2 = helper(nums, 1, nums.size());return max(res1, res2);}
};

三、337打家劫舍III

class Solution {
public:unordered_map<TreeNode*, int> umap;int rob(TreeNode* root) {if (root == nullptr) {return 0;}if (root->left == nullptr && root->right == nullptr) {return root->val;}if (umap[root]) {return umap[root];}int val1 = root->val;if (root->left) {val1 += rob(root->left->left) + rob(root->left->right);}if (root->right) {val1 += rob(root->right->left) + rob(root->right->right);}int val2 = rob(root->left) + rob(root->right);umap[root] = max(val1, val2);return max(val1, val2);        }
};

优化版:

class Solution {
public:vector<int> robTree(TreeNode* cur) {if (cur == nullptr) {return vector<int>(2, 0);}vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);//偷当前节点,左右孩子不能偷int val1 = cur->val + left[1] + right[1];//不偷当前节点,左右孩子可以偷int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val1, val2};}int rob(TreeNode* root) {vector<int> dp = robTree(root);return max(dp[0], dp[1]);}
};
http://www.lryc.cn/news/344297.html

相关文章:

  • 【补充】1-auth的使用、扩写auth的user表、django支持缓存
  • 力扣-21. 合并两个有序链表-js实现
  • tensorflow报错
  • 企业数字化转型走向平台化运营会经历哪些阶段?
  • 最新AI实景自动无人直播软件教你实现24小时不下播带货;智能化引领直播新时代
  • 《二十一》QT QML编程基础
  • 免费的发票查验接口平台 PHP开发示例
  • 10、算数运算符(以 ‘/’、‘%’、‘++’为主去讲解)(Java超详细版本)
  • 向量数据库:PGVector
  • redux实现原理
  • 【go项目01_学习记录04】
  • HCIP第二节
  • Ubuntu MATE系统下WPS显示错位
  • Mysql进阶-索引篇
  • 【算法系列】哈希表
  • Git推送本地项目到gitee远程仓库
  • 一键复制:基于vue实现的tab切换效果
  • 新手做抖音小店,卖什么最容易出单?抖音必爆类目来了!
  • 男人圣经 10
  • 如何让路由器分配固定网段(网络号)ip
  • Q1保健品线上市场分析(三):牛初乳市场扩张,同比去年增长54%
  • 使用docker-compose编排Lnmp(dockerfile) 完成Wordpress
  • 母婴店运用商城小程序店铺的效果是什么
  • 大数据技术概述_2.大数据面临的5个方面的挑战
  • 《动手学深度学习(Pytorch版)》Task03:线性神经网络——4.29打卡
  • 机器学习(二) ----------K近邻算法(KNN)+特征预处理+交叉验证网格搜索
  • This error originates from a subprocess, and is likely not a problem with pip.
  • Python中关于子类约束的开发规范
  • Isaac Sim 4 键盘控制小车前进方向(学习笔记5.8.2)
  • ​「Python绘图」绘制太极图