LeetCode上的一道题

1.   House Robber II (#213)

After robbing those houses on that street, thethief has found himself a new place for his thievery so that he will not gettoo much attention. This time, all houses at this place are arranged in acircle. 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 theprevious street.

Given a list of non-negative integersrepresenting the amount of money of each house, determine the maximum amount ofmoney you can rob tonight without alerting the police.

 

解题思路：若列表长度为0则输出0，若长度为1则输出第一个元素，若长度为2则输出第一个和第二个中的最大的那个，若长度大于2则声明两个列表，第一个列表存储0到n-2最大和，第二个列表存储1到n-1最大的和，最后返回两个列表最后一个元素中最大的那个。

 

代码如下：

classSolution:

    def rob(self, nums):

        n = len(nums)

        result1 = [i for i in range(0, n - 1)]

        result2 = result1[:]

        if n == 0:

            return 0

        elif n == 1:

            return nums[0]

        elif n == 2:

            return max(nums)

        else:

            result1[0] = nums[0]

            result1[1] = max(nums[0], nums[1])

            for i in range(2, n - 1):

                result1[i] = max(result1[i - 2]+ nums[i], result1[i - 1])

            result2[0] = nums[1]

            result2[1] = max(nums[1], nums[2])

            for i in range(3, n):

                result2[i-1] = max(result2[i-3]+ nums[i], result2[i-2])

            return max(result2[-1],result1[-1])

 

 

结果：