House Robber II

川长思鸟来 2021-12-17 10:37 190阅读 0赞

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.

这题是House Robber的follow up,加入了环的考虑。其实限制就是如果我们取数组的头，则一定没有办法取数组的尾元素，如果取了尾则一定没有办法取数组的头元素。即我们不一定取全部数组的最大rob结果。而是要么取nums\[1...n\], 要么是nums\[0...n-1\]。最后取两个结果的最大值，结合house robber的第一题，则可以得出本题的解法，时间复杂度为O(n),空间复杂度为O(1),代码如下：

class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #1.first pop out the leftest element
            #2.next pop out the rightest elemnt
            #3.get the max value of them two.
            if not nums:
                return 0
            if len(nums) < 3:
                return max(nums)
            #first pop out the leftest element
            f1 = nums[1]
            f2 = max(f1,nums[2])
            for n in nums[3:]:
                res = max(f1 + n, f2)
                f1 = f2
                f2 = res
            res1 = f2
            
            f1 = nums[0]
            f2 = max(f1,nums[1])
            for n in nums[2:-1]:
                res = max(f1 + n, f2)
                f1 = f2
                f2 = res
            res2 = f2
            return max(res1, res2)

转载于:https://www.cnblogs.com/sherylwang/p/5579987.html

[House Robber]: https://leetcode.com/problems/house-robber/