解題思維

labuladong 的演算法小抄 :: labuladong的演算法小抄

https://labuladong.github.io/algo/

常見解題框架

1. 暴力窮舉 → 最佳化

先寫出暴力解，再思考如何用資料結構或演演算法最佳化。

2. 雙指標（Two Pointers）

適用場景：已排序陣列、鏈結串列、滑動視窗問題

左右指標：從兩端向中間收斂（如 Two Sum II）
快慢指標：偵測環、找中點（如 Linked List Cycle）
滑動視窗：連續子陣列/子字串問題

3. 遞迴 / 回溯（Backtracking）

適用場景：排列組合、子集、棋盤問題

做選擇 → 遞迴 → 撤銷選擇

4. 動態規劃（DP）

適用場景：最優子結構 + 重疊子問題

1. 定義狀態（dp[i] 代表什麼）
2. 寫出狀態轉移方程
3. 確定 base case
4. 確定遍歷順序

5. BFS / DFS

• BFS：最短路徑、層序遍歷（用 Queue）
• DFS：路徑搜尋、連通性（用 Stack 或遞迴）

6. 貪心（Greedy）

每步都選當前最優解，適用於區間排程、跳躍遊戲等。

面試解題步驟

1. 釐清題意：確認輸入輸出、邊界條件
2. 想出暴力解：確保理解問題
3. 最佳化：找出重複計算或可利用的結構
4. 寫程式碼：保持清晰簡潔
5. 測試：用範例和邊界 case 驗證