House Robber II

https://leetcode.com/problems/house-robber-ii/description/

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.

Thoughts

解决circlular 的套路即假装把所有元素在尾巴处粘贴一次. 和House Robber的区别在于不能出现首尾元素都被选中的情况，也就是选了首元素则不能出现尾元素，反之亦然。那么实际上只会出现houserobber(0~n-2)或者houserobber(1~n-1)两种情况。我们因此相当于重新定义input array，分别计算houserobber(0~n-2)或者houserobber(1~n-1), 再比较下两种方式谁返回的多。

Code

class Solution {
    private int rob(int[] nums, int start, int end) {
        int[] f = new int[3];
        f[start % 3] = nums[start];
        f[(start + 1) % 3] = Math.max(f[start % 3], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            f[i % 3] = Math.max(f[(i - 1) % 3], f[(i - 2) % 3] + nums[i]);
        }
        return f[end % 3];
    }

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
}

Analysis

做题耗时25min

时间复杂度O(n).