星空网 > 软件开发 > Java

[LeetCode] House Robber II

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围成了一个圈。之前我们只需要考虑这个house的前一个是否被rob与否。现在呢就有了特殊情况。

     第一个和最后一个house不能同时被rob。

     最为简单的方法就是call两次第一次的算法。(一个assume第一个house被rob,一个则assume最后一个house被rob。)

     因为这里有nums.length-2,因此special case里面应该有nums.length==1的时候的单独的算法。

     代码如下。~

public class Solution {  public int rob(int[] nums) {    if(nums.length==0||nums==null){      return 0;    }    return Math.max(rob1(nums,0,nums.length-2),rob1(nums,1,nums.length-1));          }    private int rob1(int[]nums, int start,int end){     if(nums.length==0||nums==null){      return 0;     }     if(nums.length==1){       return nums[0];     }     int prerob=0;     int predontrob=0;     for(int i=start;i<end+1;i++){       int curr=predontrob+nums[i];       int dontcurr=Math.max(prerob,predontrob);       prerob=curr;       predontrob=dontcurr;     }     return Math.max(prerob,predontrob);       }}

 




原标题:[LeetCode] House Robber II

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流