代码随想录算法训练营第三十九天|LeetCode 198 打家劫舍、LeetCode 213 打家劫舍 ||、LeetCode 337 打家劫舍 |||

参考文章均来自代码随想录LeetCode 198 打家劫舍参考文章链接你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。示例 1 输入[1,2,3,1] 输出4 解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。 偷窃到的最高金额 1 3 4 。 示例 2 输入[2,7,9,3,1] 输出12 解释偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。 偷窃到的最高金额 2 9 1 12 。dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。决定dp[i]的因素就是第i房间偷还是不偷。如果偷第i房间那么dp[i] dp[i - 2] nums[i] 即第i-1房一定是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间那么dp[i] dp[i - 1]即考 虑i-1房注意这里是考虑并不是一定要偷i-1然后dp[i]取最大值即dp[i] max(dp[i - 2] nums[i], dp[i - 1]);dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1]);dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的那么一定是从前到后遍历classSolution{public:introb(vectorintnums){if(nums.size()0)return0;if(nums.size()1)returnnums[0];vectorintdp(nums.size()1,0);dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(inti2;inums.size();i){dp[i]max(dp[i-2]nums[i],dp[i-1]);}returndp[nums.asize()-1];}};时间复杂度: O(n)空间复杂度: O(n)LeetCode 213 打家劫舍 ||参考文章链接你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。示例 1 输入nums [2,3,2] 输出3 解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。 示例 2 输入nums [1,2,3,1] 输出4 解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。 偷窃到的最高金额 1 3 4 。 示例 3 输入nums [1,2,3] 输出3成环后有三种情况情况一是首尾都不考虑情况二是只考虑首情况三是只考虑尾而情况二和情况三包含情况一情况三虽然是考虑包含尾元素但不一定要选尾部元素所以求情况二和情况三后取最大值即可 每个情况都是打家劫舍的流程classSolution{public:introbRange(vectorintnums,intstart,intend){if(endstart)returnnums[start];vectorintdp(nums.size());dp[start]nums[start];dp[start1]max(nums[start],nums[start1]);for(intistart2;iend;i){dp[i]max(dp[i-2]nums[i],dp[i-1]);}returndp[end];}introb(vectorintnums){if(nums.size()0)return0;if(nums.size()1)returnnums[0];intresult1robRange(nums,0,nums.size()-2);// 情况二intresult2robRange(nums,1,nums.size()-1);// 情况三returnmax(result1,result2);}};时间复杂度: O(n)空间复杂度: O(n)LeetCode 337 打家劫舍 |||参考文章链接力扣题目链接本题属于树形dp 之前没做过 详看参考文章 讲的很清楚后面再多做一做理解一下/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */classSolution{public:introb(TreeNode*root){vectorintresultrobTree(root);returnmax(result[0],result[1]);}// 长度为2的数组0不偷1偷vectorintrobTree(TreeNode*cur){if(curNULL)returnvectorint{0,0};vectorintleftrobTree(cur-left);vectorintrightrobTree(cur-right);// 偷cur那么就不能偷左右节点。intval1cur-valleft[0]right[0];// 不偷cur那么可以偷也可以不偷左右节点则取较大的情况intval2max(left[0],left[1])max(right[0],right[1]);return{val2,val1};}};时间复杂度O(n)每个节点只遍历了一次空间复杂度O(log n)算上递推系统栈的空间