LeetCode 解題

演算法練習紀錄,包含解題思路、複雜度分析與最佳化策略。

ArrayHash Table
Easy

使用 Hash Map 儲存走過的數值與索引,只需遍歷一次 O(n)。

11. Container With Most Water

ArrayTwo PointersGreedy
Medium

雙指針從兩端向內收縮,每次移動高度較小的那一端,因為移動高的那端只會讓面積更小。

ArrayTwo PointersSorting
Medium

先排序,固定一個數後,使用雙指針尋找另外兩個數,注意去重。

20. Valid Parentheses

詳細筆記 →
StackString
Easy

用 Stack 配合 Hash Map 對照開閉括號。遇開括號 push,遇閉括號 pop 比對,最終 stack 需為空。

21. Merge Two Sorted Lists

Linked ListRecursion
Easy

比較兩個 ListNode 的值,遞迴地接上較小的節點;Iterative 則用 dummy head 簡化邊界處理。

42. Trapping Rain Water

詳細筆記 →
Two PointersDP
Hard

左右兩邊最高牆取 min 減去當前高度。可用雙指針優化空間至 O(1)。

49. Group Anagrams

詳細筆記 →
ArrayHash TableSortingString
Medium

同一組異位詞排序後相同,以排序結果作為 Map key 分組。進階可用 26 字元頻率陣列作 key。

56. Merge Intervals

ArraySorting
Medium

先按區間起點排序,再依序合併:若當前區間起點 ≤ 前一區間終點,則延伸終點;否則新開一個區間。

104. Maximum Depth of Binary Tree

TreeDFSBFS
Easy

DFS 遞迴:max(左子樹深度, 右子樹深度) + 1。BFS 層序遍歷:每跑一層 depth++,直到佇列清空。

121. Best Time to Buy and Sell Stock

詳細筆記 →
ArrayGreedy
Easy

一次遍歷,維護 minPrice 與 maxProfit,每天更新最低買入價,並計算今日賣出利潤是否創新高。

200. Number of Islands

ArrayDFSBFSUnion Find
Medium

遇到陸地 '1' 就 DFS/BFS 把整個連通的島嶼全部標記為已訪問,計數器 +1。時間複雜度 O(m×n)。

206. Reverse Linked List

Linked ListRecursion
Easy

Iterative 解法需三個指針 (prev, curr, next);Recursive 解法需注意 base case。

238. Product of Array Except Self

詳細筆記 →
ArrayPrefix Sum
Medium

不能用除法。前綴積填入輸出陣列後,再從右往左用一個 right 變數累乘後綴積,空間 O(1)。