項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [213] House Robber II 個人解法筆記

題目出處

213. House Robber II

難度

Medium

個人範例程式碼

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        dp_no_first = [0, nums[1]]
        dp_contains_first = [nums[0], max(nums[0], nums[1])]

        return max(self.get_max_rob(nums, dp_no_first), self.get_max_rob(nums[:-1], dp_contains_first)) 

    def get_max_rob(self, nums, dp):
        for i in range(2, len(nums)):
            dp.append(max(dp[i-2] + nums[i], dp[i-1]))

        return dp[-1]

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

算法說明

  • 這題的前一題為沒有循環房子的版本,可參考:

【Leetcode】python – [198] House Robber 個人解法筆記

相比上一題,這一題因為房子的排列會變成一個圈,因此我們把頭尾的關係分為兩段來考慮,

  • 不包含 0,一路算到 n
  • 包含 0,一路算到 n-1

input handling

處理 input 沒有房子與 input 只有一棟房子的情況

  • 沒有房子,return 0
  • 只有一棟房子,return 那一棟房子

Boundary conditions

for 來控制範圍

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091