213. House Robber II
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.
题目大意：
此题是 198. House Robber 的升级版。之前已经做过。链接如下：
http://qiaopeng688.blog.51cto.com/3572484/1844956
第一版的房间形成的街道是一条直线。
第二版的房间形成的街道是成一个圆。
思路：
因为圆的首尾是相邻的，所以选首不能选尾，选尾不能选首。所以有了下面的思路。
-
求出不选尾的最大值。也就是数组中a[0]到a[N-1]求出最大值。
-
求出不选首的最大值。也就是数组中a[1]到a[N]求出最大值。
-
比较1，2的最大值，然后得到最终结果。
代码如下：
|
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
|
class
Solution {
public
:
int
rob(vector<
int
>& nums)
{
int
numLength = nums.size();
if
(nums.empty())
return
0;
if
(1 == numLength)
return
nums[0];
if
(2 == numLength)
return
nums[0] > nums[1] ? nums[0] : nums[1];
int
*maxV1 =
new
int
[nums.size() - 1];
// 0---nums.size()-2
int
*maxV2 =
new
int
[nums.size() - 1];
// 1---nums.size()-1
int
result = 0;
maxV1[0] = nums[0];
maxV1[1] = nums[0] > nums[1] ? nums[0] : nums[1];
for
(
int
i = 2; i < nums.size() - 1; ++i)
{
maxV1[i] = max(maxV1[i - 2] + nums[i], maxV1[i - 1]);
}
maxV2[0] = nums[1];
maxV2[1] = nums[1] > nums[2] ? nums[1] : nums[2];
for
(
int
i = 3; i < nums.size(); ++i)
{
maxV2[i - 1] = max(maxV2[i - 3] + nums[i], maxV2[i - 2]);
}
result = max(maxV1[nums.size() - 2], maxV2[nums.size() - 2]);
delete
maxV1;
delete
maxV2;
maxV1 = NULL;
maxV2 = NULL;
return
result;
}
};
|
总结：
代码瞬息万变，解决万千问题。哈哈哈哈。有意思。
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1844994
