力扣打家劫舍1-3 java实现
程序员文章站
2022-07-16 09:43:10
...
打家劫舍Ⅰ
思路
动态规划实现,只需要隔着偷就好。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// 处理边界条件。
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
// 定义dp数组,按照状态转移方程递推。
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = nums[0];
//dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i <=n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1]);
}
return dp[n];
}
}
在这里可以做一个优化,方程dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1])中的dp[i-1]和dp[i-2]可以使用常量进行替代,只需要在每次赋值之后再更新常量即可。
class Solution {
public int rob(int[] nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.length; i++) {
int c = Math.max(b, a + nums[i]);
a = b;
b = c;
}
return b;
}
}
打家劫舍Ⅱ
思路
Ⅱ跟Ⅰ的差别就是第一个和最后一个不能同时偷,那么可以考虑第一个偷,最后一个不偷 和 第一个不偷(最后一个无所谓偷不偷)的情况。
class Solution {
public int rob(int[] nums) {
/*
整体思路就是把圈转化成线,把问题转化成打家劫舍1去做,分为不偷第一栋和不偷最后一栋去做
*/
int n=nums.length;
if(n==0) return 0;
if(n==1) return nums[0];
int []dp=new int[n+1];
//偷第一个不偷最后一个
dp[0]=0;
dp[1]=nums[0];
for(int i=2;i<=n;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
int end=dp[n-1];
//不偷第一个
dp[1]=0;
for(int i=2;i<=n;i++){
dp[i]= Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
return Math.max(end,dp[n]);
}
}
打家劫舍Ⅲ
思路
二叉树结构想办法用递归吧,这种情况无非就是要么偷四个孙子+根结点,要么偷两个左右结点,递归实现。
public int rob(TreeNode root) {
if (root == null) return 0;
int money = root.val;
if (root.left != null) {
money += (rob(root.left.left) + rob(root.left.right));
}
if (root.right != null) {
money += (rob(root.right.left) + rob(root.right.right));
}
return Math.max(money, rob(root.left) + rob(root.right));
}
最简单粗暴的实现了,提交结果发现效率当然不会很高,应该是可以改进的,参考了别人的思路,确实很有想法。
class Solution {
public int rob(TreeNode root) {
int []res=helper(root);
return Math.max(res[0],res[1]);
}
public int[] helper(TreeNode root){
//数组下标0存储的不抢劫当前结点可获得的最大金额,1存储的是抢劫当前结点可获得最大金额
if(root== null) return new int[2];//边界条件,r为null时,跳出
int[] left=helper(root.left);//对于以root.left为根的树,计算抢劫根节点(root.left)与不抢劫根节点可获得最大金额. left[0]则为不抢root.left可获得的最大金额,left[1]则为抢劫root.left可获得的最大金额
int[] right=helper(root.right);
int []res=new int[2];
res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
res[1]=root.val+left[0]+right[0];
return res;
}
}
参考资料:打家劫舍Ⅲ题解