寫在本書之前
本書約定
- 一切以可讀性為目標(biāo)：Python、C++ 和 Java 混用
- 最小化語言特性，專注算法思維：使用內(nèi)置數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)
LeetCode
- 二叉樹節(jié)點
TreeNode - 單鏈表節(jié)點
ListNode
C++
函數(shù)參數(shù)默認(rèn)傳值：& 引用容器
-
動態(tài)數(shù)組
vector：避免從其中間或頭部增刪元素的低效操作 -
字符串
string：直接用if(s1 == s2)判斷相等 -
哈希表
unordered_map：- 鍵一般為
int或string類型 - 方括號
[]訪問鍵時，若鍵不存在，則自動創(chuàng)建
- 鍵一般為
- 哈希集合
unordered_set - 隊列
queue -
堆棧
stack-
pop方法是void類型的，需要先存待刪除元素
-
Java
- 數(shù)組 ：非空檢查
-
字符串
string：- 不能直接修改，要用
toCharArray轉(zhuǎn)化成char[]類型數(shù)組再修改 -
+拼接效率低，推薦使用StringBuilder的append方法 -
if(s1.equals(s2))判斷相等
- 不能直接修改，要用
- 動態(tài)數(shù)組
ArrayList - 雙鏈表
LinkedList - 哈希表
HashMap - 哈希集合
HashSet -
隊列
queue：Queue<String> q = new LinkedList<>() - 堆棧
stack
Python 3
-
列表
list：數(shù)組、堆棧和隊列 - 元組
tuple -
字典
dict- 動態(tài)規(guī)劃的備忘錄 ：
memo = dict(), memo[(i, j)]
- 動態(tài)規(guī)劃的備忘錄 ：
第 1 章 / 核心套路
-
算法：
- 通過合適的工具（數(shù)據(jù)結(jié)構(gòu)）
- 解決特定問題的方法
1.1. 框架思維
- 從整體到細(xì)節(jié)
- 自頂向下
- 從抽象到具體
1.1.1. 數(shù)據(jù)結(jié)構(gòu)的存儲方式
- 數(shù)組（順序存儲）
- 隨機訪問
- 復(fù)制擴容
- 移動插入刪除
- 鏈表（鏈?zhǔn)酱鎯?/em>）
- 順序訪問
- 插入擴容
- 直接插入刪除
| 數(shù)組 | 鏈表 | |
|---|---|---|
| 隊列/棧 | 需處理擴容和縮容 | 需存儲節(jié)點指針 |
| 圖 | 鄰接矩陣 | 鄰接表（稀疏矩陣） |
| 哈希表（處理哈希沖突） | 線性探查法 | 拉鏈法 |
| 樹 | 堆（完全二叉樹） | 二叉搜索樹、AVL 樹、紅黑樹、區(qū)間樹、B 樹等 |
1.1.2. 數(shù)據(jù)結(jié)構(gòu)的基本操作
數(shù)據(jù)結(jié)構(gòu)的使命：
- 在不同的應(yīng)用場景下盡可能 高效 地 增、刪、查、改
遍歷 + 訪問：
-
線性：for/while 迭代
- 數(shù)組迭代 遍歷框架
void traverse(int [] arr) { for (int i = 0; i < arr.length; i++) { // 迭代遍歷 arr[i] } }- 鏈表迭代 遍歷框架
/* 單鏈表節(jié)點 */ class ListNode { int val; ListNode next; } void traverse(ListNode head) { for (ListNode p = head; p != null; p = p.next) { // 迭代遍歷 p.val } } -
非線性：遞歸
- 鏈表遞歸 遍歷框架
void traverse(ListNode head) { // 前序遍歷 head.val traverse(head.next); // 后序遍歷 head.val }- 二叉樹遞歸 遍歷框架
/* 二叉樹節(jié)點 */ class TreeNode { int val; TreeNode left, right; } void traverse(TreeNode root) { // 前序遍歷（根左右） traverse(root.left); // 中序遍歷（左根右） traverse(root.right); // 后序遍歷（左右根） }- N 叉樹遞歸 遍歷框架 → 圖的遍歷（多個 N 叉樹 + 布爾數(shù)組 visited）
/* N 叉樹節(jié)點 */ class TreeNode { int val; TreeNode[] children; } void traverse(TreeNode root) { for (TreeNode child : root.children) { traverse(child); } }
算法刷題第一步：二叉樹
- 最容易培養(yǎng)框架思維
- 大部分?？妓惴ǎ?strong>回溯、動態(tài)規(guī)劃、分治）本質(zhì)上是樹的遍歷問題（遞歸）
1.2. 動態(tài)規(guī)劃解題套路框架
- 一般形式：求最值（如 最長 遞增子序列、最小 編輯距離）
↓
- 核心問題：窮舉
-
動態(tài)規(guī)劃三要素
- 存在“重疊子問題”：優(yōu)化窮舉效率（備忘錄、DP table）
- 具備“最優(yōu)子結(jié)構(gòu)”：子問題的最值 → 原問題的最值
- 正確的“狀態(tài)轉(zhuǎn)移方程”
- 問題的 base case（最簡單情況）
- “狀態(tài)”空間
- “選擇”使“狀態(tài)”改變
- dp 數(shù)組表示“狀態(tài)”和“選擇”
# 初始化 base case
dp[0][0][...] = base case
# 進(jìn)行狀態(tài)轉(zhuǎn)移
for 狀態(tài) 1 in 狀態(tài) 1 的所有取值:
for 狀態(tài) 2 in 狀態(tài) 2 的所有取值:
for ...
dp[狀態(tài) 1][狀態(tài) 2][...] = 求最值 (選擇 1, 選擇 2, ...)
1.2.1. 斐波那契數(shù)列：重疊子問題
斐波那契數(shù)列：1, 1, 2, 3, 5, 8, ...
int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
- 遞歸算法 的遞歸樹：時間復(fù)雜度 O(2N)，空間復(fù)雜度 O(1)
遞歸算法的遞歸樹
↓“剪枝”
- 帶“備忘錄”的遞歸算法（自頂向下） 的遞歸圖：時間復(fù)雜度 O(N)，空間復(fù)雜度 O(N)
帶“備忘錄”的遞歸算法的遞歸圖
↓
- dp 數(shù)組的迭代算法（自底向上） 的 DP table 圖：時間復(fù)雜度 O(N)，空間復(fù)雜度 O(N)
DP table
int fib(iny N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
vector<int> dp(N + 1, 0);
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
狀態(tài)轉(zhuǎn)移方程：
狀態(tài)轉(zhuǎn)移方程
↓
狀態(tài)壓縮 的dp 數(shù)組的迭代算法：時間復(fù)雜度 O(N)，空間復(fù)雜度 O(1)
int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
int pre2 = 1, pre1 = 1;
for (int i = 3; i <= N; i++) {
int cur = pre2 + pre1;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
1.2.2. 湊零錢問題：狀態(tài)轉(zhuǎn)移方程
k 種面值的硬幣：c1, c2, ..., ck，以最少的硬幣數(shù)湊出總金額 amount
算法的函數(shù)簽名：
// coins 可選硬幣面值，amount 目標(biāo)金額
int coinChange(int[] coins, int amount);
-
暴力遞歸：確定狀態(tài)轉(zhuǎn)移方程
- 時間復(fù)雜度 O(knk)，空間復(fù)雜度 O(1)
- 確定 base case：amount 為 0 時，算法返回 0
- 確定“狀態(tài)”：amount
- 確定“選擇”：coins
- 確定 dp 函數(shù)/數(shù)組的定義：輸入 amount，輸出湊出 amount 的最少硬幣數(shù)量
int coinChange(int[] coins, int amount) {
return dp(amount, coins);
}
int dp(int n, int[] coins) {
// base case
if (n == 0) return 0;
if (n < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int subproblem = dp(n - coin, coins);
// 子問題不能湊出，跳過這一面值
if (subproblem == -1) continue;
// 取子問題中各面值的最少硬幣數(shù)
res = Math.min(res, 1 + subproblem);
}
// 原問題不能湊出，則返回 -1
return (res != Integer.MAX_VALUE) ? res : -1;
}
結(jié)果：遞歸超時
-
帶“備忘錄”的遞歸：自頂向下，消除重疊子問題
- 時間復(fù)雜度 O(kn)，空間復(fù)雜度 O(n)
int coinChange(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, 0);
return helper(memo, amount, coins);
}
int helper(int[] memo, int n, int[] coins) {
// base case
if (n == 0) return 0;
if (n < 0) return -1;
if (memo[n] != 0) return memo[n];
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int subproblem = helper(memo, n - coin, coins);
// 子問題不能湊出，則跳過這一面值
if (subproblem == -1) continue;
// 取子問題中各面值的最少硬幣數(shù)
res = Math.min(res, 1 + subproblem);
}
// 原問題不能湊出，則設(shè)置備忘錄值為 -1
memo[n] = (res != Integer.MAX_VALUE) ? res : -1;
return memo[n];
}
-
dp 數(shù)組的迭代：自底向上
- 時間復(fù)雜度 O(kn)，空間復(fù)雜度 O(n)
int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return -1;
int[] dp = new int[amount + 1];
// 初始化為 amount + 1，最多用 amount + 1 枚硬幣湊出
Arrays.fill(dp, amount + 1);
// base case
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
// 子問題超出范圍，跳過
if (i - coin < 0) continue;
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] != amount + 1) ? dp[amount] : -1;
}
