长大后想做什么？做回小孩！

0%

LeetCode——打家劫舍

发表于 分类于 Valine：
本文字数： 1k

NO.198 打家劫舍 简单 、 NO.213 打家劫舍II 中等、 NO.337 打家劫舍III 中等

NO.198 打家劫舍 简单

YO5con.png

思路一：动态规划 dp[i]数组的含义：到第 i 号房子可偷窃的最高金额。

初始化：数组大小[nums.length+1]包含没有房子的情况，dp[0] = 0,dp[1]=nums[0] 即没有房子的时候最高金额 0 ，只有 1 个房子的时候，最高金额就是这个房子中的现金。

状态转移：到第 i 号房子为止偷窃最高金额 = Max(到 i-1 号的最高金额，到 i-2 号的金额 + nums[i-1])

1
2
3
4
5
6
7
8
9
10
public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length + 1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int i = 2; i < nums.length + 1; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[nums.length];
}

时间复杂度：O(n) 空间复杂度：O(n)

优化空间 只需要用两个变量 pre 和 cur ，分别记录 dp[i-1] 和 dp[i-2] 即可。

1
2
3
4
5
6
7
8
9
10
public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int pre = 0, cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int temp = cur;
        cur = Math.max(cur, pre + nums[i]);
        pre = temp;
    }
    return cur;
}

时间复杂度：O(n) 空间复杂度：O(1)

NO.213 打家劫舍II 中等

YjfHF1.png

思路一：动态规划 较上一题，本题的增加了一个房屋围成一圈的限定，翻译一下就是 1 号房子和 最后一个房子只能选择偷窃一个 ，例如输入 [2,3,2] 在上一题中，结果是 4 ，本题的结果是 3，因为首尾房子是相邻的。

回归难点本身，要求我们首尾的房子只能选择一个，那么我们将这个逻辑上环形的偷窃区间，分割成两个线性的偷窃区间：一个含头不含尾[0,n-2]、一个含尾不含头[1,n-1]。

这样问题就转换成了第一题的样子，分别计算两个偷窃区间的最大金额，选择最大的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    //分割成两个偷窃区间
    return Math.max(helper(nums, 0, nums.length - 2),
                    helper(nums, 1, nums.length - 1));
}
//动态规划
private int helper(int[] nums, int start, int end) {
    if (nums.length == 0) return 0;
    int pre = 0, cur = nums[start];
    for (int i = start + 1; i <= end; i++) {
        int temp = cur;
        cur = Math.max(cur, pre + nums[i]);
        pre = temp;
    }
    return cur;
}

时间复杂度：O(n) 空间复杂度：O(n) 需要分割成两个线性偷窃区间。

NO.337 打家劫舍III 中等

Yjht0J.png

思路一：深度优先遍历 虽然从数组变成了树，但是问题的本质并没有变化，仍然是隔一个偷窃一次。

仍然是两种情况：1. 不偷根节点，偷左右孩子，分别偷左右孩子的左右孙子。 2. 偷根节点，分别偷根节点的左右孩子的左右孙子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int rob(TreeNode root) {
    if (root == null) return 0;
    //偷根节点
    int ans = root.val;
    //再跳过根节点的左右孩子，分别去偷左右孩子的孙子节点
    if (root.left != null) {
        ans += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        ans += rob(root.right.left) + rob(root.right.right);
    }
    //Max(偷根节点的情况,不偷根节点的情况)
    return Math.max(ans, rob(root.left) + rob(root.right));
}

上述暴力方法，存在重复大量计算。

记忆化搜索 用一个 Map 保存每个节点和从该节点开始可以偷窃的最大金额的键值对。DFS 过程中先判断当前节点是否已经计算过了，搜搜完成保存当前节点和可偷窃最大值的映射到 Map 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashMap<TreeNode, Integer> map = new HashMap<>();

public int rob(TreeNode root) {
    if (root == null) return 0;
    if (map.containsKey(root)) return map.get(root);
    int ans = root.val;
    if (root.left != null) {
        ans += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        ans += rob(root.right.left) + rob(root.right.right);
    }
    ans = Math.max(ans, rob(root.left) + rob(root.right));
    map.put(root, ans);
    return ans;
}

计算节点不同状态时的最大金额 这种很像股票买卖问题，我们只需要考虑两种情况：1. 偷根节点。 2. 不偷根节点。 从两种情况中选择可偷窃金额最大的即可。

上面两个方法，比较容易逐步分析得到的，但是这个方法，如果完全没有提示的情况下，还是很难想到的。

用一个数组 ans ，ans[0] 表示偷根节点可偷最大金额， ans[1] 表示不偷根节点可偷最大金额。

递归计算左右子树，因为左右子树的根节点也存在偷和不偷两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int rob(TreeNode root) {
    //ans[0]偷根节点,ans[1]不偷根节点
    int[] ans = dp(root);
    return Math.max(ans[0],ans[1]);
}

private int[] dp(TreeNode root) {
    int[] ans = new int[2];
    if (root ==null) return ans;
    //左右子树根节点也存在偷和不偷两种情况
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    //偷根节点
    ans[0] = root.val + left[1] + right[1];
    //不偷根节点,左右子树的根节点可偷可不偷,选金额最大即可
    ans[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return ans;
}

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github