Skip to content

Commit 43bda27

Browse files
awangdevawangdev
committed
house rob problem
1 parent f0a58b6 commit 43bda27

File tree

6 files changed

+690
-436
lines changed

6 files changed

+690
-436
lines changed

‎Java/House Robber II.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
M
2+
3+
和House Robber I 类似, DP.
4+
5+
根据dp[i-1]是否被rob来讨论dp[i]: dp[i] = Math.max(dp[i-1], dp[i - 2] + nums[i - 1]);
6+
7+
特别的是，末尾的last house 和 first house相连。这里就需要分别讨论两种情况:
8+
1. 最后一个房子被rob
9+
2. 最后一个房子没被rob
10+
11+
两种情况做完，综合对比一下.
12+
13+
```
14+
/*
15+
Note: This is an extension of House Robber.
16+
17+
After robbing those houses on that street, the thief has found himself a new place for his thievery
18+
so that he will not get too much attention. This time, all houses at this place are arranged in a circle.
19+
That means the first house is the neighbor of the last one.
20+
Meanwhile, the security system for these houses remain the same as for those in the previous street.
21+
22+
Given a list of non-negative integers representing the amount of money of each house,
23+
determine the maximum amount of money you can rob tonight without alerting the police.
24+
25+
Credits:
26+
Special thanks to @Freezen for adding this problem and creating all test cases.
27+
28+
Subscribe to see which companies asked this question
29+
30+
31+
Dynamic Programming
32+
Hide Similar Problems (E) House Robber (M) Paint House (E) Paint Fence (M) House Robber III
33+
34+
35+
36+
*/
37+
38+
/*
39+
Each house depends on front and back houses
40+
Two possible case for the last house: rob or not robbed. So we can do two for loop, then compare the
41+
two differnet future.
42+
*/
43+
public class Solution {
44+
public int rob(int[] nums) {
45+
if (nums == null || nums.length == 0) {
46+
return 0;
47+
} else if (nums.length == 1) {
48+
return nums[0];
49+
} else if (nums.length == 2) {
50+
return Math.max(nums[0], nums[1]);
51+
}
52+
53+
int n = nums.length;
54+
55+
//Last house not robbed
56+
int[] dp1 = new int[n];
57+
dp1[0] = nums[0];
58+
dp1[1] = Math.max(nums[0], nums[1]);
59+
for (int i = 2; i < n - 1; i++) {
60+
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
61+
}
62+
dp1[n - 1] = dp1[n - 2];
63+
64+
//Last house robbed
65+
int[] dp2 = new int[n];
66+
dp2[0] = 0;
67+
dp2[1] = nums[1];
68+
for (int i = 2; i < n - 2; i++) {
69+
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
70+
}
71+
dp2[n - 1] = dp2[n - 3] + nums[n - 1];
72+
73+
//Compare
74+
return Math.max(dp2[n - 1], dp1[n - 1]);
75+
}
76+
}
77+
78+
79+
80+
81+
82+
```

‎Java/House Robber III.java

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
H
2+
3+
由于无法用简单的方法构造DP array, 所以采取了普通的DFS。
4+
5+
The catch:
6+
判断当下的node是否被采用，用一个boolean来表示.
7+
8+
1. 如果curr node被采用，那么下面的child一定不能被采用。
9+
2. 如果curr node不被采用，那么下面的children有可能被采用，但也可能略过，所以这里用Math.max() 比较一下两种可能有的dfs结果。
10+
11+
12+
```
13+
/*
14+
The thief has found himself a new place for his thievery again.
15+
There is only one entrance to this area, called the "root."
16+
Besides the root, each house has one and only one parent house.
17+
After a tour, the smart thief realized that "all houses in this place forms a binary tree".
18+
It will automatically contact the police if two directly-linked houses were broken into on the same night.
19+
20+
Determine the maximum amount of money the thief can rob tonight without alerting the police.
21+
22+
Example 1:
23+
3
24+
/ \
25+
2 3
26+
\ \
27+
3 1
28+
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
29+
30+
Example 2:
31+
3
32+
/ \
33+
4 5
34+
/ \ \
35+
1 3 1
36+
Maximum amount of money the thief can rob = 4 + 5 = 9.
37+
Credits:
38+
Special thanks to @dietpepsi for adding this problem and creating all test cases.
39+
40+
Subscribe to see which companies asked this question
41+
42+
43+
Tree Depth-first Search
44+
Hide Similar Problems (E) House Robber (M) House Robber II
45+
46+
47+
*/
48+
49+
/**
50+
* Definition for a binary tree node.
51+
* public class TreeNode {
52+
* int val;
53+
* TreeNode left;
54+
* TreeNode right;
55+
* TreeNode(int x) { val = x; }
56+
* }
57+
*/
58+
59+
/*
60+
3.24.2016
61+
Thought: dfs should be able to handle this.
62+
*/
63+
public class Solution {
64+
public int rob(TreeNode root) {
65+
if (root == null) {
66+
return 0;
67+
} else if (root.left == null && root.right == null) {
68+
return root.val;
69+
}
70+
return Math.max(dfs(root,true), dfs(root, false));
71+
}
72+
73+
public int dfs (TreeNode node, boolean visit) {
74+
if (node.left == null && node.right == null) {
75+
if (visit){
76+
return node.val;
77+
} else {
78+
return 0;
79+
}
80+
}
81+
int left = 0;
82+
int right = 0;
83+
if (visit) {
84+
if (node.left != null) {
85+
left = dfs(node.left, !visit);
86+
}
87+
if (node.right != null) {
88+
right = dfs(node.right, !visit);
89+
}
90+
return node.val + left + right;
91+
} else {
92+
if (node.left != null) {
93+
left = Math.max(dfs(node.left, !visit), dfs(node.left, visit));
94+
}
95+
if (node.right != null) {
96+
right = Math.max(dfs(node.right, !visit), dfs(node.right, visit));
97+
}
98+
return left + right;
99+
}
100+
101+
}
102+
}
103+
104+
105+
```

‎Java/House Robber.java

Lines changed: 45 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
1-
最基本的dp。
2-
看前一个或前两个的情况，再总和考虑当下的。
3-
思考的适合搞清楚当下的和之前的情况的关系。
4-
滚动数组的优化，就是确定了是这类“只和前一两个位子“相关的Fn而推出的。
1+
E
2+
3+
最基本的dp。
4+
看前一个或前两个的情况，再总和考虑当下的。
5+
思考的适合搞清楚当下的和之前的情况的关系。
6+
滚动数组的优化，就是确定了是这类“只和前一两个位子“相关的Fn而推出的。
7+
58
```
69
/*
710
You are a professional robber planning to rob houses along a street.
@@ -13,7 +16,7 @@
1316
Given a list of non-negative integers representing the amount of money of each house,
1417
determine the maximum amount of money you can rob tonight without alerting the police.
1518
16-
Have you met this question in a real interview? Yes
19+
1720
Example
1821
Given [3, 8, 4], return 8.
1922
@@ -24,12 +27,48 @@
2427
Dynamic Programming
2528
2629
*/
30+
31+
32+
33+
/*
34+
3.24.2016 recap
35+
Find max, either add nums[i - 1] or not. Use dp[i] to track the max money take from [0 ~ i]
36+
*/
37+
public class Solution {
38+
public int rob(int[] nums) {
39+
if (nums == null || nums.length == 0) {
40+
return 0;
41+
} else if (nums.length == 1) {
42+
return nums[0];
43+
}
44+
int[] dp = new int[nums.length];
45+
dp[0] = nums[0];
46+
dp[1] = Math.max(nums[0], nums[1]);
47+
48+
for (int i = 2; i < dp.length; i++) {
49+
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
50+
}
51+
52+
return dp[dp.length - 1];
53+
}
54+
}
55+
56+
/*
57+
Should be able to do with recursive way.
58+
dfs(nums, index, robFlag, sum)
59+
Based on robFlag (true/false), this recursive level will be limited weather we can pick the current
60+
house or no. Update robFlag, sum, index and go into next level of dfs.
61+
*/
62+
63+
64+
65+
2766
/*
2867
Thoughts:
2968
dp[i]: the best we can rob by i.
3069
If I'm at house i, I'll either pick i or not pick i.
3170
Pick i: dp[i-2] + A[i]
32-
Not pick i: dp[i+1]
71+
Not pick i: dp[i-1]
3372
fn:
3473
dp[i] = Math.max(dp[i-1], dp[i-2] + A[i])
3574
Init:
@@ -96,9 +135,4 @@ public long houseRobber(int[] A) {
96135

97136

98137

99-
100-
101-
102-
103-
104138
```

0 commit comments

Comments
 (0)