文章目录
- Leetcode 198. 打家劫舍
- 解题思路
- 代码
- 总结
- Leetcode 213. 打家劫舍 II
- 解题思路
- 代码
- 总结
- Leetcode 337. 打家劫舍 III
- 解题思路
- 代码
- 总结
草稿图网站
java的Deque
Leetcode 198. 打家劫舍
题目:198. 打家劫舍
解析:代码随想录解析
解题思路
偷:上上家的最大值加上这一家
不偷:上家的最大值
代码
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
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 < dp.length; i++) {
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[dp.length-1];
}
}
//滚动数组
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0], nums[1]);
int []dp = new int[3];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[2] = Math.max(dp[0] + nums[i], dp[1]);
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
}
总结
暂无
Leetcode 213. 打家劫舍 II
题目:213. 打家劫舍 II
解析:代码随想录解析
解题思路
去头去尾两种情况取最大值
代码
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int result1 = robHouse(nums, 0, nums.length - 2);
int result2 = robHouse(nums, 1, nums.length - 1);
return Math.max(result1, result2);
}
private int robHouse(int[] nums, int begin, int end) {
if (begin == end)
return nums[begin];
else if (begin + 1 == end)
return Math.max(nums[begin], nums[begin + 1]);
int []dp = new int[3];
dp[0] = nums[begin];
dp[1] = Math.max(nums[begin], nums[begin + 1]);
for (int i = begin + 2; i <= end; i++) {
dp[2] = Math.max(dp[1], dp[0] + nums[i]);
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
}
总结
暂无
Leetcode 337. 打家劫舍 III
题目:337. 打家劫舍 III
解析:代码随想录解析
解题思路
两种情况取最大值,当前节点偷两个孩子不偷;当前节点不透两个孩子偷和不偷的最大值。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] vals = robHouse(root);
return Math.max(vals[0], vals[1]);
}
private int[] robHouse(TreeNode root) {
int[] res = new int[2];
if (root == null)
return res;
int[] left = robHouse(root.left);
int[] right = robHouse(root.right);
//0表示偷,1表示不偷
res[0] = root.val + left[1] + right[1];
res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return res;
}
}
总结
暂无