題目出處
難度
medium
個人範例程式碼
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums:
return 0
start, end = 0, len(nums) - 1
while(start + 1 < end):
mid = (start + end) // 2
if(nums[mid] >= nums[mid+1]):
end = mid
else:
start = mid
else:
if(nums[start] >= nums[end]):
return start
else:
return end
算法說明
可以參考那邊的做法,這邊簡單寫
binary search,仔細討論會發現 mid 總共有 4 種狀況
- [mid-1] < [mid] < [mid+1] ,正在往上走,把 start 移動往 mid (加速上坡)
- [mid-1] > [mid] > [mid+1] ,正在往下走,把 end 移動往 mid (減少下坡)
- [mid-1] < [mid] > [mid+1] ,paek 就是我們要的山峰
- [mid-1] > [mid] < [mid+1] ,valley 山谷,往兩側走都可
也可以再簡化,其實我們只要判斷一邊就好,
最後會縮小到一個範圍當中,其中一邊是高的,就是我們的局部最佳解。
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
處理沒有輸入的時候,return 0 (題目有保證不會有輸入問題)
Boundary conditions
binary search 的結束條件
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 | Shortest Path in Binary Matrix | BFS (最短路徑) |