題目出處
難度
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,可以嘗試直接閱讀程式碼理解
算法說明
- 這題的前一題為沒有循環房子的版本,可參考:
相比上一題,這一題因為房子的排列會變成一個圈,因此我們把頭尾的關係分為兩段來考慮,
- 不包含 0,一路算到 n
- 包含 0,一路算到 n-1
input handling
處理 input 沒有房子與 input 只有一棟房子的情況
- 沒有房子,return 0
- 只有一棟房子,return 那一棟房子
Boundary conditions
for 來控制範圍
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |
1091 |