LeetCode 213. House Robber II

原题链接在这里：https://leetcode.com/problems/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.

题解：

For questions with array working as circle.

There are 2 ways.

First is to calculate [0, nums.length-2] and [1, nums.length-1]. This is to avoid first and last having some constraint.

Second is to go through the array twice. This is to get the maximum or minimum value.

比较从第一家到倒数第二家能偷最大值和把第二家到最后一家能偷最大值, 返回较大者.

corner case nums.length == 1, return nums[0].

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 public class Solution {
 2     public int rob(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return 0;
 5         }
 6         if(nums.length == 1){
 7             return nums[0];
 8         }
 9         return Math.max(robHelper(nums, 0, nums.length-2), robHelper(nums, 1, nums.length-1));
10     }
11     
12     private int robHelper(int [] nums, int l, int r){
13         int include = 0;
14         int exclude = 0;
15         for(int cur = l; cur<=r; cur++){
16             int i = include;
17             int e = exclude;
18             exclude = Math.max(i, e);
19             include = e+nums[cur];
20         }
21         return Math.max(exclude, include);
22     }
23 }

是House Robber的进阶题.

跟上House Robber III.