建站模板大全,辽宁建设工程信息网ca锁激活,宁波seo优化,乐清网站建设哪家好代码随想录训练营第48天|198.打家劫舍#xff0c;213.打家劫舍II#xff0c;337.打家劫舍III 198.打家劫舍文章思路代码 213.打家劫舍III文章思路代码 337.打家劫舍III文章思路代码 总结 198.打家劫舍
文章
代码随想录|0198.打家劫舍
思路 d p [ i ] M a x ( d p [ i − … 代码随想录训练营第48天|198.打家劫舍213.打家劫舍II337.打家劫舍III 198.打家劫舍文章思路代码 213.打家劫舍III文章思路代码 337.打家劫舍III文章思路代码 总结 198.打家劫舍
文章
代码随想录|0198.打家劫舍
思路 d p [ i ] M a x ( d p [ i − 1 ] , d p [ i − 2 ] n u m s [ i ] ) dp[i]Max(dp[i-1],dp[i-2]nums[i]) dp[i]Max(dp[i−1],dp[i−2]nums[i])
代码
class Solution {public int rob(int[] nums) {int i, n;n nums.length;int[] dp new int[n];dp[0] nums[0];if (n 2) {return dp[0];}dp[1] nums[1] nums[0] ? nums[1] : nums[0];for (i 2; i n; i) {dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]);}return dp[n - 1];}
}213.打家劫舍III
文章
213.打家劫舍II
思路
在[0, n-1]范围内dp一次在[1, n]范围内dp一次取二者最大值
代码
class Solution {public int rob(int[] nums) {int i, n;n nums.length;if (n 1) {return nums[0];}if (n 2) {return nums[1] nums[0] ? nums[1] : nums[0];}int[] dp0 new int[n - 1];dp0[0] nums[0];dp0[1] nums[1] nums[0] ? nums[1] : nums[0];int[] dp1 new int[n - 1];dp1[0] nums[1];dp1[1] nums[2] nums[1] ? nums[2] : nums[1];for (i 2; i n - 1; i) {dp0[i] Math.max(dp0[i - 1], dp0[i - 2] nums[i]);dp1[i] Math.max(dp1[i - 1], dp1[i - 2] nums[i 1]);}return Math.max(dp0[n - 2], dp1[n - 2]);}
}337.打家劫舍III
文章
代码随想录|0337.打家劫舍III
思路
劫不劫某个节点取决于其两个子节点有没有被劫所以是后续遍历递归每一层返回是否劫那个节点的两种情况
代码
class Solution {public int rob(TreeNode root) {TreeNode dummy new TreeNode(0);dummy.right root;return dfs(dummy)[0];}public int[] dfs(TreeNode node) {if (node null) {return new int[] {0, 0};}int[] leftVal dfs(node.left);int[] rightVal dfs(node.right);int[] res new int[2];res[0] Math.max(leftVal[0], leftVal[1]) Math.max(rightVal[0], rightVal[1]);res[1] leftVal[0] rightVal[0] node.val;return res;}
}总结
这三道题都是二刷了思路明确 但是上上周笔试人家出的题目是打家劫舍IV。。。。我并没有做出来等下去研究研究再说
