Monday, July 24, 2017

[Leetcode] House Robber II, Solution

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
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.

[Thoughts]
是House Robber的扩展题(http://fisherlei.blogspot.com/2017/07/leetcode-house-robber-solution.html ),唯一的区别就是house 0 和house n-1相邻了。根据题目要求,不能抢劫相邻的房子,所以这个环把它拆开就两种可能:

  1. 抢劫house 0,那么就不能抢劫house n-1,所以抢劫的范围就是[0, n-2]
  2. 不抢劫house 0,那么就得从house 1开始抢,抢劫的范围就是[1, n-1]
对于#1和#2两种情况,都可以复用House Robber的代码, 最后比较一下这两种可能中,那个收入多即可。


[Code]

1:    int rob(vector<int>& nums) {  
2:      int len = nums.size();  
3:        
4:      if(len == 0) return 0;      
5:      if(len == 1) return nums[0];  
6:        
7:      return max(robList(nums, 0, len -2), robList(nums, 1, len-1));  
8:    }  
9:      
10:    int robList(vector<int>& nums, int start, int end) {  
11:      int rob=0, no_rob=0;  
12:      for(int i = start; i<= end; i++) {  
13:        int new_rob = no_rob + nums[i];  
14:        no_rob = max(rob, no_rob);  
15:        rob = new_rob;  
16:      }  
17:        
18:      return max(rob, no_rob);  
19:    }  

No comments: