213. House Robber II

  • 33.4%

https://leetcode.com/problems/house-robber-ii/#/description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.


方法一:

与house robber i 类似,但是这个可以看做两个,一个是nums[2:],一个是nums[:-1]这两个偷盗情况。这样就可以随意像一个那么偷了。

https://discuss.leetcode.com/topic/14504/9-lines-0ms-o-1-space-c-solution

9-lines 0ms O(1)-Space C++ solution

This problem is a little tricky at first glance. However, if you have finished the House Robber problem, this problem can simply be decomposed into two House Robber problems.
Suppose there are n houses, since house 0 and n - 1 are now neighbors, we cannot rob them together and thus the solution is now the maximum of

  1. Rob houses 0 to n - 2;
  2. Rob houses 1 to n - 1.

The code is as follows. Some edge cases (n < 2) are handled explicitly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n ? nums[0] : 0;
return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
}
private:
int robber(vector<int>& nums, int l, int r) {
int pre = 0, cur = 0;
for (int i = l; i <= r; i++) {
int temp = max(pre + nums[i], cur);
pre = cur;
cur = temp;
}
return cur;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
int first = helper(nums, 0, n-2);
int second = helper(nums, 1, n-1);
return max(first, second);
}

int helper(vector<int>& nums, int start, int end){
int r1 = 0, r2 = 0;
int res = 0;
for(int i=start; i<=end; i++){
res = max(r2, r1+nums[i]);
r1 = r2;
r2 = res;
}
return res;
}
};

https://discuss.leetcode.com/topic/14325/twice-pass-solution-c

Twice pass solution, C++

Twice pass:

not rob nums[n-1]

not rob nums[0]

and the other is same as House Robber.

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
int rob(vector<int>& nums)
{
if(nums.size() == 0)
return 0;
if(nums.size() == 1)
return nums[0];

int pre1 = 0, cur1 = 0;
for(int i = 0; i < nums.size() - 1; ++ i)
{
int temp = pre1;
pre1 = cur1;
cur1 = max(temp + nums[i], pre1);
}

int pre2 = 0, cur2 = 0;
for(int i = 1; i < nums.size(); ++ i)
{
int temp = pre2;
pre2 = cur2;
cur2 = max(temp + nums[i], pre2);
}

return max(cur1, cur2);
}

https://discuss.leetcode.com/topic/20770/c-super-simple-0ms-solution-with-explanation

[C++] Super Simple 0ms solution with explanation

Since you cannot rob both the first and last house, just create two separate vectors, one excluding the first house, and another excluding the last house. The best solution generated from these two vectors using the original House Robber DP algorithm is the optimal one.

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
class Solution {
public:

int robOriginal(vector<int>& nums) {
int a = 0, b = 0, res = 0;

for(int i = 0; i < nums.size(); ++i){
res = max(b + nums[i], a);
b = a;
a = res;
}

return res;
}

int rob(vector<int>& nums) {
if(nums.empty()) return 0;
if(nums.size() == 1) return nums[0];

vector<int> numsA(nums.begin() + 1, nums.end());
vector<int> numsB(nums.begin(), nums.end()-1);

return max(robOriginal(numsA), robOriginal(numsB));
}
};

https://discuss.leetcode.com/topic/18123/0ms-o-n-time-o-1-space-c-solution

0ms O(N) time O(1) space C++ solution

This solution is based on house robber 1. The idea is that either the first house or the last house is not robbed. The final solution is max of (house robber without last element) and (house robber without the first element). Note endIndex is not inclusive in the second rob function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];

return max(rob(nums, 0, nums.size()-1), rob(nums, 1, 0));
}

int rob(vector<int>& nums, int startIndex, int endIndex) {
int p = 0, q = 0;
for (int i = startIndex; i != endIndex; /* do nothing */) {
int tmp = p;
p = max(p, q + nums[i]);
q = tmp;
i = (i + 1) % nums.size();
}
return p;
}
};

https://discuss.leetcode.com/topic/28279/simple-and-easy-c-solution-modified-from-the-best-solution-of-house-robber-easy

Simple and easy C++ solution modified from the best solution of House Robber (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int rob_line(vector<int>& nums, int start, int end) {
int odd_sum=0;
int even_sum=0;

for(int i=start; i<end; i++) {
if(i%2)
odd_sum = max(even_sum, odd_sum+nums[i]);
else
even_sum = max(odd_sum, even_sum+nums[i]);
}

return max(odd_sum, even_sum);
}

int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
else if(nums.size()==1) return nums[0];
else return max(rob_line(nums,0,nums.size()-1), rob_line(nums,1,nums.size()));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Solution mine:
# 48ms, 20.23%, 74/74, April.25th, 2016
class Solution(object):
def rob_ori(self, num):
num = [0, 0] + num
for i, n in enumerate(num[2:], start = 2) : num[i] = max(num[i-2] + n, num[i-1])
return num[-1]

def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
if len(nums) == 1: return nums[0]
return max(self.rob_ori(nums[1:]), self.rob_ori(nums[:-1]))
谢谢你,可爱的朋友。