【算法刷题day47】Leetcode：198. 打家劫舍、213. 打家劫舍 II、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;
    }
}

总结

暂无