算法练习Day48|198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

LeetCode:

198. 打家劫舍 - 力扣（LeetCode）

1.思路

边界思维，只有一个元素和两个元素的初始化考虑
当元素数大于3个时，
逆向思维，是否偷最后一个元素，倒序得出递推公式dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);前者不偷，后者偷，两者取较大值。

2.代码实现

 1// 递推公式逆向思考可以得出2class Solution {3    public int rob(int[] nums) {4        int len = nums.length;5        if (len == 0) {6            return 0;7        } else if (len == 1) {8            return nums[0];9        }
10
11        int[] dp = new int[len];
12        dp[0] = nums[0];
13        dp[1] = Math.max(dp[0], nums[1]);
14
15        for (int i = 2; i < len; i++) {
16            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
17        }
18        return dp[len - 1];
19    }
20}
21// 滚动数组，有些小坑得踩一下
22class Solution {
23    public int rob(int[] nums) {
24        int len = nums.length;
25
26        if (len == 0) {
27            return 0;
28        } else if (len == 1) {
29            return nums[0];
30        } else if (len == 2) {
31            return Math.max(nums[0], nums[1]);
32        }
33
34        int[] result = new int[3];
35        result[0] = nums[0];
36        result[1] = Math.max(nums[0], nums[1]);
37
38        for (int i = 2; i < len; i++) {
39            result[2] = Math.max(result[0] + nums[i], result[1]);
40
41            result[0] = result[1];
42            result[1] = result[2];
43        }
44        return result[2];
45    }
46}

3.复杂度分析

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

LeetCode:

213. 打家劫舍 II - 力扣（LeetCode）

1.思路

考虑首元素和不考虑首元素，即可将环形进行拆解为两个线性数组，取两者之间的较大值即可

2.代码实现

 1class Solution {2    public int rob(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }67        int len = nums.length;8        if (len == 1) {9            return nums[0];
10        }
11        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
12    }
13
14    int robAction(int[] nums, int start, int end) {
15        int x = 0, y = 0, z = 0;
16        for (int i = start; i < end; i++) {
17            y = z;
18            z = Math.max(y, x + nums[i]); //
19            x = y;
20        }
21        return z;
22    }
23}

3.复杂度分析

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

LeetCode:

337. 打家劫舍 III - 力扣（LeetCode）

1.思路

分两种情况，选择根节点和不选根节点，分别计算两种情况的较大值，并选择两者之间的较大值存入map集合中，返回结果。

2.代码实现

 1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public int rob(TreeNode root) {
18        // 创建一个 Map 来保存已经计算过的节点的最大金额
19        Map<TreeNode, Integer> map = new HashMap<>(); 
20        // 调用递归方法计算能够偷取的最大金额
21        return robAction(root, map);
22    }
23    // 构建递归方法，计算以 root 为根节点的子树能够偷取的最大金额
24    int robAction(TreeNode root, Map<TreeNode, Integer> map) {
25        // 如果 root 为空，返回 0
26        if (root == null) {
27            return 0;
28        } 
29        // 如果map中已经存在以 root 为根节点的子树的最大金额，直接返回该值
30        if (map.containsKey(root)) {
31            return map.get(root);
32        }
33        // money 来保存以 root 为根节点的子树能够偷取的最大金额
34        int money = root.val;
35        // 左：判断 root 的左子节点是否存在，存在则计算左子节点的左子节点和右子节点的最大金额并加到 money 中
36        if (root.left != null) {
37            money += robAction(root.left.left, map) + robAction(root.left.right, map);
38        }
39        // 右：同理
40        if (root.right != null) {
41            money += robAction(root.right.left, map) + robAction(root.right.right, map);
42        }
43        // 结果从选择根节点和不选择根节点之中选取最大值
44        int res = Math.max(money, robAction(root.left, map) + robAction(root.right, map));
45        // 将结果res 存入map中，以便下次使用
46        map.put(root, res);
47        return res;
48    }
49}

3.复杂度分析

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