-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHouseRobber.java
More file actions
127 lines (118 loc) · 4.44 KB
/
HouseRobber.java
File metadata and controls
127 lines (118 loc) · 4.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package problems;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* 打家劫舍问题
*/
public class HouseRobber {
Map<TreeNode, Integer> memo = new HashMap<>();
/**
* 打家劫舍
* 解答：
* 从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。如果抢了这间房子，那么肯定
* 就不能抢相邻的下一间房子了，只能从下下间房子开始选择。如果不抢这间房子，那么可以走到下一
* 间房子继续做选择。当走过了最后一间房子后，就没得抢了，能抢到的钱就是0（base case）。
*
* 所以我们定义当前房子的索引就是状态，抢和不抢就是选择。
*
* https://leetcode-cn.com/problems/house-robber/
*/
public int rob1(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
int[] dp = new int[n];
// 基础条件
// 1、只有一间房子时，只能抢它了
// 2、只有两间房子，因为不能抢相邻的，就选择最大的那个来抢
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(
// 抢了i - 2
dp[i - 1],
// 没有抢i - 2
dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
/**
* 打家劫舍。房子围成一圈，即第一个房屋和最后一个房屋相连
* 解答：
* 在第一题的基础上进行扩展，对于该环形问题，分以下情况：
* - 首尾房子都不抢
* - 抢第一间，不抢最后一间
* - 不抢第一间，抢最后一间
* 后两种情况一定比第一种情况大，所以只需要取后两者最大值即可。从这里我们可以将该问题分成
* 两个单排列房子的问题：
* - 抢第一间，不抢最后一间，则求nums[:n-1]的最大值
* - 不抢第一间，抢最后一间，则求nums[1:]的最大值
*
* https://leetcode-cn.com/problems/house-robber-ii/
*/
public int rob2(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];
return Math.max(
rob1(Arrays.copyOfRange(nums, 0, n - 1)),
rob1(Arrays.copyOfRange(nums, 1, n))
);
}
/**
* 打家劫舍。房子成二叉树形状
*
* https://leetcode-cn.com/problems/house-robber-iii/
*/
public int rob3(TreeNode root) {
if (root == null) return 0;
// 利用备忘录来消除子问题
if (memo.containsKey(root)) {
return memo.get(root);
}
// 抢，然后去下下家
int doRob = root.val
+ (root.left == null ? 0 : rob3(root.left.left) + rob3(root.left.right))
+ (root.right == null ? 0 : rob3(root.right.left) + rob3(root.right.right));
// 不抢，直接去下家
int notRob = rob3(root.left) + rob3(root.right);
int res = Math.max(doRob, notRob);
memo.put(root, res);
return res;
}
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 给定值序列构造一棵树
private TreeNode buildTree(Integer[] values) {
TreeNode[] nodes = new TreeNode[values.length];
for (int i = 0; i < values.length; i++) {
if (i == 0 && values[i] != null) {
nodes[0] = new TreeNode(values[i]);
} else if (values[i] != null) {
nodes[i] = new TreeNode(values[i]);
int parentIndex = (i - 1) / 2;
if ((i - 1) % 2 == 0) { // left
nodes[parentIndex].left = nodes[i];
} else { // right
nodes[parentIndex].right = nodes[i];
}
}
}
return nodes[0];
}
public static void main(String[] args) {
HouseRobber robber = new HouseRobber();
// 题目1
System.out.println(robber.rob1(new int[]{1,2,3,1})); // 4
// 题目2
System.out.println(robber.rob2(new int[]{2,3,2})); // 3
// 题目3
TreeNode root = robber.buildTree(new Integer[]{3,2,3,null,3,null,1});
System.out.println(robber.rob3(root)); // 7
}
}