leetcode|leetcode_House Robber II leetcode|leetcode题解

描述：

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.
思路：
1.和House Robber的思路类似，只是本题中房子是首尾相连的，也就是说第一个房子和最后一个房子不能都被盗，否则，触发警报，小偷被抓
2.在House Robber的基础上，a:如果从第一座房子开始偷窃，那么最后一个房子肯定不能被偷；b:如果从第二座房子偷窃，那么最后一个房子可以被偷，分别对这两种情况进行计算即可。
代码：

public int rob(int[] nums) { if(nums==null) return 0; int len=nums.length; int maxProfit=0; if(len==0) return 0; else if(len==1) return nums[0]; else if(len==2) return Math.max(nums[0],nums[1]); else { int tempMaxProfit1=getMaxProfit(nums, 0, nums.length-2); int tempMaxProfit2=getMaxProfit(nums, 1, nums.length-1); maxProfit=Math.max(tempMaxProfit1, tempMaxProfit2); } return maxProfit; } public int getMaxProfit(int nums[],int start,int end) { int maxProfit1=nums[start]; //用maxProfit1、maxProfit2来避免用数组来存储临时变量 int maxProfit2=Math.max(nums[start],nums[start+1]); int maxProfit=Math.max(maxProfit1, maxProfit2); for(int i=start+2; i<=end; i++) { maxProfit=Math.max(maxProfit2,maxProfit1+nums[i]); maxProfit1=maxProfit2; maxProfit2=maxProfit; } return maxProfit; }

【leetcode|leetcode_House Robber II】