wordpress建外贸网站,北京个人网站备案,网站图片宽度,长沙做网站价格力扣labuladong一刷day11拿下打家劫舍问题共3题 文章目录 力扣labuladong一刷day11拿下打家劫舍问题共3题一、198. 打家劫舍二、213. 打家劫舍 II三、337. 打家劫舍 III 一、198. 打家劫舍
题目链接#xff1a;https://leetcode.cn/problems/house-robber/ 思路#xff1a;打…力扣labuladong一刷day11拿下打家劫舍问题共3题 文章目录 力扣labuladong一刷day11拿下打家劫舍问题共3题一、198. 打家劫舍二、213. 打家劫舍 II三、337. 打家劫舍 III 一、198. 打家劫舍
题目链接https://leetcode.cn/problems/house-robber/ 思路打劫必须隔1家定义dp[i]表示截止到第i家所能抢到的最大值。 递推公式 dp[i] max(dp[i-1], dp[i-2]nums[i]); 如果当前这家不偷最大值就是dp[i-1]如果偷就是要隔一家dp[i-2]nums[i]
class Solution {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];}
}由于只用到了前一天和前两天所以还可以优化一下空间。
public int rob(int[] nums) {if (nums.length 1) return nums[0];int a nums[0], b Math.max(nums[0], nums[1]);for (int i 2; i nums.length; i) {int c Math.max(b, anums[i]);a b;b c;}return b;}二、213. 打家劫舍 II
题目链接https://leetcode.cn/problems/house-robber-ii/ 思路直接划分为两个区间然后分别计算再比较。即nums[0, len-2] 和 nums[1, len-1]
class Solution {public int rob(int[] nums) {if (nums.length 1) return nums[0];if (nums.length 2) return Math.max(nums[0], nums[1]);int max 0, a nums[0], b Math.max(nums[0], nums[1]);for (int i 2; i nums.length - 1; i) {int c Math.max(b, anums[i]);a b;b c;}max b;a nums[1];b Math.max(nums[1], nums[2]);for (int i 3; i nums.length; i) {int c Math.max(b, anums[i]);a b;b c;}return max b ? max : b;}
}三、337. 打家劫舍 III
题目链接https://leetcode.cn/problems/house-robber-iii/ 思路定义nums[2] 记录每个节点偷与不偷的状态。
class Solution {public int rob(TreeNode root) {int[] ints f1(root);return Math.max(ints[0], ints[1]);}int[] f1(TreeNode root) {int[] nums new int[2];if (root null) {return nums;}int[] left f1(root.left);int[] right f1(root.right);nums[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);nums[1] root.val left[0] right[0];return nums;}
}
