欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣打家劫舍1-3 java实现

程序员文章站 2022-07-16 09:43:10
...

打家劫舍Ⅰ

力扣打家劫舍1-3 java实现
思路
动态规划实现,只需要隔着偷就好。

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;
   }
}

打家劫舍Ⅱ

力扣打家劫舍1-3 java实现
思路
Ⅱ跟Ⅰ的差别就是第一个和最后一个不能同时偷,那么可以考虑第一个偷,最后一个不偷 和 第一个不偷(最后一个无所谓偷不偷)的情况。

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]);
    }
}

打家劫舍Ⅲ

力扣打家劫舍1-3 java实现
思路
二叉树结构想办法用递归吧,这种情况无非就是要么偷四个孙子+根结点,要么偷两个左右结点,递归实现。

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;
    }
}

参考资料:打家劫舍Ⅲ题解