LeetCode Digest
5 分鐘 閱讀文 (大約 687 個字)

House Robber II

題目
思路

  1. 跟 House Robber 很像，只差在房子的排列變成頭尾相連，有沒有辦法把這題拆解，變成能用上第一版 House Robber 的解題方法？譬如把環形變回直排？
  2. 變成環形之後多出來的限制讓我們可以把這題分成以下三種情況：
    1. 搶第一個、不搶最後一個：加入第三種情況，等同於可以視為直排，但只考慮到倒數第二個
    2. 不搶第一個、搶最後一個：加入第三種情況，等同於可以視為直排，但從第二個開始考慮
    3. 第一個和最後一個都不搶：可與前兩種情況合併
    • 最後把以上三種情況合併為粗體的兩種情況，轉為第一版 House Robber 問題，接下來只需取兩種情況錢比較多的就是答案
  3. 因為現在需多考慮起始 index，我們把第一版解法的遞迴函式改為多傳入起始 index，並同樣用 @cache 避免同樣的 inner_rob(i, j) 重複計算
    • Base case 寫法：
      1. 考慮一開始 j 比 i 大的情況，一路因為 inner_rob(i, j - 1), inner_rob(i, j - 2) 而減少的情況：
        1. j == i + 2 時：下兩個遞迴節點為 inner_rob(i, i + 1), inner_rob(i, i)
        2. j == i + 1 時： 下兩個遞迴節點為 inner_rob(i, i), inner_rob(i, i - 1)
        • 此時可以寫出 base case 的兩種情況 j == i, j < i
      2. 考慮 nums 數字最小的幾種情況，看看遞迴是否正常收斂 or 結果是否正確
        1. len(nums) == 3:
          • max(inner_job(0, 1), inner_job(1, 2)) -> 正常收斂
        2. len(nums) == 2:
          • max(inner_job(0, 0), inner_job(1, 1)) -> 結果正確
        3. len(nums) == 1:
          • max(inner_job(0, -1), inner_job(1, 0))
          • 此時得出的答案為 0，是錯的，所以 base case 需多考慮這種情況，加入 len(nums) == 1 時的判斷處理
  4. 取錢比較多的情況即為答案：return max(inner_rob(0, len(nums) - 2), inner_rob(1, len(nums) - 1))

Python3 solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rob(self, nums: List[int]) -> int:
    @cache
    def inner_rob(i, j):
        """@return 由 index i 搶到 j 可得的最大收穫"""
        # Base case
        if len(nums) == 1:
            return nums[0]
        if j == i:
            return nums[j]
        if j < i:
            return 0
            
        # Recursive case
        return max(inner_rob(i, j - 1), nums[j] + inner_rob(i, j - 2))
        
    return max(inner_rob(0, len(nums) - 2), inner_rob(1, len(nums) - 1))

如果不用 @cache:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def rob(self, nums: List[int]) -> int:
    l = len(nums)
    memo = [[None] * l for _ in range(l)]

    def inner_rob(i, j):
        """@return 由 index i 搶到 j 可得的最大收穫"""
        if len(nums) == 1:
            return nums[0]
        if i == j:
            return nums[j]
        if j < i:
            return 0
            
        if memo[i][j] is not None:
            return memo[i][j]
        memo[i][j] = max(inner_rob(i, j - 1), nums[j] + inner_rob(i, j - 2))
        return memo[i][j]
        
    return max(inner_rob(0, len(nums) - 2), inner_rob(1, len(nums) - 1))
# ,
Binary Tree Inorder Traversal
遞迴的時間複雜度算法

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×