网站关键字选择标准,上海官网建设费用,怎样建设营销型网站,湖南旅游攻略代码随想录算法训练营第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
打家劫舍
198.打家劫舍
文章讲解#xff1a;https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
题目链接#xff1a;https://leetcode.cn/problems/house-robber…代码随想录算法训练营第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
打家劫舍
198.打家劫舍
文章讲解https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
题目链接https://leetcode.cn/problems/house-robber/
视频讲解https://www.bilibili.com/video/BV1Te411N7SX/自己看到题目的第一想法
套动态规划五步骤去做但是没想到切入点卡在递推公式的推导以及dp的定义上。不知道该如何确定i的概念。
看完代码随想录之后的想法
动态规划去处理该题i是输入元素的下标然后递推公式按照i这个索引的元素放不放去推导出来具体实现
定义dp数组概念dp[i]为从0-i个元素中选取多个元素使这些元素的和最大同时要满足题目不能选相邻元素的规则。确定递推公式递推公式的确定可以从选i和不选i来推导 选idp[i]dp[i-2] nums[i]。这里用dp[i-2]是因为选了i之后就不能选i-1了。不选i:dp[i] dp[i-1]。这里dp[i-1]不一定会选i-1要多去回顾dp[i]的概念这里是指从0到i-1中选取多个元素使这些元素的和最大。根据选i和不选i最终可以得到推导公式 dp[i] Math.max(dp[i-2] nums[i],dp[i-1]); 确定初始化值dp[0] nums[0]。dp[1] Math.max(nums[0],nums[1]);其他元素的值因为是从小到大推的后面的值由前面推导而来因此可以直接初始化为0。确定遍历顺序因为递推公式是从小到大所以遍历顺序也从小到大。打印值
自己实现过程中遇到哪些困难
遍历的时候i的取值没确定下来是inums.length还是inums.length。 这里思考了一下因为最终求得后的dp数组要返回的值应该是nums的最后一个元素的位置因此应该返回dp[nums.length - 1]。并且在遍历过程中p[i] Math.max(dp[i-2] nums[i],dp[i-1])nums[i]也只能到达inums.length - 1因此这里的循环处理逻辑为inums.length。最终代码 public int rob(int[] nums) {if(nums.length 1){return nums[0];}int[] dp new int[nums.length];dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);for(int i 2; i nums.length; i){dp[i] Math.max(dp[i-1],dp[i-2] nums[i]);}return dp[nums.length - 1];}这道题的核心就是dp[i]的概念和递推公式的确定。
打家劫舍II
213.打家劫舍II
文章讲解https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
题目链接https://leetcode.cn/problems/house-robber-ii/
视频讲解https://www.bilibili.com/video/BV1oM411B7xq/自己看到题目的第一想法
整体思路和打家劫舍第一步一样区别就是如果是环形的话 那0位置的元素和最后位置的元素不能共存。 这里分2钟场景一去掉头二去掉尾然后看一或者二求出来哪个更大。
看完代码随想录之后的想法
整体方法一样这里和自己的想法有区别的是自己的想法是做2个nums数组做截取得到[0,length - 1]和[1,length]而代码随想录里是用2个循环去处理。
自己实现过程中遇到哪些困难
初始化值的赋值方式和遍历循环i的初始值和结尾值没确定。 最终代码
public int rob(int[] nums,int start,int end){if (end start) return nums[start];int[] dp new int[nums.length];dp[start] nums[start];dp[start 1] Math.max(nums[start],nums[start 1]);for(int i start 2; i end; i){dp[i] Math.max(dp[i-2] nums[i],dp[i - 1]);}return dp[end];
}打家劫舍III
337.打家劫舍III
文章讲解https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
题目链接https://leetcode.cn/problems/house-robber-iii/
视频讲解https://www.bilibili.com/video/BV1H24y1Q7sY/自己看到题目的第一想法
二叉树一样只是把循环改成树的遍历了根节点不能打劫左右子节点。 树的遍历有前中后。中为处理计算前后为递归。
看完代码随想录之后的想法
代码分成2种情况偷父节点和不偷父节点。
暴力递归 偷父节点则直接取父节点的值不偷父节点取2个字节点的值的和。最终再使用Math.max把两种情况下的值做一个比较取大值。
动态规划 使用一个长度为2的数组0记录不选根节点的最大值1记录选根节点的最大值。 树形dp先搭后序遍历的框架二叉树的递归需要回归下。 然后再在二叉树递归中增加动态规划逻辑。
public int rob(TreeNode root) {// 二叉树一样只是把循环改成树的遍历了根节点不能打劫左右子节点int[] result backtracking(root);return Math.max(result[0],result[1]);
}
public int[] backtracking(TreeNode node){int[] dp new int[2];// 递归三部曲// 终止条件if(node null){return dp;}// 后序遍历int[] left backtracking(node.left);int[] right backtracking(node.right);// 选当前节点和不选当前节点// 选当前节点dp[0] node.val left[1] right[1];// 不选当前节点dp[1] Math.max(left[0],left[1]) Math.max(right[0],right[1]);return dp;
}今日收获学习时长
这节课整体用的时间不多大概1.5h。 今天回顾了一下树的遍历整体还是做递归遍历结合前、中、后序遍历去做逻辑。 学习了打家劫舍的解题方法整体处理的逻辑还是讨论当前节点抢还是不抢。如果抢了当前节点两个孩子就不能动如果没抢当前节点就可以考虑抢左右孩子注意这里说的是“考虑”
