笔记:代码随想录算法练习营day39:LeetCode 198.打家劫舍,213.打家劫舍II,33 ...

学习资料:代码随想录
198.打家劫舍

力扣题目链接
思路：有点像贪婪，是一个不断比力取最大路径的思路
界说：偷到下标为i的这家，能偷到的最大值
递推公式：选当前这家偷能得到的钱和不偷当前这家的钱作比力，选能偷到的最大金额。因为这个金额是逐一递推过来的，所以是能够代表最大值的。
初始化：把第一家和第二家初始化，简朴来说，因为递推公式须要i-1和i-2
遍历次序：顺着偷
打印：

1. // 五部曲
2. // 定义:dp[i]为偷到第i家时,偷到的最高金额
3. // 递推:投当下这家和偷前一家的对比
4. // 初始化:第一家处为第一家的金额,第二家处为偷第一家和第二家中最多的那一家
5. // 遍历顺序:从一开始一家一家偷
7. class Solution {
8. public:
9.     int rob(vector<int>& nums) {
10.         vector<int> dp(nums.size(),0);
11.         if(nums.size()==1) return nums[0];
13.         dp[0] = nums[0];
14.         dp[1] = max(nums[0],nums[1]);
16.         for(int i =2;i<nums.size();i++){
17.             dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
18.             //cout<<dp[i];
19.         }      
21.         return dp[nums.size()-1];
22.     }
23. };

复制代码

213.打家劫舍II

力扣题目链接
思路：把上一题的函数打包了，然后把给定命组拆出一个不含第一个数的数组，拆出一个不含第二个数的数组，末了两个一比力

1. class Solution {
2. public:
3.     int rob(vector<int>& nums) {
4.         if(nums.size()==1) return nums[0];
5.         int result1 = toubushiqiang(nums,0,nums.size()-2);
6.         int result2 = toubushiqiang(nums,1,nums.size()-1);
7.         return max(result1,result2);
8.     }
9. private:
10.     int toubushiqiang(vector<int>& nums,int start,int end){
11.         if(end==start) return nums[start];
12.         
13.         vector<int> dp(nums.size());
15.         dp[start] = nums[start];
17.         dp[start+1] = max(nums[start],nums[start+1]);
19.         for(int i=start+2;i<=end;i++){
20.             dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
21.         }
22.         return dp[end];
23.     }
24. };

复制代码

337.打家劫舍 III

力扣题目链接
思路：
界说：不用dp数组了，按递归来，递归函数界说为该节点偷或不偷两种状态劳绩的金额
终止条件：遇空返回
遍历次序：从树的底层往上推导到根节点，后序
单层递归逻辑：还是偷与不偷该节点的比力

1. // 每个节点返回长度为2的两个数组,表示选或不选该节点所得到的金钱
2. // 终止条件:遇到空节点,返回,偷不偷空节点金额都是0
3. // 遍历顺序:后序
4. // 递推公式:递推要得到/返回两个偷或不偷的结果
5. /**
6. * Definition for a binary tree node.
7. * struct TreeNode {
8. *     int val;
9. *     TreeNode *left;
10. *     TreeNode *right;
11. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
12. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14. * };
15. */
16. class Solution {
17. private:
18.     vector<int> toubushiqiang(TreeNode* cur){   
19.         if(cur==nullptr) return vector<int>{0,0};
20.         vector<int> leftval = toubushiqiang(cur->left);
21.         vector<int> rightval = toubushiqiang(cur->right);
22.         int val1 = cur->val+leftval[0]+rightval[0];                             //选该节点1
23.         int val2 = max(leftval[0],leftval[1])+max(rightval[0],rightval[1]);     //不选该节点0
25.         return{val2,val1};
26.     }
27. public:
28.     int rob(TreeNode* root) {
29.         vector<int> result = toubushiqiang(root);
30.         return max(result[0],result[1]);
31.     }
32. };

复制代码

这题挺难

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。