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

【Leetcode】python – [162] Find Peak Element 個人解法筆記

題目出處

162. Find Peak Element

難度

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 種狀況

  1. [mid-1] < [mid] < [mid+1] ,正在往上走,把 start 移動往 mid (加速上坡)
  2. [mid-1] > [mid] > [mid+1] ,正在往下走,把 end 移動往 mid (減少下坡)
  3. [mid-1] < [mid] > [mid+1] ,paek 就是我們要的山峰
  4. [mid-1] > [mid] < [mid+1] ,valley 山谷,往兩側走都可

也可以再簡化,其實我們只要判斷一邊就好,
最後會縮小到一個範圍當中,其中一邊是高的,就是我們的局部最佳解。

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

input handling

處理沒有輸入的時候,return 0 (題目有保證不會有輸入問題)

Boundary conditions

binary search 的結束條件

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 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)