网站建设维护岗位,哈尔滨房管局官网查询,黄冈黄页,国内免费建站平台代码随想录算法训练营第四十八天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III 一、198.打家劫舍
解题代码C#xff1a;
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];ve…代码随想录算法训练营第四十八天 | LeetCode198.打家劫舍、213.打家劫舍II、337.打家劫舍III 一、198.打家劫舍
解题代码C
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];vectorint dp(nums.size());dp[0] nums[0];dp[1] max(nums[0], nums[1]);for (int i 2; i nums.size(); i) {dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};
题目链接/文章讲解/视频讲解 https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html 二、213.打家劫舍II
解题代码C
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int result1 robRange(nums, 0, nums.size() - 2); // 情况二int result2 robRange(nums, 1, nums.size() - 1); // 情况三return max(result1, result2);}// 198.打家劫舍的逻辑int robRange(vectorint nums, int start, int end) {if (end start) return nums[start];vectorint dp(nums.size());dp[start] nums[start];dp[start 1] max(nums[start], nums[start 1]);for (int i start 2; i end; i) {dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[end];}
};题目链接/文章讲解/视频讲解 https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html 三、337.打家劫舍III
解题代码C
class Solution {
public:int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}// 长度为2的数组0不偷1偷vectorint robTree(TreeNode* cur) {if (cur NULL) return vectorint{0, 0};vectorint left robTree(cur-left);vectorint right robTree(cur-right);// 偷cur那么就不能偷左右节点。int val1 cur-val left[0] right[0];// 不偷cur那么可以偷也可以不偷左右节点则取较大的情况int val2 max(left[0], left[1]) max(right[0], right[1]);return {val2, val1};}
};
题目链接/文章讲解/视频讲解 https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
