主流做网站程序代码,电商网站如何避免客户信息泄露,烟台网站建设的公司,网站设计公司网页设计代码随想录第四十八天 Leetcode 198. 打家劫舍ILeetcode 213. 打家劫舍 IILeetcode 337. 打家劫舍 III Leetcode 198. 打家劫舍I
题目链接: 打家劫舍I 自己的思路:想不太出来递推公式#xff01;#xff01;#xff01;#xff01;
正确思路:这个题主要是看是否偷第下标为… 代码随想录第四十八天 Leetcode 198. 打家劫舍ILeetcode 213. 打家劫舍 IILeetcode 337. 打家劫舍 III Leetcode 198. 打家劫舍I
题目链接: 打家劫舍I 自己的思路:想不太出来递推公式
正确思路:这个题主要是看是否偷第下标为i的房间直接动规五部曲1、dp数组的含义dp[i]表示从下标0到下标i包括下标i但不一定偷下标i所能偷到的最大金钱数2、递推公式分为偷下标i和不偷下标i如果偷下标i的话那么0-i的最大金钱数就是之前偷的最大金钱数也就是dp[i-2]因为没法偷下标为i-1的房间那么当不偷下标i的话那么0-i的最大金钱数就是dp[i-1]了两者中取最大值3、dp数组初始化由于当前的最大金钱和前面两个状态有关所以所有的值一定是和dp[0]和dp[1]有关dp[0]表示0-0的最大金钱所以一定选下标为0的房间dp[1]是0-1的最大金钱所以只能选一个选最大者即可4、遍历顺序由于是找包含最后一个房间的最大金钱所以一定要从前向后遍历才可以5、打印dp数组主要用于debug
代码:
class Solution {public int rob(int[] nums) {if (nums.length1) return nums[0];if (nums.length2) return Math.max(nums[0],nums[1]);int[] dp new int[nums.length];//初始化dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);for (int i 2;inums.length;i){//递推公式偷第i天和不偷第i天//从小到大遍历dp[i] Math.max(dp[i-2]nums[i],dp[i-1]);}return dp[nums.length-1];}
}Leetcode 213. 打家劫舍 II
题目链接: 打家劫舍 II 自己的思路:不好处理环的问题
正确思路:将环的问题处理成两个子问题一个是不考虑最后一间房间一个是不考虑第一间房间然后根据这两种线性情况求最大值线性情况就是打家劫舍一的情况这里我们对打家劫舍一的代码做了优化使用三个变量来代替原来的dp数组
代码:
class Solution {public int rob(int[] nums) {int len nums.length;if (len1) return nums[0];//两种情况取最大值return Math.max(robaction(Arrays.copyOfRange(nums,0,nums.length-1)),robaction(Arrays.copyOfRange(nums,1,nums.length)));}//打家劫舍一的代码简化版public int robaction(int[] nums){int x0,z0,y;for (int num:nums){y z;z Math.max(xnum,y);x y;}return z;}
}Leetcode 337. 打家劫舍 III
题目链接: 打家劫舍 III 自己的思路:好难
正确思路:树形dp没接触过完全没有思路这道题要使用后序遍历来递归二叉树因为我们要求左右子树所能偷到的最多的钱然后再求中间节点所能偷到最多的钱一次次向上递归最后返回给根节点递归三部曲1、递归参数和返回值递归参数就是当前节点返回值是一个维度为2的一维数组res这里我们选择res[0]表示偷当前节点res[1]表示不偷当前节点2、终止条件当当前节点为null时直接返回全为0的一维数组即可3、单层逻辑这里我们拿一点节点来说明当偷当前结点的房间时那么一定不能偷左右孩子的房间valnode.valleft[1]right[1]当不偷当前结点的房间时我们要分情况进行讨论因为我们不一定必须偷左右孩子的房间我们要从中选择最大值来判断所以valmax(left[0],left[1])max(right[0],right[1])然后将这两个数组成一维数组返回即可
代码:
class Solution {public int rob(TreeNode root) {//索引0表示偷 索引1表示不偷int[] res robac(root);return Math.max(res[0],res[1]);}public int[] robac(TreeNode node){if (nodenull) return new int[2];int[] left robac(node.left);int[] right robac(node.right);//偷当前结点int val1 node.val left[1]right[1];//不偷当前节点int val2 Math.max(left[0],left[1])Math.max(right[0],right[1]);return new int[]{val1,val2};}
}
