iT邦幫忙

2025 iThome 鐵人賽

DAY 24
0
自我挑戰組

LeetCode演算法解密:30天強化演算法戰力系列 第 24

Day 24 - Leetcode刷題213. House Robber II (Med)

  • 分享至 

  • xImage
  •  

題目連結: 213. House Robber II

題目描述:與前天的題目幾乎一樣,但增加了一個條件:所有房屋圍成一個環。這意味著第一間房子和最後一間房子是相鄰的。同樣地,你不能偷竊相鄰的房屋。請問你能偷竊到的最高總金額是多少?

Example 1:
Input: nums = [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: nums = [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.

Example 3:
Input: nums = [1,2,3]
Output: 3


Python

解題思路:
昨天的解法沒有考慮到「頭尾相連」的約束。如果我們直接套用,可能會同時選擇偷第一間和最後一間,這在環形結構中是不被允許的。
不產生環形的方法只要把問題劃分不偷第一間與偷第一間,那麼解決問題不就與昨天一模一樣了嗎!


class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob1(nums):
            dp0 = 0
            dp1 = 0
            for i in range(len(nums)):
                curr =max(dp1,dp0+nums[i])
                temp = dp1
                dp1 = curr 
                dp0 = temp
            return dp1
        if len(nums)<=3:
            return max(nums)
        sum1 = rob1(nums[1:])# 第一間不偷
        sum2 = rob1(nums[:-1])# 最後一間偷
        return max(sum1,sum2)

演算法分析:

  • 這個問題比「House Robber」只多了一個「環形」的約束,即第一間房 nums[0] 和最後一間房 nums[n-1] 是相鄰的。
  • 不過先考慮如果nums陣列數量<=3時,直接回傳最大值就行了。

複雜度分析:

  • 時間複雜度為 O(n)(演算法的核心是一個 for 迴圈,它遍歷了 nums 陣列一次。)。
    1. 第一次呼叫 rob_linear(nums[1:]),傳入的子陣列長度也為 n-1。其時間複雜度為 O(n-1)
    2. 第二次呼叫 rob_linear(nums[:-1]),傳入的子陣列長度也為 n-1。時間複雜度同樣是 O(n-1)
    3. 總的時間複雜度是 O(n-1) + O(n-1)忽略常數和低階項,所以最終時間複雜度為 O(n)。
  • 空間複雜度: O(1)O(n)(這個演算法的核心邏輯只需要 O(1) 的輔助空間。,為了程式碼的簡潔,使用了切片操作,這會產生 O(n) 的臨時空間)。

有問題可以底下留言!
下回見!!/images/emoticon/emoticon37.gif


上一篇
Day 23 - Leetcode刷題70. Climbing Stairs(Easy)
下一篇
Day 25 - Leetcode刷題 740. Delete and Earn(Med)
系列文
LeetCode演算法解密:30天強化演算法戰力25
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言