算法练习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).