213. House Robber II


Note:This is an extension ofHouse 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 arearranged 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 tonightwithout alerting the police.

题目大意：

此题是198. House Robber 的升级版。之前已经做过。链接如下：

http://qiaopeng688.blog.51cto.com/3572484/1844956

第一版的房间形成的街道是一条直线。

第二版的房间形成的街道是成一个圆。


思路：

因为圆的首尾是相邻的，所以选首不能选尾，选尾不能选首。所以有了下面的思路。

求出不选尾的最大值。也就是数组中a[0]到a[N-1]求出最大值。

求出不选首的最大值。也就是数组中a[1]到a[N]求出最大值。

比较1，2的最大值，然后得到最终结果。


代码如下：

classSolution{public:introb(vector<int>&nums){intnumLength=nums.size();if(nums.empty())return0;if(1==numLength)returnnums[0];if(2==numLength)returnnums[0]>nums[1]?nums[0]:nums[1];int*maxV1=newint[nums.size()-1];//0---nums.size()-2int*maxV2=newint[nums.size()-1];//1---nums.size()-1intresult=0;maxV1[0]=nums[0];maxV1[1]=nums[0]>nums[1]?nums[0]:nums[1];for(inti=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(inti=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]);deletemaxV1;deletemaxV2;maxV1=NULL;maxV2=NULL;returnresult;}};

总结：

代码瞬息万变，解决万千问题。哈哈哈哈。有意思。

2016-08-31 23:41:18