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

【Leetcode】python – [121] Best Time to Buy and Sell Stock 個人解法筆記 (updated: 2022/4/15)

題目出處

121. Best Time to Buy and Sell Stock

難度

Easy

題目分類

array, dynamic-programming

個人範例程式碼 – 2022/4/15

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices) < 2:
            return 0

        min_buy = prices[0]
        best_profit = 0

        for i, today_price in enumerate(prices):
            if i == 0: # pass first day
                continue
            else:
                min_buy = min(min_buy, today_price)
                best_profit = max(best_profit, today_price - min_buy)

        return best_profit

算法說明

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

input handling

處理沒有 input 或 input 只有一天 (沒得賣啊!) 的情況,return 0

Boundary conditions

for 迴圈,不怕出界

個人範例程式碼 – 2022/3/2

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_buyin_record = 999999 # min buy in 
        res_record = 0 # max result  
        for today in range(len(prices)):
            if today == 0: # first
                min_buyin_record = prices[today]
            else:
                min_buyin_record = min(min_buyin_record, prices[today])
                res_record = max(res_record, prices[today] - min_buyin_record)

        return res_record

Time Complexity

O(n)

算法說明

唯一要記錄只有兩個

  • 到今日之前的「購入最低價」
  • 到今日之前的「最佳結果」

corner case 特殊情況處理

當只有一天時,需要回傳 0,
這邊我在初始化時解掉了。

Boundary conditions/ Edge conditions 邊際情況處理

初始值處理

  • 第一天時,因為沒有最大值,我特別去判斷現在進來的是不是第一天,

  • 不過後來有使用另外一個做法,先定義最小值為「999999」,
    預設第一天就會被取代。

這個可以成功的原因是因為:
題目限制「0 <= prices[i] <= 10^4」

兩種作法應該都可以,我之後應該會選擇第一種,去避免自訂義值的情況。

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 (拓撲)