0213. House Robber II - chasel2361/leetcode GitHub Wiki

You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money stashed.
All houses at this place are arranged in a circle.
That means the first house is the neighbor of the last one. Meanwhile, 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.

Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.

Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

這個問題跟前面一個搶匪問題差不多，只是要解決頭尾相連的條件

比較單純的解法是算兩次，一次強制取首項，一次強制不取首項，兩個結果取大者

強制取首項時，因為首尾相連，所以最多只能算到倒數第二項；強制不取首項，就可以計算到末項

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        if l <= 2: return max(nums)
            
        pre = nums[0]
        cur = max(nums[0], nums[1])
        res = max(nums[0], nums[1])
        for i in range(2, l-1):
            res = max(pre + nums[i], cur)
            pre = cur
            cur = res
        tmp = res
            
        pre = 0
        cur = nums[1]
        res = nums[1]
        for i in range(2, l):
            res = max(pre + nums[i], cur)
            pre = cur
            cur = res
                
        return max(tmp, res)

這樣的解法時間複雜度是 O(N)，空間複雜度為 O(1)

不過這樣寫要把整個陣列走兩次有點麻煩，不如增加一組變數，只要把陣列走過一次再比較也可以得到答案

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        if l <= 3: return max(nums)
            
        pre_1, now_1 = 0, nums[0]
        pre_2, now_2 = 0, nums[1]
            
        for i in range(1, l-1):
            tmp_1 = pre_1
            pre_1 = now_1
            now_1 = max(tmp_1 + nums[i], now_1)
                
            tmp_2 = pre_2
            pre_2 = now_2
            now_2 = max(tmp_2 + nums[i+1], now_2)
                
        return max(now_1, now_2)

如果這樣還嫌太長的話，可以利用python的特性，把暫存變數也丟掉(速度會再更快一點)

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0: return 0
        if l <= 3: return max(nums)
            
        pre_1, now_1 = 0, nums[0]
        pre_2, now_2 = 0, nums[1]
            
        for i in range(1, l-1):
            pre_1, now_1  = now_1, max(pre_1 + nums[i], now_1)
            pre_2 ,now_2 = now_2, max(pre_2 + nums[i+1], now_2)
                
        return max(now_1, now_2)

這兩種走法的時間複雜度跟空間複雜度跟前一個方法相同，是 O(N) 跟 O(1)。