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

1打家劫舍三部曲

 刷题刷题找工作!

s198.打家劫舍

动态规划:开始打家劫舍!

dp数组表示到第i家的最高金额

dp递归公式,要么抢劫这家,加上i-2所抢的钱,要么不抢,保留上一家的。                                                                                                    

class Solution {public int rob(int[] nums) {//一切的问题都是是否装入int len = nums.length;int[] dp = new int[len+1];dp[0] = 0;dp[1] = nums[0];for(int i=2; i <= len; i++){dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);}return dp[len];}
}

这个题呢,就是要注意考虑细节 ,关于为0,为1,以及初始化的时候是怎么样的,不要以为做出推导公式就万事大吉了。

213.打家劫舍II

. - 力扣(LeetCode)

两次dp,只不过注意范围

class Solution {public int rob(int[] nums) {//如何把证第一间房屋和最后一间房屋不同时偷窃呢。//如果偷窃了第一间,则不能偷窃最后一间,所以范围会变//如果偷最后一间,不能偷第一间//做两次dp不就行了?int len = nums.length;if(len == 1){//不能省,后面有now = nums[i]的赋值return nums[0];}int nums1 = ro(nums, 0, len-1);int nums2 = ro(nums, 1, len-1);return Math.max(nums1, nums2);}public int ro(int[] nums, int i, int len){int now = nums[i];int pre1 = 0, pre2 = 0;while(len-- > 0){now = Math.max(pre1, pre2 + nums[i]);pre2 = pre1;pre1 = now;i++;}return now;}
}


 337.打家劫舍III

动态规划:继续打家劫舍!

自己的思路

很好理解,看注释。

但是递归的魅力,超时了。

class Solution {public int rob(TreeNode root) {//如果父亲节点被访问过,直接往左右节点的节点走//如果父亲节点未被访问,比较访问子节点,和不访问子节点的,取最大值//访问下一个节点, 1表示当前节点可以访问return Math.max(dfs(root.left, 1) + dfs(root.right, 1), dfs(root.left, 0) + dfs(root.right, 0) + root.val);}public int dfs(TreeNode root, int flag){//父节点是否访问了if(root == null){return 0;}if(root.left == null && root.right == null ){if(flag == 1){return root.val;}return 0;}if(flag == 0){//不可访问当前节点,只能访问子节点return dfs(root.left, 1) + dfs(root.right, 1);}//访问子节点/访问当前节点int num = Math.max(dfs(root.left, 1) + dfs(root.right, 1), dfs(root.left, 0) + dfs(root.right, 0) + root.val);return num;}
}

题解

优化了一下,通过返回数组,一次遍历就找出访问子节点的最大值和不访问子节点的最大值。

class Solution {public int rob(TreeNode root) {//如果父亲节点被访问过,直接往左右节点的节点走//如果父亲节点未被访问,比较访问子节点,和不访问子节点的,取最大值int[] ans = dfs(root);return Math.max(ans[0], ans[1]);}public int[] dfs(TreeNode root){if(root == null){return new int[]{0, 0};//包括根点的最值,不包括跟节点的最值}int[] left = dfs(root.left);int[] right = dfs(root.right);//这样只遍历一次把最大最小值都放进去了int v1 = left[0] + right[0];//放子节点int v2 = left[1] + right[1] + root.val;v2 = Math.max(v2, v1);//为什么要加这个,因为放根节点的最大值是可以放或者不可以放的,而放子节点是一定不能放当前节点的return new int[]{v2, v1};}
}


http://www.mrgr.cn/news/45789.html

相关文章:

  • Java中Collections类详解
  • Git管理远程仓库
  • 【动态规划-最长公共子序列(LCS)】【hard】力扣1092. 最短公共超序列
  • rust gio-rs 挂载 samba 磁盘
  • 【Java 并发编程】多线程安全问题(上)
  • 算法:724.寻找数组的中心下标
  • 面试(十)
  • 【JVM】内存分析工具JConsole/Visual VM
  • 每日OJ题_牛客_平方数_数学_C++_Java
  • 面试题:Redis(一)
  • 回到原点再出发
  • 职场上的人情世故,你知多少?这五点一定要了解
  • Python获取json返回的字符串获取方法大全
  • 若依初相识
  • 每天一道面试题5——Linux内核包含哪些部分?
  • 【C语言刷力扣】1678.设计Goal解析器
  • Python酷库之旅-第三方库Pandas(137)
  • 解决方案:Pandas里面的loc跟iloc,有什么区别
  • 形式逻辑 | 管理类联考
  • 初入网络学习第一篇