算法与数据结构入门（JS → Python 双语版）
面向有 JS 基础的开发者——用你最熟悉的语言理解算法思路，再用 Python 重写一遍，一箭双雕：掌握核心算法 + 入门 Python 语法。每道题先看 JS 版"我懂了"，再看 Python 版"原来这么写"。
1. 从 JS 到 Python：语法速查对照
这一章不讲算法——专门用来过渡语法差异。目标是：看完这章，后面所有章节的 Python 代码你都能看懂。
如果你已经会 Python，直接跳到第 2 章。如果你只写过 JS，花 15 分钟过一遍这里的对照表，后面会非常轻松。
💡 本章的使用方式：不需要背，当作字典来查。写算法时遇到"这个 Python 怎么写来着"，回来翻这一章就行。
1.1 变量、类型与基本运算
JS 和 Python 在变量声明、数据类型上有不少差异，但核心思路一致。
变量声明：
javascript
// JavaScript
let count = 10; // 可变变量
const MAX = 100; // 常量（不可重新赋值）
var old = "别用了"; // 旧语法，有作用域陷阱python
# Python
count = 10 # 直接赋值，不需要 let/const/var
MAX = 100 # Python 没有真正的常量，全大写只是约定数据类型对照：
| JS 类型 | Python 类型 | 说明 |
|---|---|---|
number | int / float | Python 区分整数和浮点数，JS 不区分 |
string | str | 几乎一样，Python 单双引号完全等价 |
boolean（true/false） | bool（True/False） | ⚠️ 注意大写！ |
null | None | ⚠️ 注意大写！ |
undefined | 无对应 | Python 没有 undefined |
Array | list | Python 的列表 = JS 的数组 |
Object | dict | Python 的字典 = JS 的普通对象 |
Set | set | 两者几乎一样 |
Map | dict | Python 的 dict 天然就是有序的 |
基本运算：
javascript
// JavaScript
console.log(10 / 3); // 3.333...（总是浮点除法）
console.log(Math.floor(10 / 3)); // 3（手动取整）
console.log(10 % 3); // 1（取余）
console.log(2 ** 10); // 1024（幂运算）
console.log("abc".length); // 3python
# Python
print(10 / 3) # 3.333...（浮点除法）
print(10 // 3) # 3（整除，JS 没有的运算符！）
print(10 % 3) # 1（取余，一样）
print(2 ** 10) # 1024（幂运算，一样）
print(len("abc")) # 3（用 len() 函数，不是 .length）💡 算法中最常用的差异：Python 的
//整除运算符在算法题里非常常见（比如二分查找的mid = (left + right) // 2）。JS 需要用Math.floor()来实现同样的效果。
类型检查：
javascript
// JavaScript
typeof 42; // "number"
typeof "hello"; // "string"
Array.isArray([1,2,3]); // truepython
# Python
type(42) # <class 'int'>
type("hello") # <class 'str'>
isinstance([1,2,3], list) # True（推荐用 isinstance）类型转换：
javascript
// JavaScript
Number("42"); // 42
String(42); // "42"
parseInt("3.14"); // 3
parseFloat("3.14"); // 3.14python
# Python
int("42") # 42
str(42) # "42"
int(3.14) # 3（直接截断，不四舍五入）
float("3.14") # 3.141.2 数组/列表、对象/字典、字符串
算法题 90% 的时间都在操作这三种数据结构。把 JS 和 Python 的差异搞清楚，后面写代码会顺畅很多。
数组 vs 列表——创建与访问：
javascript
// JavaScript
const arr = [1, 2, 3, 4, 5];
arr[0]; // 1
arr[arr.length - 1]; // 5（最后一个元素）
arr.length; // 5python
# Python
arr = [1, 2, 3, 4, 5]
arr[0] # 1
arr[-1] # 5（负索引！直接取最后一个，超好用）
len(arr) # 5（又是 len() 函数）💡 Python 的负索引是写算法时的大杀器：
arr[-1]最后一个，arr[-2]倒数第二个。JS 需要arr[arr.length - 1]，Python 优雅得多。
数组/列表的常用操作对照：
| 操作 | JavaScript | Python |
|---|---|---|
| 末尾添加 | arr.push(6) | arr.append(6) |
| 末尾删除 | arr.pop() | arr.pop() |
| 头部添加 | arr.unshift(0) | arr.insert(0, 0) |
| 头部删除 | arr.shift() | arr.pop(0) |
| 切片 | arr.slice(1, 3) | arr[1:3] |
| 拼接 | [...a, ...b] | a + b |
| 查找元素 | arr.indexOf(3) | arr.index(3) |
| 是否包含 | arr.includes(3) | 3 in arr |
| 反转 | arr.reverse() | arr.reverse() 或 arr[::-1] |
| 排序 | arr.sort((a,b) => a-b) | arr.sort() |
| 长度 | arr.length | len(arr) |
切片——Python 的王牌语法：
python
# Python 的切片语法：arr[start:end:step]
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arr[2:5] # [2, 3, 4] 从索引2到4（不含5）
arr[:3] # [0, 1, 2] 前3个
arr[7:] # [7, 8, 9] 从索引7到末尾
arr[-3:] # [7, 8, 9] 最后3个
arr[::2] # [0, 2, 4, 6, 8] 每隔2个取一个
arr[::-1] # [9, 8, ..., 0] 反转整个列表javascript
// JavaScript 对应写法（没那么简洁）
arr.slice(2, 5); // [2, 3, 4]
arr.slice(0, 3); // [0, 1, 2]
arr.slice(7); // [7, 8, 9]
arr.slice(-3); // [7, 8, 9]
arr.filter((_, i) => i % 2 === 0); // 每隔2个（麻烦多了）
[...arr].reverse(); // 反转对象 vs 字典：
javascript
// JavaScript
const obj = { name: "Alice", age: 25 };
obj.name; // "Alice"（点语法）
obj["name"]; // "Alice"（括号语法）
Object.keys(obj); // ["name", "age"]
Object.values(obj); // ["Alice", 25]
Object.entries(obj); // [["name", "Alice"], ["age", 25]]
"name" in obj; // truepython
# Python
obj = {"name": "Alice", "age": 25}
obj["name"] # "Alice"（只有括号语法！）
# obj.name # ❌ 报错！Python 字典没有点语法
obj.get("name") # "Alice"（安全访问，key 不存在返回 None）
obj.keys() # dict_keys(["name", "age"])
obj.values() # dict_values(["Alice", 25])
obj.items() # dict_items([("name", "Alice"), ("age", 25)])
"name" in obj # True💡 算法中的关键差异：Python 字典的
.get(key, default)方法在算法题里极其常用——count.get(char, 0) + 1一行搞定字符计数，JS 需要count[char] = (count[char] || 0) + 1。
字符串——不可变的老朋友：
javascript
// JavaScript
const s = "hello world";
s[0]; // "h"
s.toUpperCase(); // "HELLO WORLD"
s.split(" "); // ["hello", "world"]
s.includes("world"); // true
s.replace("world", "python"); // "hello python"
`count is ${42}`; // 模板字符串
"ha".repeat(3); // "hahaha"python
# Python
s = "hello world"
s[0] # "h"
s.upper() # "HELLO WORLD"（方法名不同！）
s.split(" ") # ["hello", "world"]
"world" in s # True（用 in 运算符，不是方法）
s.replace("world", "python") # "hello python"
f"count is {42}" # f-string（类似模板字符串）
"ha" * 3 # "hahaha"（乘法运算符！）| 操作 | JavaScript | Python |
|---|---|---|
| 大写 | s.toUpperCase() | s.upper() |
| 小写 | s.toLowerCase() | s.lower() |
| 去空格 | s.trim() | s.strip() |
| 分割 | s.split(",") | s.split(",") |
| 连接数组 | arr.join(",") | ",".join(arr) |
| 包含 | s.includes("x") | "x" in s |
| 开头判断 | s.startsWith("h") | s.startswith("h") |
| 字符串拼接 | `${a} ${b}` | f"{a} {b}" |
💡 Python 字符串是不可变的（和 JS 一样）。
s.upper()不会修改s，而是返回一个新字符串。算法题里如果需要"修改字符串"，通常先转成列表：list(s)→ 操作 →"".join(list)。
1.3 条件、循环与函数
这三个是写算法代码的"骨架"——条件决定分支，循环驱动遍历，函数组织逻辑。
条件语句：
javascript
// JavaScript
if (x > 0) {
console.log("正数");
} else if (x === 0) {
console.log("零");
} else {
console.log("负数");
}
// 三元表达式
const result = x > 0 ? "正" : "非正";python
# Python
if x > 0:
print("正数") # 缩进代替花括号！
elif x == 0: # elif 不是 else if！
print("零")
else:
print("负数")
# 三元表达式（语序不同）
result = "正" if x > 0 else "非正"💡 Python 用缩进代替花括号，这是最大的语法差异。缩进必须一致（通常 4 空格），混用空格和 Tab 会报错。
for 循环：
javascript
// JavaScript
// 遍历数组
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// for...of（推荐）
for (const item of arr) {
console.log(item);
}
// 带索引
arr.forEach((item, index) => {
console.log(index, item);
});python
# Python
# 遍历列表（直接 for...in）
for item in arr:
print(item)
# 需要索引？用 enumerate（算法题里超常用！）
for index, item in enumerate(arr):
print(index, item)
# 需要数字范围？用 range
for i in range(5): # 0, 1, 2, 3, 4
print(i)
for i in range(2, 8): # 2, 3, 4, 5, 6, 7
print(i)
for i in range(0, 10, 2): # 0, 2, 4, 6, 8（步长为2）
print(i)
for i in range(5, 0, -1): # 5, 4, 3, 2, 1（倒序）
print(i)💡
range()是 Python 算法题的基础设施。JS 没有直接等价的，需要用for (let i = 0; i < n; i++)。记住range(start, stop, step)，左闭右开。
while 循环：
javascript
// JavaScript
let i = 0;
while (i < 10) {
console.log(i);
i++;
}python
# Python
i = 0
while i < 10:
print(i)
i += 1 # ⚠️ Python 没有 i++ / i--，只有 i += 1函数：
javascript
// JavaScript
function add(a, b) {
return a + b;
}
// 箭头函数
const add = (a, b) => a + b;
// 默认参数
function greet(name = "World") {
return `Hello, ${name}`;
}python
# Python
def add(a, b):
return a + b
# lambda（对应箭头函数，但只能写一行）
add = lambda a, b: a + b
# 默认参数
def greet(name="World"):
return f"Hello, {name}"列表推导式——Python 的"函数式一行流"：
javascript
// JavaScript 的 map/filter
const doubled = arr.map(x => x * 2);
const evens = arr.filter(x => x % 2 === 0);
const sum = arr.reduce((acc, x) => acc + x, 0);python
# Python 列表推导式（算法题里用得极多）
doubled = [x * 2 for x in arr]
evens = [x for x in arr if x % 2 == 0]
total = sum(arr) # 内置 sum() 函数，不需要 reduce
# 更复杂的推导式
matrix = [[j for j in range(3)] for i in range(3)]
# → [[0,1,2], [0,1,2], [0,1,2]]💡 列表推导式是 Python 算法代码简洁的秘密武器。JS 用
.map().filter()链式调用，Python 用推导式一行搞定，可读性更好。
1.4 解构赋值、展开运算符与 Python 等价写法
JS 开发者日常离不开解构和展开运算符，Python 有完全对等的语法——只是写法不同。
数组/列表解构：
javascript
// JavaScript
const [a, b, c] = [1, 2, 3];
const [first, ...rest] = [1, 2, 3, 4, 5];
// first = 1, rest = [2, 3, 4, 5]
const [x, , z] = [1, 2, 3]; // 跳过第二个
// x = 1, z = 3python
# Python
a, b, c = [1, 2, 3] # 直接解包，不需要 []
first, *rest = [1, 2, 3, 4, 5]
# first = 1, rest = [2, 3, 4, 5]（* 代替 ...）
x, _, z = [1, 2, 3] # _ 是惯用的"丢弃"变量
# x = 1, z = 3💡 Python 的
*rest= JS 的...rest。在算法题里，a, *mid, b = arr可以同时取首尾元素，非常方便。
对象/字典解构：
javascript
// JavaScript
const { name, age } = { name: "Alice", age: 25 };
const { name: n, age: a } = { name: "Alice", age: 25 };
// 重命名：n = "Alice", a = 25python
# Python——字典没有直接解构语法，但有替代方案
obj = {"name": "Alice", "age": 25}
name, age = obj["name"], obj["age"] # 手动取值
name, age = obj.values() # 按值顺序解包
# 函数参数中的字典解包（最接近 JS 解构的用法）
def greet(name, age):
print(f"{name} is {age}")
greet(**obj) # ** 展开字典为关键字参数 → greet(name="Alice", age=25)展开运算符：
javascript
// JavaScript
const arr1 = [1, 2, 3];
const arr2 = [4, 5, 6];
const merged = [...arr1, ...arr2]; // [1,2,3,4,5,6]
const obj1 = { a: 1, b: 2 };
const obj2 = { ...obj1, c: 3 }; // { a:1, b:2, c:3 }python
# Python
arr1 = [1, 2, 3]
arr2 = [4, 5, 6]
merged = [*arr1, *arr2] # [1,2,3,4,5,6]（* 展开列表）
# 或者：merged = arr1 + arr2 # 更简单
obj1 = {"a": 1, "b": 2}
obj2 = {**obj1, "c": 3} # {"a":1, "b":2, "c":3}（** 展开字典）交换变量——Python 的优雅：
javascript
// JavaScript（需要临时变量或解构）
[a, b] = [b, a];python
# Python（天然支持多重赋值）
a, b = b, a # 就这么简单，不需要临时变量💡 算法题里的经典场景：交换数组中两个元素
arr[i], arr[j] = arr[j], arr[i]，排序算法里用得极多。
JS ... vs Python * / ** 速查：
| 场景 | JavaScript | Python |
|---|---|---|
| 数组展开 | [...arr] | [*arr] |
| 对象展开 | {...obj} | {**obj} |
| 剩余参数 | function f(...args) | def f(*args) |
| 关键字参数 | 无直接等价 | def f(**kwargs) |
| 剩余解构 | [first, ...rest] | first, *rest |
1.5 类与面向对象：JS class vs Python class
算法题用到类的场景主要是：自定义数据结构（链表节点、树节点、图节点）。不需要深入 OOP，但必须能看懂和写出简单的类。
基础类定义：
javascript
// JavaScript
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
toString() {
return `Node(${this.val})`;
}
}
const node = new ListNode(42);
console.log(node.val); // 42
console.log(node.next); // nullpython
# Python
class ListNode:
def __init__(self, val, next=None): # __init__ = constructor
self.val = val # self = this
self.next = next
def __str__(self): # __str__ = toString
return f"Node({self.val})"
node = ListNode(42) # ⚠️ 不需要 new！
print(node.val) # 42
print(node.next) # None关键差异速查：
| 特性 | JavaScript | Python |
|---|---|---|
| 构造函数 | constructor() | __init__(self) |
| this/self | this（隐式） | self（显式，必须作为第一个参数） |
| 创建实例 | new ClassName() | ClassName()（不需要 new） |
| toString | toString() | __str__() |
| 私有属性 | #field（ES2022） | _field（约定，非强制） |
| 继承 | class B extends A | class B(A) |
继承：
javascript
// JavaScript
class TreeNode extends ListNode {
constructor(val, left = null, right = null) {
super(val); // 调用父类构造函数
this.left = left;
this.right = right;
}
}python
# Python
class TreeNode(ListNode): # 括号里放父类
def __init__(self, val, left=None, right=None):
super().__init__(val) # 调用父类构造函数
self.left = left
self.right = right💡 算法题中最常用的类就这几个：
ListNode（链表节点）、TreeNode（树节点）。LeetCode 通常会帮你定义好这些类，你只需要会用就行。但理解它们的结构有助于调试。
第 1 章核心知识回顾：
| JS 概念 | Python 等价 | 注意事项 |
|---|---|---|
let / const | 直接赋值 | Python 没有变量声明关键字 |
arr.length | len(arr) | Python 统一用 len() 函数 |
arr[arr.length-1] | arr[-1] | 负索引是 Python 的杀器 |
arr.push() / arr.pop() | arr.append() / arr.pop() | push → append |
{...obj} | {**obj} | * 展开列表，** 展开字典 |
for...of | for...in | Python 的 in = JS 的 of |
arr.map(fn) | [fn(x) for x in arr] | 列表推导式更 Pythonic |
x > 0 ? a : b | a if x > 0 else b | 语序不同 |
new ClassName() | ClassName() | Python 不需要 new |
this | self | Python 的 self 要显式声明 |
Math.floor(a/b) | a // b | 整除运算符 |
i++ | i += 1 | Python 没有自增运算符 |
2. 复杂度分析：算法的"标尺"
学算法之前，先学会衡量算法的好坏。不然你怎么知道自己写的代码是快还是慢？
复杂度分析就像跑步计时——不需要跑完全程才知道快慢，看跑法就能预估。面试官问"你这个解法的时间复杂度是多少"，你得张口就来。
💡 本章的目标：看到一段代码，能在 30 秒内说出它的时间复杂度和空间复杂度。不需要做数学证明，建立直觉就够了。
2.1 什么是时间复杂度：代码跑多快
时间复杂度不是测量代码实际跑了多少秒——而是描述当输入规模 n 增大时，执行次数的增长趋势。
用大 O 表示法（Big O Notation）来表示。
O(1) — 常数时间：不管输入多大，都是固定步骤
javascript
// JavaScript
function getFirst(arr) {
return arr[0]; // 不管数组多长，都只执行 1 次
}python
# Python
def get_first(arr):
return arr[0] # O(1)，和数组长度无关O(n) — 线性时间：输入翻倍，执行次数也翻倍
javascript
// JavaScript
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) { // 循环 n 次
total += arr[i];
}
return total; // O(n)
}python
# Python
def sum_arr(arr):
total = 0
for num in arr: # 循环 n 次
total += num
return total # O(n)O(n²) — 平方时间：嵌套循环，输入翻倍，执行次数翻 4 倍
javascript
// JavaScript
function hasDuplicate(arr) {
for (let i = 0; i < arr.length; i++) { // 外层 n 次
for (let j = i + 1; j < arr.length; j++) { // 内层 n 次
if (arr[i] === arr[j]) return true;
}
}
return false; // O(n²)，两层循环
}python
# Python
def has_duplicate(arr):
for i in range(len(arr)): # 外层 n 次
for j in range(i + 1, len(arr)): # 内层 n 次
if arr[i] == arr[j]:
return True
return False # O(n²)O(log n) — 对数时间：每次砍掉一半，增长极慢
javascript
// JavaScript
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1; // 砍掉左半边
else right = mid - 1; // 砍掉右半边
}
return -1; // O(log n)，每次排除一半
}python
# Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # 整除！
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1 # 砍掉左半边
else:
right = mid - 1 # 砍掉右半边
return -1 # O(log n)如何快速判断时间复杂度：
看代码结构：
没有循环 → O(1)
一层 for 循环（遍历整个数组） → O(n)
两层嵌套 for 循环 → O(n²)
每次问题规模减半（二分） → O(log n)
一层循环 × 内部二分 → O(n log n)
递归（每层分两个子问题） → 看情况，可能 O(2^n)💡 面试口诀：一层循环 O(n)，两层循环 O(n²)，减半搜索 O(log n)，排序一般 O(n log n)。90% 的算法题用这四个就够了。
2.2 什么是空间复杂度：代码吃多少内存
空间复杂度描述的是算法额外使用的内存随输入规模 n 的增长趋势。注意是"额外"——输入本身占的空间不算。
O(1) — 常数空间：只用了几个变量
javascript
// JavaScript
function findMax(arr) {
let max = arr[0]; // 只用了 1 个额外变量
for (const num of arr) {
if (num > max) max = num;
}
return max; // 空间 O(1)
}python
# Python
def find_max(arr):
max_val = arr[0] # 只用了 1 个额外变量
for num in arr:
if num > max_val:
max_val = num
return max_val # 空间 O(1)O(n) — 线性空间：新建了一个和输入一样大的数组
javascript
// JavaScript
function doubleArray(arr) {
const result = []; // 新建了一个数组
for (const num of arr) {
result.push(num * 2); // result 和 arr 一样长
}
return result; // 空间 O(n)
}
// 哈希表也是 O(n)
function countChars(s) {
const map = new Map(); // 最多存 n 个键值对
for (const c of s) {
map.set(c, (map.get(c) || 0) + 1);
}
return map; // 空间 O(n)
}python
# Python
def double_array(arr):
result = [] # 新建了一个列表
for num in arr:
result.append(num * 2) # result 和 arr 一样长
return result # 空间 O(n)
# 哈希表也是 O(n)
def count_chars(s):
counter = {} # 最多存 n 个键值对
for c in s:
counter[c] = counter.get(c, 0) + 1
return counter # 空间 O(n)O(n²) — 平方空间：二维数组
javascript
// JavaScript — 创建 n×n 的矩阵
function createMatrix(n) {
const matrix = [];
for (let i = 0; i < n; i++) {
matrix.push(new Array(n).fill(0)); // n 行 × n 列
}
return matrix; // 空间 O(n²)
}python
# Python — 创建 n×n 的矩阵
def create_matrix(n):
matrix = [[0] * n for _ in range(n)] # n 行 × n 列
return matrix # 空间 O(n²)
# ⚠️ 常见陷阱！不要这样写：
# matrix = [[0] * n] * n # 所有行指向同一个列表！改一个全变💡 递归的隐藏空间开销：递归调用会占用调用栈空间。递归深度为 d，空间复杂度就至少是 O(d)。比如二叉树遍历，递归深度最大为树高 h，空间 O(h)。
空间复杂度速查：
| 场景 | 空间复杂度 | 例子 |
|---|---|---|
| 只用几个变量 | O(1) | 双指针、原地交换 |
| 新建哈希表/数组 | O(n) | 计数、去重、缓存 |
| 新建二维数组 | O(n²) | DP 表、矩阵 |
| 递归（深度 n） | O(n) | 链表递归、深度搜索 |
| 递归（深度 log n） | O(log n) | 二分查找递归版 |
2.3 常见复杂度对比：O(1) 到 O(n!) 的直觉建立
光说 O(n) 比 O(n²) 快，到底快多少？看数字最直观：
当 n 增长时，各复杂度的执行次数：
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2^n) | O(n!) |
|---|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1,024 | 3,628,800 |
| 100 | 1 | 7 | 100 | 664 | 10,000 | 💀 | 💀 |
| 1,000 | 1 | 10 | 1,000 | 9,966 | 1,000,000 | 💀 | 💀 |
| 10,000 | 1 | 13 | 10,000 | 132,877 | 100,000,000 | 💀 | 💀 |
| 100,000 | 1 | 17 | 100,000 | 1,660,964 | 💀 | 💀 | 💀 |
💀 = 数字大到宇宙毁灭都算不完
增长速度的直觉：
O(1) → 常数，永远一步搞定
O(log n) → 极慢增长，n 从 1000 到 100万 只多算 10 次
O(n) → 线性增长，n 翻倍计算量翻倍，可以接受
O(n log n) → 比线性稍多，排序算法的标准复杂度
O(n²) → n = 10000 就要算 1 亿次，开始吃力
O(2^n) → n = 30 就要算 10 亿次，只能处理小规模
O(n!) → n = 20 就到极限了，全排列级别算法题的复杂度选择指南——根据数据规模倒推：
LeetCode 的时间限制通常是 1-2 秒
现代计算机每秒大约执行 10^8（1 亿）次简单操作
所以：
n ≤ 10 → O(n!) 或 O(2^n) 都行（暴力搜索、全排列）
n ≤ 20 → O(2^n)（回溯、状态压缩 DP）
n ≤ 500 → O(n³)（三层循环，Floyd 算法）
n ≤ 5,000 → O(n²)（双层循环，简单 DP）
n ≤ 100,000 → O(n log n)（排序、二分 + 遍历）
n ≤ 1,000,000 → O(n)（一次遍历、哈希表）
n > 1,000,000 → O(log n) 或 O(1)（二分查找、数学公式）💡 实战技巧：先看题目的数据范围（"1 ≤ n ≤ 10⁵"），再倒推需要什么复杂度的算法。看到 n ≤ 10⁵，就知道需要 O(n log n) 或更好的解法——O(n²) 肯定超时。这个思路能帮你快速排除错误方向。
2.4 实战：用代码计时验证复杂度理论
理论讲完了，跑一段代码亲自感受一下不同复杂度之间的差距。
JS 版本——计时对比 O(n) vs O(n²)：
javascript
// JavaScript — 在浏览器或 Node.js 中运行
function testOn(n) {
const arr = Array.from({ length: n }, (_, i) => i);
const start = performance.now();
// O(n)：遍历求和
let sum = 0;
for (const num of arr) {
sum += num;
}
const time = (performance.now() - start).toFixed(2);
console.log(`O(n) | n=${n.toLocaleString()} | ${time}ms`);
}
function testOn2(n) {
const arr = Array.from({ length: n }, (_, i) => i);
const start = performance.now();
// O(n²)：双层循环
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
count++;
}
}
const time = (performance.now() - start).toFixed(2);
console.log(`O(n²) | n=${n.toLocaleString()} | ${time}ms`);
}
// 跑一跑看看
testOn(10000); // 几乎瞬间
testOn(100000); // 还是很快
testOn2(10000); // 开始有感觉了
testOn2(100000); // 明显变慢...Python 版本——同样的对比：
python
# Python — 运行 python3 执行
import time
def test_on(n):
arr = list(range(n))
start = time.time()
# O(n)：遍历求和
total = 0
for num in arr:
total += num
elapsed = (time.time() - start) * 1000
print(f"O(n) | n={n:>10,} | {elapsed:.2f}ms")
def test_on2(n):
arr = list(range(n))
start = time.time()
# O(n²)：双层循环
count = 0
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
count += 1
elapsed = (time.time() - start) * 1000
print(f"O(n²) | n={n:>10,} | {elapsed:.2f}ms")
# 跑一跑看看
test_on(10000) # 约 1ms
test_on(100000) # 约 10ms（翻 10 倍，时间也翻 10 倍 → 线性）
test_on2(10000) # 约 500ms
test_on2(100000) # 约 50000ms（翻 10 倍，时间翻 100 倍 → 平方）运行结果的直觉（大致参考）：
O(n) 遍历：
n = 10,000 → ~1ms ✅ 秒出
n = 100,000 → ~10ms ✅ 秒出
n = 1,000,000 → ~100ms ✅ 还行
O(n²) 双层循环：
n = 10,000 → ~500ms 😰 半秒
n = 100,000 → ~50s 💀 等不了
n = 1,000,000 → 别试了 💀💀💀
结论：
→ n = 10 万的时候，O(n) 只要 10ms，O(n²) 要 50 秒
→ 差距是 5000 倍！
→ 这就是为什么算法优化如此重要💡 动手跑一次比读十遍理论有用。把上面的代码复制到浏览器控制台或 Python 里跑一下，亲自感受 O(n) 和 O(n²) 的差距。当你看到 n=100000 的 O(n²) 卡了 50 秒，以后写嵌套循环时就会本能地想"有没有更快的方法"。
第 2 章核心知识回顾：
| 概念 | 一句话解释 |
|---|---|
| 时间复杂度 | 执行次数随 n 增长的趋势，不是实际秒数 |
| 空间复杂度 | 额外内存随 n 增长的趋势，输入本身不算 |
| O(1) | 常数，和输入大小无关 |
| O(log n) | 每次减半，增长极慢（二分查找） |
| O(n) | 线性，一层循环 |
| O(n log n) | 排序的标准复杂度（归并/快排） |
| O(n²) | 两层嵌套循环，n > 1 万就危险 |
| 倒推法 | 看数据范围 → 倒推所需复杂度 → 选择算法 |
3. 数组与哈希表：最常用的两把刀
从这一章开始，我们正式进入算法世界。数组和哈希表是算法题里出现频率最高的两种数据结构——LeetCode 前 100 热题中，超过一半都和它们有关。
这一章会介绍三个核心技巧：双指针、滑动窗口、哈希表。掌握它们，你就能解决大量"Easy"和"Medium"题。
3.1 数组遍历与双指针技巧
"双指针"是算法题里性价比最高的技巧——思路简单，适用面极广，很多 O(n²) 的暴力解法用双指针都能优化到 O(n)。
什么是双指针：
双指针的两种模式：
① 对撞指针（左右指针）
═══════════════════════════════════
left → ← right
[1, 2, 3, 4, 5, 6, 7, 8, 9]
从两端向中间走，常用于：有序数组、回文判断、盛水容器
② 快慢指针
═══════════════════════════════════
slow →
fast ──────→
[1, 2, 2, 3, 3, 4, 5]
两个指针同向移动但速度不同，常用于：去重、链表找环例题：有序数组两数之和（LeetCode 167）
给定一个有序数组，找到两个数使它们的和等于目标值。
javascript
// JavaScript — 对撞指针
function twoSum(numbers, target) {
let left = 0, right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1]; // 题目要求 1-indexed
} else if (sum < target) {
left++; // 和太小，左指针右移让和变大
} else {
right--; // 和太大，右指针左移让和变小
}
}
return [-1, -1]; // 时间 O(n)，空间 O(1)
}python
# Python — 对撞指针
def two_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 题目要求 1-indexed
elif s < target:
left += 1 # 和太小，左指针右移
else:
right -= 1 # 和太大，右指针左移
return [-1, -1] # 时间 O(n)，空间 O(1)💡 为什么双指针有效？ 因为数组是有序的。
sum < target时，只能让较小的数变大（左指针右移）；sum > target时，只能让较大的数变小（右指针左移）。每一步都能排除掉一个不可能的候选。
例题：原地移除元素（LeetCode 27）
javascript
// JavaScript — 快慢指针
function removeElement(nums, val) {
let slow = 0; // slow 指向下一个要写入的位置
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== val) { // fast 找到不等于 val 的元素
nums[slow] = nums[fast]; // 写到 slow 的位置
slow++;
}
}
return slow; // slow 就是新数组的长度
}python
# Python — 快慢指针
def remove_element(nums, val):
slow = 0 # slow 指向下一个要写入的位置
for fast in range(len(nums)):
if nums[fast] != val: # fast 找到不等于 val 的元素
nums[slow] = nums[fast] # 写到 slow 的位置
slow += 1
return slow # slow 就是新数组的长度双指针模板总结：
对撞指针模板：
left = 0, right = n - 1
while left < right:
根据条件移动 left 或 right
快慢指针模板：
slow = 0
for fast in range(n):
if 满足条件:
处理 nums[slow]
slow += 13.2 滑动窗口：子数组/子串问题的万能模板
滑动窗口是双指针的升级版——维护一个可以伸缩的"窗口"，在数组上滑动。遇到"连续子数组""子串"相关问题，优先想滑动窗口。
滑动窗口的核心思路：
固定 left，向右扩展 right（扩大窗口）
当窗口满足/不满足条件时，收缩 left（缩小窗口）
在这个过程中记录答案
[1, 3, 2, 6, 4, 1, 8, 5]
↑ ↑
left right
←――窗口――→
right 一直向右走（扩大窗口）
当窗口满足条件时，left 向右走（缩小窗口、尝试更优解）滑动窗口模板：
javascript
// JavaScript 模板
function slidingWindow(arr) {
let left = 0;
let result = /* 初始值 */;
let windowState = /* 窗口状态（和/计数/集合等）*/;
for (let right = 0; right < arr.length; right++) {
// 1. 右边元素进入窗口，更新窗口状态
windowState = /* 更新 */;
// 2. 当窗口不满足条件时，收缩左边界
while (/* 窗口需要收缩 */) {
// 左边元素离开窗口
windowState = /* 更新 */;
left++;
}
// 3. 更新结果
result = /* 比较/记录最优解 */;
}
return result;
}python
# Python 模板
def sliding_window(arr):
left = 0
result = # 初始值
window_state = # 窗口状态
for right in range(len(arr)):
# 1. 右边元素进入窗口
window_state = # 更新
# 2. 收缩左边界
while # 窗口需要收缩:
window_state = # 更新
left += 1
# 3. 更新结果
result = # 比较/记录最优解
return result例题：长度最小的子数组（LeetCode 209）
找一个最短的连续子数组，使其元素之和 ≥ target。
javascript
// JavaScript
function minSubArrayLen(target, nums) {
let left = 0, sum = 0;
let minLen = Infinity; // 初始为无穷大
for (let right = 0; right < nums.length; right++) {
sum += nums[right]; // 右边元素进窗口
while (sum >= target) { // 满足条件，尝试缩小
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left]; // 左边元素出窗口
left++;
}
}
return minLen === Infinity ? 0 : minLen; // O(n)
}python
# Python
def min_sub_array_len(target, nums):
left = 0
total = 0
min_len = float('inf') # 初始为无穷大
for right in range(len(nums)):
total += nums[right] # 右边元素进窗口
while total >= target: # 满足条件，尝试缩小
min_len = min(min_len, right - left + 1)
total -= nums[left] # 左边元素出窗口
left += 1
return 0 if min_len == float('inf') else min_len # O(n)💡 滑动窗口为什么是 O(n)？ 虽然有两层循环（for + while），但 left 和 right 都只会向右移动，每个元素最多进窗口一次、出窗口一次，总操作 2n 次 = O(n)。
何时用滑动窗口？
| 关键词 | 例题 |
|---|---|
| "最长/最短子数组" | 长度最小的子数组 |
| "最长/最短子串" | 最长无重复字符子串 |
| "连续" | 连续子数组最大和 |
| "包含某些字符的子串" | 最小覆盖子串 |
3.3 哈希表（Map/Set）：空间换时间
哈希表的核心理念：用额外的空间存信息，换取查找速度从 O(n) 降到 O(1)。
没有哈希表：
"数组里有没有 5？" → 从头遍历到尾 → O(n)
有了哈希表：
"数组里有没有 5？" → 直接查表 → O(1)JS 和 Python 的哈希表对照：
| 操作 | JS Map | Python dict | JS Set | Python set |
|---|---|---|---|---|
| 创建 | new Map() | {} 或 dict() | new Set() | set() |
| 添加 | .set(k, v) | d[k] = v | .add(v) | .add(v) |
| 查找 | .get(k) | d[k] / d.get(k) | .has(v) | v in s |
| 删除 | .delete(k) | del d[k] | .delete(v) | s.remove(v) |
| 大小 | .size | len(d) | .size | len(s) |
| 遍历 | for [k,v] of map | for k,v in d.items() | for v of set | for v in s |
哈希表最典型的用法——计数：
javascript
// JavaScript — 统计字符出现次数
function charCount(s) {
const map = new Map();
for (const c of s) {
map.set(c, (map.get(c) || 0) + 1);
}
return map;
}
// charCount("aabbc") → Map { 'a' => 2, 'b' => 2, 'c' => 1 }python
# Python — 统计字符出现次数
def char_count(s):
counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1
return counter
# char_count("aabbc") → {'a': 2, 'b': 2, 'c': 1}
# 更 Pythonic 的方式：
from collections import Counter
counter = Counter("aabbc") # 一行搞定！Counter({'a': 2, 'b': 2, 'c': 1})💡 Python 的
Counter是算法题的神器——一行完成频次统计，还支持most_common(k)取出前 k 个高频元素。JS 没有对应的内置工具。
Set 的典型用法——去重与快速查存在性：
javascript
// JavaScript — 数组去重
const unique = [...new Set([1, 2, 2, 3, 3, 3])];
// [1, 2, 3]
// 快速判断是否存在
const seen = new Set();
for (const num of arr) {
if (seen.has(num)) {
console.log("发现重复：", num);
}
seen.add(num);
}python
# Python — 列表去重
unique = list(set([1, 2, 2, 3, 3, 3]))
# [1, 2, 3]（注意：set 不保证顺序）
# 快速判断是否存在
seen = set()
for num in arr:
if num in seen: # O(1) 查找！
print("发现重复：", num)
seen.add(num)哈希表解题公式：
看到这些关键词，想到哈希表：
"找出两个数满足某个条件" → 遍历时查表（两数之和）
"统计频次" → Counter / Map 计数
"去重" → Set
"是否存在" → Set.has / in set
"分组" → Map<key, list>3.4 经典题实战：两数之和、三数之和、最长无重复子串
把前面学的双指针、滑动窗口、哈希表组合起来，解三道高频题。
题 1：两数之和（LeetCode 1）— 哈希表解法
给定数组和目标值，找两个数的下标使其和等于目标值。
javascript
// JavaScript — 哈希表 O(n)
function twoSum(nums, target) {
const map = new Map(); // 存储：值 → 下标
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]; // 需要的另一个数
if (map.has(complement)) {
return [map.get(complement), i]; // 找到了！
}
map.set(nums[i], i); // 没找到，存入当前元素
}
return [];
}
// twoSum([2, 7, 11, 15], 9) → [0, 1]python
# Python — 哈希表 O(n)
def two_sum(nums, target):
seen = {} # 存储：值 → 下标
for i, num in enumerate(nums):
complement = target - num # 需要的另一个数
if complement in seen:
return [seen[complement], i] # 找到了！
seen[num] = i # 没找到，存入当前元素
return []
# two_sum([2, 7, 11, 15], 9) → [0, 1]💡 两数之和是 LeetCode 第 1 题，也是哈希表的经典入门题。核心思路：遍历的同时查"我需要的那个数是否已经出现过"。暴力 O(n²) → 哈希表 O(n)。
题 2：最长无重复子串（LeetCode 3）— 滑动窗口 + Set
javascript
// JavaScript — 滑动窗口
function lengthOfLongestSubstring(s) {
const set = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) { // 有重复？收缩左边界
set.delete(s[left]);
left++;
}
set.add(s[right]); // 右边字符进窗口
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// "abcabcbb" → 3（"abc"）python
# Python — 滑动窗口
def length_of_longest_substring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set: # 有重复？收缩左边界
char_set.remove(s[left])
left += 1
char_set.add(s[right]) # 右边字符进窗口
max_len = max(max_len, right - left + 1)
return max_len
# "abcabcbb" → 3（"abc"）题 3：三数之和（LeetCode 15）— 排序 + 对撞指针
javascript
// JavaScript — 排序 + 双指针 O(n²)
function threeSum(nums) {
nums.sort((a, b) => a - b); // 先排序
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue; // 跳过重复
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left+1]) left++; // 跳过重复
while (left < right && nums[right] === nums[right-1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}python
# Python — 排序 + 双指针 O(n²)
def three_sum(nums):
nums.sort() # 先排序
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # 跳过重复
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: # 跳过重复
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result💡 三数之和的核心思路：固定一个数，剩下两个数用双指针找。排序是为了让双指针能工作（有序才能判断大小）。去重是难点——跳过重复元素避免重复三元组。
第 3 章核心知识回顾：
| 技巧 | 适用场景 | 时间复杂度 |
|---|---|---|
| 双指针（对撞） | 有序数组找目标和、回文判断 | O(n) |
| 双指针（快慢） | 原地操作、去重、链表找环 | O(n) |
| 滑动窗口 | 连续子数组/子串的最长/最短/包含问题 | O(n) |
| 哈希表（Map） | 两数之和、频次统计、分组 | O(n) |
| 哈希表（Set） | 去重、判断存在性、无重复子串 | O(n) |
| 排序 + 双指针 | 三数之和、有序数组问题 | O(n log n) |
4. 字符串处理：从 API 到算法
JS 开发者每天都在处理字符串——拼接、查找、替换。但算法中的字符串问题思维完全不同：你需要把字符串看成字符数组，用双指针、哈希表、动态规划等技巧来处理。
这一章覆盖三类高频字符串问题：回文、变位词（字符频次）、子串匹配。
4.1 字符串基础操作对照：JS 方法 vs Python 方法
第 1 章已经对照过基础字符串操作，这里补充几个算法题中特别常用的操作。
字符串 ↔ 数组/列表转换（算法题超高频）：
javascript
// JavaScript
const s = "hello";
const arr = s.split(""); // ["h", "e", "l", "l", "o"]
const back = arr.join(""); // "hello"
// 遍历字符
for (const c of s) {
console.log(c);
}
// 字符编码
"a".charCodeAt(0); // 97
String.fromCharCode(97); // "a"python
# Python
s = "hello"
arr = list(s) # ['h', 'e', 'l', 'l', 'o']
back = "".join(arr) # "hello"
# 遍历字符
for c in s:
print(c)
# 字符编码
ord("a") # 97
chr(97) # "a"💡 为什么要转成数组？ 因为 JS 和 Python 的字符串都是不可变的。要"修改"字符串（如翻转部分字符），必须先转数组 → 操作 → 再拼回来。
算法中常用的字符串技巧：
javascript
// JavaScript
// 判断是否为字母/数字
const isAlphaNum = (c) => /[a-zA-Z0-9]/.test(c);
// 字符串重复
"ab".repeat(3); // "ababab"
// 字符串比较
"abc" === "abc"; // true
"abc" < "abd"; // true（字典序）python
# Python
# 判断是否为字母/数字
c.isalnum() # True if 字母或数字
c.isalpha() # True if 纯字母
c.isdigit() # True if 纯数字
# 字符串重复
"ab" * 3 # "ababab"
# 字符串比较
"abc" == "abc" # True
"abc" < "abd" # True（字典序，和 JS 一样）算法题高频操作速查：
| 操作 | JavaScript | Python |
|---|---|---|
| 字符串→数组 | s.split("") | list(s) |
| 数组→字符串 | arr.join("") | "".join(arr) |
| 字符编码 | s.charCodeAt(0) | ord(s) |
| 编码→字符 | String.fromCharCode(n) | chr(n) |
| 是否字母数字 | /[a-zA-Z0-9]/.test(c) | c.isalnum() |
| 翻转字符串 | s.split("").reverse().join("") | s[::-1] |
| 子串提取 | s.substring(i, j) | s[i:j] |
4.2 回文判断与回文子串
回文就是正着读和反着读一样的字符串——"aba"、"abba"、"racecar"。回文问题在算法题中非常高频。
基础：判断一个字符串是否回文
javascript
// JavaScript — 方法 1：翻转对比
function isPalindrome(s) {
return s === s.split("").reverse().join("");
}
// 方法 2：双指针（更优，O(1) 空间）
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}python
# Python — 方法 1：切片翻转
def is_palindrome(s):
return s == s[::-1] # Python 一行搞定！
# 方法 2：双指针
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True💡 Python 的
s[::-1]判回文简洁到极致，但面试时面试官更想看你写双指针版本——因为双指针能处理更复杂的变体（比如"忽略大小写和非字母字符的回文"）。
进阶：验证回文串 II（LeetCode 680）
最多可以删除一个字符，判断是否能构成回文。
javascript
// JavaScript
function validPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
// 尝试跳过左边或右边的一个字符
return isPalin(s, left + 1, right) || isPalin(s, left, right - 1);
}
left++;
right--;
}
return true;
}
function isPalin(s, left, right) {
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}python
# Python
def valid_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# 尝试跳过左边或右边的一个字符
skip_left = s[left+1:right+1]
skip_right = s[left:right]
return skip_left == skip_left[::-1] or skip_right == skip_right[::-1]
left += 1
right -= 1
return True最长回文子串的核心算法——中心扩展法：
中心扩展的思路：
以每个字符为中心，向两边扩展，找到最长的回文
对于 "babad"：
以 b 为中心扩展 → "b"（长度 1）
以 a 为中心扩展 → "bab"（长度 3）✅
以 b 为中心扩展 → "aba"（长度 3）
以 a 为中心扩展 → "a"（长度 1）
以 d 为中心扩展 → "d"（长度 1）
注意：回文中心可能是 1 个字符（"aba"）或 2 个字符（"abba"）4.3 字符频次统计与变位词问题
"变位词"（Anagram）是指由相同字母重新排列组成的单词——"listen" 和 "silent"、"eat" 和 "tea"。判断两个字符串是否是变位词，本质就是看两者的字符频次是否完全相同。
三种计数方式：
javascript
// JavaScript
// 方式 1：Map 手动计数
function charCount(s) {
const map = {};
for (const c of s) {
map[c] = (map[c] || 0) + 1;
}
return map;
}
// 方式 2：排序后比较（简单但稍慢）
function isAnagram(s, t) {
return s.split("").sort().join("") === t.split("").sort().join("");
}
// O(n log n) 排序
// 方式 3：26 位数组计数（纯小写字母场景）
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++; // s 的字符 +1
count[t.charCodeAt(i) - 97]--; // t 的字符 -1
}
return count.every(c => c === 0); // 全部为 0 → 变位词
}python
# Python
# 方式 1：Counter 一行搞定
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t) # 直接比较 Counter 对象！
# 方式 2：排序后比较
def is_anagram(s, t):
return sorted(s) == sorted(t) # sorted 返回列表，直接比较
# 方式 3：26 位数组计数
def is_anagram(s, t):
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1 # s 的字符 +1
count[ord(t[i]) - ord('a')] -= 1 # t 的字符 -1
return all(c == 0 for c in count) # 全部为 0 → 变位词💡 Python 的
Counter(s) == Counter(t)简直是作弊级别的简洁。JS 没有内置的 Counter，需要手动用 Map 或数组计数。实际 LeetCode 做题时，Python 一行解法的优势非常明显。
变位词分组（LeetCode 49）：
把一组字符串按变位词分组——["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"], ["tan","nat"], ["bat"]]
javascript
// JavaScript — 排序后的字符串作为 key
function groupAnagrams(strs) {
const map = new Map();
for (const s of strs) {
const key = s.split("").sort().join(""); // "eat" → "aet"
if (!map.has(key)) map.set(key, []);
map.get(key).push(s);
}
return [...map.values()];
}python
# Python — 排序后的字符串作为 key
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list) # 默认值为空列表
for s in strs:
key = "".join(sorted(s)) # "eat" → "aet"
groups[key].append(s)
return list(groups.values())💡
defaultdict(list)是 Python 的好东西——不需要判断 key 是否存在就能直接 append。JS 需要if (!map.has(key)) map.set(key, [])这样的判断。
4.4 经典题实战：有效的字母异位词、最长回文子串
题 1：有效的字母异位词（LeetCode 242）
4.3 已经讲了多种解法，这里补充一个最优的 O(n) 解法——单数组计数：
javascript
// JavaScript — 一个数组搞定
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every(c => c === 0);
}
// 时间 O(n)，空间 O(1)（固定 26 位）python
# Python — 最简写法
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
# 时间 O(n)，空间 O(1)（最多 26 个字母）题 2：最长回文子串（LeetCode 5）— 中心扩展法
javascript
// JavaScript — 中心扩展
function longestPalindrome(s) {
let start = 0, maxLen = 1;
function expand(left, right) {
// 从中心向两边扩展，返回最长回文的起止位置
while (left >= 0 && right < s.length && s[left] === s[right]) {
if (right - left + 1 > maxLen) {
start = left;
maxLen = right - left + 1;
}
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // 奇数长度回文（以 i 为中心）
expand(i, i + 1); // 偶数长度回文（以 i 和 i+1 为中心）
}
return s.substring(start, start + maxLen);
}
// 时间 O(n²)，空间 O(1)python
# Python — 中心扩展
def longest_palindrome(s):
start, max_len = 0, 1
def expand(left, right):
nonlocal start, max_len # 修改外层变量需要 nonlocal
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > max_len:
start = left
max_len = right - left + 1
left -= 1
right += 1
for i in range(len(s)):
expand(i, i) # 奇数长度回文
expand(i, i + 1) # 偶数长度回文
return s[start:start + max_len]
# 时间 O(n²)，空间 O(1)💡 中心扩展法的关键：每个位置作为中心尝试两次——一次奇数长度（单字符中心），一次偶数长度（双字符中心）。总共 2n 个中心，每个最多扩展 n 步，所以是 O(n²)。
💡 Python 的
nonlocal：嵌套函数要修改外层函数的变量，需要声明nonlocal。这和 JS 的闭包自动捕获不同——JS 不需要额外声明，Python 需要。
第 4 章核心知识回顾：
| 题型 | 核心技巧 | 复杂度 |
|---|---|---|
| 判断回文 | 双指针 / s[::-1] | O(n) |
| 验证回文 II | 双指针 + 跳过一个字符再判断 | O(n) |
| 最长回文子串 | 中心扩展法 | O(n²) |
| 判断变位词 | Counter / 排序 / 26位数组 | O(n) |
| 变位词分组 | 排序后的字符串作为哈希 key | O(n·k log k) |
| 字符串修改 | 转数组→操作→join 拼回 | — |
5. 栈与队列：后进先出与先进先出
栈和队列是两种最基础的数据结构——JS 开发者其实每天都在用它们，只是没意识到：浏览器的前进后退是栈，事件循环的任务队列是队列。
算法题中，栈和队列的出题频率很高，而且题目模式非常固定——掌握几个模板就能覆盖大部分场景。
5.1 栈的原理与 JS/Python 实现
栈的核心规则：后进先出（LIFO）——最后放进去的元素最先被取出来。
栈的操作可视化：
push(1) push(2) push(3) pop() pop()
│ │ │ │ │ 3 │ │ │ │ │
│ │ │ 2 │ │ 2 │ │ 2 │ │ │
│ 1 │ │ 1 │ │ 1 │ │ 1 │ │ 1 │
└───┘ └───┘ └───┘ └───┘ └───┘
弹出 3 弹出 2JS 和 Python 都用数组/列表直接当栈用：
javascript
// JavaScript — 数组天然就是栈
const stack = [];
stack.push(1); // 入栈 → [1]
stack.push(2); // 入栈 → [1, 2]
stack.push(3); // 入栈 → [1, 2, 3]
stack[stack.length - 1]; // 3（查看栈顶，不弹出）
stack.pop(); // 3（弹出栈顶）→ [1, 2]
stack.length; // 2（栈的大小）
stack.length === 0; // false（是否为空）python
# Python — 列表天然就是栈
stack = []
stack.append(1) # 入栈 → [1]
stack.append(2) # 入栈 → [1, 2]
stack.append(3) # 入栈 → [1, 2, 3]
stack[-1] # 3（查看栈顶，负索引！）
stack.pop() # 3（弹出栈顶）→ [1, 2]
len(stack) # 2（栈的大小）
not stack # False（Pythonic 判空方式）栈操作对照表：
| 操作 | JavaScript | Python |
|---|---|---|
| 入栈 | stack.push(x) | stack.append(x) |
| 出栈 | stack.pop() | stack.pop() |
| 查看栈顶 | stack[stack.length - 1] | stack[-1] |
| 判空 | stack.length === 0 | not stack 或 len(stack) == 0 |
| 大小 | stack.length | len(stack) |
💡 什么时候想到用栈？ 看到这些关键词："匹配"（括号匹配）、"最近的"（最近的更大元素）、"撤销"（编辑器 undo）、"嵌套"（表达式求值）。本质上，凡是需要"最后处理的先解决"的场景，都是栈。
5.2 经典栈问题：括号匹配、最小栈、每日温度
题 1：有效的括号（LeetCode 20）
给定一个只包含 ()、{}、[] 的字符串，判断是否有效。
javascript
// JavaScript
function isValid(s) {
const stack = [];
const map = { ')': '(', '}': '{', ']': '[' };
for (const c of s) {
if (c in map) { // 是右括号？
if (stack.pop() !== map[c]) return false; // 栈顶不匹配
} else {
stack.push(c); // 左括号入栈
}
}
return stack.length === 0; // 栈空 = 全部匹配
}
// isValid("({[]})") → true
// isValid("([)]") → falsepython
# Python
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for c in s:
if c in mapping: # 是右括号？
if not stack or stack.pop() != mapping[c]:
return False # 栈空或不匹配
else:
stack.append(c) # 左括号入栈
return not stack # 栈空 = 全部匹配💡 括号匹配是栈的"Hello World"——遇到左括号入栈，遇到右括号检查栈顶是否匹配。最后栈空说明全部匹配。
题 2：每日温度（LeetCode 739）— 单调栈
给定每日温度列表，返回对于每一天需要等几天才能遇到更高温度。
输入：[73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]
73 → 第二天 74 > 73，等 1 天
75 → 第六天 76 > 75，等 4 天
73 → 后面没有更高的，等 0 天javascript
// JavaScript — 单调递减栈
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const result = new Array(n).fill(0);
const stack = []; // 存下标，不存值！
for (let i = 0; i < n; i++) {
// 当前温度比栈顶温度高 → 栈顶找到了更高温度
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const prevIndex = stack.pop();
result[prevIndex] = i - prevIndex; // 等了几天
}
stack.push(i); // 当前下标入栈
}
return result;
}python
# Python — 单调递减栈
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # 存下标
for i in range(n):
# 当前温度比栈顶温度高 → 栈顶找到了更高温度
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
result[prev_index] = i - prev_index # 等了几天
stack.append(i) # 当前下标入栈
return result💡 单调栈的核心思想：维护一个单调递减的栈。遍历时，如果当前元素比栈顶大，说明栈顶找到了"下一个更大元素"。单调栈是 O(n) 的——每个元素最多入栈一次、出栈一次。
单调栈适用场景：
| 题目特征 | 例题 |
|---|---|
| "下一个更大/更小元素" | 每日温度、下一个更大元素 |
| "左/右边第一个更大/更小" | 柱状图中最大矩形 |
| "连续递增/递减" | 股票价格跨度 |
5.3 队列与双端队列
队列的核心规则：先进先出（FIFO）——最先放进去的元素最先被取出来。想象排队买奶茶。
队列的操作可视化：
enqueue(1) enqueue(2) enqueue(3) dequeue()
┌─────────────────┐ 取出 1
│ 1 │ 2 │ 3 │ │ ←──────
└─────────────────┘
↑ front ↑ rearJS 和 Python 的队列实现：
javascript
// JavaScript
// ⚠️ 数组的 shift() 是 O(n)，因为要移动所有元素
const queue = [];
queue.push(1); // 入队（末尾） → [1]
queue.push(2); // 入队 → [1, 2]
queue.shift(); // 1（出队，头部）→ [2] ← O(n)！
// 算法题中如果性能敏感，可以用指针模拟
// 但大多数 LeetCode 题用 shift() 就够了python
# Python — 用 deque（推荐！O(1) 出队）
from collections import deque
queue = deque()
queue.append(1) # 入队（右端） → deque([1])
queue.append(2) # 入队 → deque([1, 2])
queue.popleft() # 1（出队，左端）→ deque([2]) ← O(1)！💡 Python 的
deque是算法题必备工具。列表的pop(0)是 O(n)，而deque.popleft()是 O(1)。BFS 算法一定要用 deque，否则大数据量会超时。
双端队列（Deque） — 两端都能进出：
javascript
// JavaScript — 没有内置 Deque，用数组模拟
const deque = [];
deque.push(1); // 右端入队
deque.unshift(0); // 左端入队 → [0, 1]
deque.pop(); // 右端出队 → 1
deque.shift(); // 左端出队 → 0python
# Python — deque 天然支持双端操作
from collections import deque
dq = deque()
dq.append(1) # 右端入队
dq.appendleft(0) # 左端入队 → deque([0, 1])
dq.pop() # 右端出队 → 1
dq.popleft() # 左端出队 → 0队列操作对照表：
| 操作 | JS (Array) | Python (deque) | 复杂度 |
|---|---|---|---|
| 右端入队 | arr.push(x) | dq.append(x) | O(1) |
| 左端出队 | arr.shift() | dq.popleft() | ⚠️O(n) / ✅O(1) |
| 左端入队 | arr.unshift(x) | dq.appendleft(x) | ⚠️O(n) / ✅O(1) |
| 右端出队 | arr.pop() | dq.pop() | O(1) |
| 查看头部 | arr[0] | dq[0] | O(1) |
| 判空 | arr.length === 0 | not dq | O(1) |
5.4 经典队列问题：滑动窗口最大值、任务调度
题：滑动窗口最大值（LeetCode 239）— 单调双端队列
给定数组和窗口大小 k，返回每个滑动窗口中的最大值。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
窗口位置： 最大值：
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输出：[3, 3, 5, 5, 6, 7]javascript
// JavaScript — 单调递减双端队列
function maxSlidingWindow(nums, k) {
const deque = []; // 存下标，维护单调递减
const result = [];
for (let i = 0; i < nums.length; i++) {
// 1. 移除超出窗口范围的元素
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 2. 维护单调递减：移除所有比当前值小的元素
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
// 3. 窗口形成后，记录最大值（deque 头部就是最大值的下标）
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}python
# Python — 单调递减双端队列
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # 存下标，维护单调递减
result = []
for i in range(len(nums)):
# 1. 移除超出窗口范围的元素
if dq and dq[0] <= i - k:
dq.popleft()
# 2. 维护单调递减：移除所有比当前值小的元素
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
# 3. 窗口形成后，记录最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result💡 单调双端队列的核心：队列中维护一个递减序列，队头永远是当前窗口的最大值。新元素进来时，把队尾所有比它小的元素都移除（它们不可能再成为最大值了）。时间 O(n)。
第 5 章核心知识回顾：
| 数据结构 | 特性 | 核心操作 | 典型应用 |
|---|---|---|---|
| 栈 | 后进先出（LIFO） | push / pop | 括号匹配、表达式求值、DFS |
| 单调栈 | 栈内保持单调 | 遇到破坏单调性的元素时弹出 | 下一个更大元素、每日温度 |
| 队列 | 先进先出（FIFO） | enqueue / dequeue | BFS、任务调度 |
| 双端队列 | 两端都能操作 | appendleft / popleft | 滑动窗口最大值 |
| Python deque | O(1) 双端操作 | from collections import deque | BFS 必备 |
6. 链表：指针思维的入门
JS 开发者日常几乎不会手写链表——数组够用了。但链表是面试的高频考点，也是理解"指针/引用"的最佳练习场。
链表题的核心不在于"难"，而在于"容易出错"——指针指错了、忘了断链、丢了引用，一个小疏忽就导致死循环或 null 异常。
6.1 为什么需要链表：数组的局限性
数组 vs 链表：
数组（连续内存）：
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ → 随机访问 O(1)，但插入/删除要移动元素 O(n)
└───┴───┴───┴───┴───┘
链表（离散内存）：
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │──→│ 2 │──→│ 3 │──→│ 4 │──→ null
└───┘ └───┘ └───┘ └───┘
→ 插入/删除 O(1)（改指针就行），但随机访问 O(n)| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问（第 k 个） | O(1) | O(n) |
| 头部插入/删除 | O(n) | O(1) |
| 尾部插入 | O(1) | O(n)（无尾指针时） |
| 中间插入/删除 | O(n) | O(1)（已知位置时） |
| 内存 | 连续，缓存友好 | 离散，有额外指针开销 |
6.2 单链表的实现与基本操作
链表节点的定义（第 1 章已经见过）：
javascript
// JavaScript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
// 创建链表：1 → 2 → 3
const head = new ListNode(1, new ListNode(2, new ListNode(3)));python
# Python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表：1 → 2 → 3
head = ListNode(1, ListNode(2, ListNode(3)))遍历链表：
javascript
// JavaScript
function printList(head) {
let curr = head;
while (curr !== null) {
console.log(curr.val);
curr = curr.next; // 移动到下一个节点
}
}python
# Python
def print_list(head):
curr = head
while curr: # Python 中 None 是 falsy
print(curr.val)
curr = curr.next从数组创建链表（刷题辅助函数）：
javascript
// JavaScript
function arrayToList(arr) {
const dummy = new ListNode(0); // 虚拟头节点
let curr = dummy;
for (const val of arr) {
curr.next = new ListNode(val);
curr = curr.next;
}
return dummy.next; // 返回真正的头节点
}
// arrayToList([1,2,3]) → 1 → 2 → 3python
# Python
def array_to_list(arr):
dummy = ListNode(0) # 虚拟头节点
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next # 返回真正的头节点💡 虚拟头节点（Dummy Node） 是链表题的万能技巧——在真正的头节点前加一个哨兵节点，避免处理"头节点为空"的边界情况。返回结果时返回
dummy.next。后面的链表题几乎都会用到它。
6.3 链表核心技巧：快慢指针、虚拟头节点、反转
链表题的三大核心技巧几乎能覆盖所有链表考题：
技巧 1：反转链表 — 链表题的"必杀技"
反转过程：改变每个节点的 next 指针方向
原始：1 → 2 → 3 → null
步骤 1：prev=null, curr=1
null ← 1 2 → 3 → null
步骤 2：prev=1, curr=2
null ← 1 ← 2 3 → null
步骤 3：prev=2, curr=3
null ← 1 ← 2 ← 3
结果：3 → 2 → 1 → nulljavascript
// JavaScript — 迭代反转
function reverseList(head) {
let prev = null, curr = head;
while (curr !== null) {
const next = curr.next; // 先保存下一个节点
curr.next = prev; // 反转指针
prev = curr; // prev 前进
curr = next; // curr 前进
}
return prev; // prev 就是新的头节点
}python
# Python — 迭代反转
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # 先保存下一个节点
curr.next = prev # 反转指针
prev = curr # prev 前进
curr = next_node # curr 前进
return prev # prev 就是新的头节点💡 反转链表三步口诀：①保存 next ②反转指针 ③双指针前进。背下来，闭着眼睛都能写。
技巧 2：快慢指针 — 找中间节点 / 判环
快指针每次走 2 步，慢指针每次走 1 步
当快指针到达末尾时，慢指针刚好在中间
slow → → →
fast → → → → → → → → →
[1, 2, 3, 4, 5]
↑
中间节点javascript
// JavaScript — 找链表中间节点（LeetCode 876）
function middleNode(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next; // 慢指针走 1 步
fast = fast.next.next; // 快指针走 2 步
}
return slow; // slow 就是中间节点
}python
# Python — 找链表中间节点
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 慢指针走 1 步
fast = fast.next.next # 快指针走 2 步
return slow # slow 就是中间节点技巧 3：虚拟头节点 — 统一边界处理
javascript
// 没有虚拟头节点 → 需要单独处理头节点
function removeElements(head, val) {
while (head !== null && head.val === val) { // 处理头节点（烦！）
head = head.next;
}
let curr = head;
while (curr !== null && curr.next !== null) {
if (curr.next.val === val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
// 有虚拟头节点 → 统一处理，简洁很多
function removeElements(head, val) {
const dummy = new ListNode(0, head); // 虚拟头
let curr = dummy;
while (curr.next !== null) {
if (curr.next.val === val) {
curr.next = curr.next.next; // 跳过目标节点
} else {
curr = curr.next;
}
}
return dummy.next;
}6.4 经典题实战：反转链表、合并有序链表、环形链表检测
反转链表已经在 6.3 讲过了，这里重点讲另外两道高频题。
题 1：合并两个有序链表（LeetCode 21）
javascript
// JavaScript — 虚拟头节点 + 逐一比较
function mergeTwoLists(list1, list2) {
const dummy = new ListNode(0);
let curr = dummy;
while (list1 !== null && list2 !== null) {
if (list1.val <= list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
curr.next = list1 || list2; // 拼接剩余部分
return dummy.next;
}python
# Python
def merge_two_lists(list1, list2):
dummy = ListNode(0)
curr = dummy
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 or list2 # 拼接剩余部分
return dummy.next💡
list1 || list2（JS）/list1 or list2（Python）：当一个链表遍历完，另一个还有剩余，直接接上剩余部分即可。
题 2：环形链表检测（LeetCode 141）— 快慢指针
如果链表有环，快指针一定会追上慢指针（像操场跑步）
如果没有环，快指针会先到达 null
1 → 2 → 3 → 4
↑ ↓
6 ← 5 → 有环！fast 和 slow 会相遇javascript
// JavaScript
function hasCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // 相遇 = 有环
}
return false; // fast 到 null = 无环
}python
# Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # 相遇 = 有环
return True
return False # fast 到 None = 无环💡 Python 用
is比较链表节点，而不是==。is比较的是内存地址（同一个对象），==比较的是值。链表判环需要判断"是同一个节点"，所以用is。
第 6 章核心知识回顾：
| 技巧 | 适用场景 | 时间/空间 |
|---|---|---|
| 虚拟头节点 | 所有需要修改链表头部的问题 | 避免边界判断 |
| 反转链表 | 反转整个/部分链表 | O(n) / O(1) |
| 快慢指针 | 找中间节点、判环、找环入口 | O(n) / O(1) |
| 合并链表 | 两个有序链表合并 | O(n+m) / O(1) |
| 链表判环 | 快慢指针是否相遇 | O(n) / O(1) |
7. 递归与回溯：用"套娃"解决问题
递归是算法学习的分水岭——很多人在这里卡住。但递归的核心思想其实很简单：把大问题拆成一样结构的小问题，直到小到可以直接解决。
回溯法是递归的延伸——在所有可能的选择中搜索答案，走不通就"回退"换条路。排列、组合、子集、N 皇后这类"穷举所有可能"的题，都用回溯。
7.1 递归的本质：函数调用自己
递归就像套娃：
factorial(5)
→ 5 × factorial(4)
→ 4 × factorial(3)
→ 3 × factorial(2)
→ 2 × factorial(1)
→ 1（到底了！开始返回）
← 2 × 1 = 2
← 3 × 2 = 6
← 4 × 6 = 24
← 5 × 24 = 120javascript
// JavaScript — 阶乘
function factorial(n) {
if (n <= 1) return 1; // base case：到底了
return n * factorial(n - 1); // 递推：大问题 = n × 小问题
}python
# Python — 阶乘
def factorial(n):
if n <= 1:
return 1 # base case
return n * factorial(n - 1) # 递推7.2 递归三要素：base case、递推关系、返回值
写递归只需要想清楚三件事：
① base case（终止条件）：什么时候不再递归？
② 递推关系：大问题怎么拆成小问题？
③ 返回值：每一层递归返回什么？例：斐波那契数列
javascript
// JavaScript
function fib(n) {
// ① base case
if (n <= 1) return n;
// ② 递推关系：fib(n) = fib(n-1) + fib(n-2)
// ③ 返回值：当前层的计算结果
return fib(n - 1) + fib(n - 2);
}
// ⚠️ 这个版本是 O(2^n)，非常慢！后面动态规划章节会优化python
# Python
def fib(n):
if n <= 1: # ① base case
return n
return fib(n - 1) + fib(n - 2) # ② 递推 + ③ 返回递归思维的训练方法：
写递归时，不要去想"函数怎么一层层展开"
而是假设递归函数已经能正确处理子问题
你只需要思考：
1. 当前层该做什么？
2. 子问题是什么？
3. 什么时候停？
这叫"递归的信仰之跃"——相信子递归能给你正确答案，你只管处理当前层。💡 常见错误：忘了写 base case（导致无限递归和栈溢出）、base case 条件不对（差一错误）、递推关系搞反了。最佳实践：先写 base case，再写递推。
7.3 回溯法模板：排列、组合、子集
回溯法本质就是递归 + 撤销选择。想象你在走迷宫：每个岔路口做一个选择，走不通就退回上一个岔路口换条路。
回溯法的决策树（以子集 [1,2,3] 为例）：
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
每一层做一个决策：选 or 不选当前元素回溯法万能模板：
javascript
// JavaScript — 回溯模板
function backtrack(path, choices) {
// 1. 满足结束条件 → 收集结果
if (满足结束条件) {
result.push([...path]); // ⚠️ 必须拷贝！
return;
}
// 2. 遍历所有选择
for (const choice of choices) {
// 3. 做选择
path.push(choice);
// 4. 递归（进入下一层决策）
backtrack(path, 剩余选择);
// 5. 撤销选择（回溯！）
path.pop();
}
}python
# Python — 回溯模板
def backtrack(path, choices):
# 1. 满足结束条件 → 收集结果
if 满足结束条件:
result.append(path[:]) # ⚠️ 必须拷贝！path[:] 或 list(path)
return
# 2. 遍历所有选择
for choice in choices:
# 3. 做选择
path.append(choice)
# 4. 递归
backtrack(path, 剩余选择)
# 5. 撤销选择
path.pop()💡 为什么要拷贝 path？ 因为 path 是引用类型（数组/列表），如果直接
result.push(path)，后续修改 path 会影响已存入的结果。JS 用[...path]，Python 用path[:]。
子集问题（LeetCode 78）：
给定数组 [1,2,3]，输出所有子集。
javascript
// JavaScript
function subsets(nums) {
const result = [];
function backtrack(start, path) {
result.push([...path]); // 每个节点都是一个子集
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // 选择
backtrack(i + 1, path); // 递归（从 i+1 开始避免重复）
path.pop(); // 撤销
}
}
backtrack(0, []);
return result;
}
// → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]python
# Python
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # 每个节点都是一个子集
for i in range(start, len(nums)):
path.append(nums[i]) # 选择
backtrack(i + 1, path) # 递归
path.pop() # 撤销
backtrack(0, [])
return result排列 vs 组合 vs 子集的区别：
| 类型 | 特点 | 循环起点 | 需要 used 数组？ |
|---|---|---|---|
| 子集 | 不要求用完，顺序无关 | start | 否 |
| 组合 | 选 k 个，顺序无关 | start | 否 |
| 排列 | 全部用完，顺序有关 | 0（每次从头遍历） | 是 |
7.4 经典题实战：全排列、组合总和、N 皇后
题 1：全排列（LeetCode 46）
javascript
// JavaScript — 回溯 + used 数组
function permute(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
function backtrack(path) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 已经用过，跳过
used[i] = true; // 标记使用
path.push(nums[i]);
backtrack(path);
path.pop(); // 撤销
used[i] = false; // 取消标记
}
}
backtrack([]);
return result;
}
// permute([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]python
# Python
def permute(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue # 已经用过，跳过
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result💡 排列和子集的关键区别：子集从
start开始循环（避免重复），排列从0开始但用used数组标记已选元素。
题 2：组合总和（LeetCode 39）
给定数组和目标值，找出所有和为目标值的组合（元素可重复使用）。
javascript
// JavaScript
function combinationSum(candidates, target) {
const result = [];
function backtrack(start, path, remaining) {
if (remaining === 0) {
result.push([...path]);
return;
}
if (remaining < 0) return; // 剪枝：超过目标值
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]);
backtrack(i, path, remaining - candidates[i]); // i 不是 i+1，允许重复
path.pop();
}
}
backtrack(0, [], target);
return result;
}
// combinationSum([2,3,6,7], 7) → [[2,2,3], [7]]python
# Python
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0: # 剪枝
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i 不是 i+1
path.pop()
backtrack(0, [], target)
return result💡
backtrack(i, ...)vsbacktrack(i+1, ...)：传i表示当前元素可以重复选，传i+1表示不能重复。这一个字母的差别决定了"可重复选"还是"不可重复选"。
第 7 章核心知识回顾：
| 概念 | 一句话解释 |
|---|---|
| 递归 | 函数调用自己，大问题拆小问题 |
| base case | 递归终止条件，必须先写 |
| 回溯法 | 递归 + 撤销选择，穷举所有可能 |
| path 拷贝 | 收集结果时必须拷贝 [...path] / path[:] |
| 子集 | 从 start 开始，每个节点都收集 |
| 排列 | 从 0 开始 + used 数组，叶子节点收集 |
| 组合 | 从 start 开始，满足条件时收集 |
| 剪枝 | 提前排除不可能的分支，加速回溯 |
8. 排序算法：不只是 .sort()
JS 的 Array.sort() 和 Python 的 sorted() 用起来很方便，但面试官经常会问"你知道排序底层怎么实现的吗？"手写排序不是为了造轮子，而是理解分治、递归、交换这些算法设计思想。
8.1 基础排序：冒泡、选择、插入
三种 O(n²) 排序，面试不太考但理解思想很重要。以冒泡排序为代表：
冒泡排序 — 每轮把最大的"冒"到末尾：
javascript
// JavaScript
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换
swapped = true;
}
}
if (!swapped) break; // 没有交换说明已排好序，提前退出
}
return arr;
}python
# Python
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # 交换
swapped = True
if not swapped:
break # 提前退出
return arr三种基础排序对比：
| 排序 | 思路 | 时间 | 空间 | 稳定？ |
|---|---|---|---|---|
| 冒泡 | 相邻比较交换，大的冒到后面 | O(n²) | O(1) | ✅ |
| 选择 | 每轮选最小的放到前面 | O(n²) | O(1) | ❌ |
| 插入 | 像打牌——把新牌插入已排好的手牌中 | O(n²) | O(1) | ✅ |
8.2 高效排序：归并排序与快速排序
面试真正考的排序。两者都是 O(n log n)，都用到分治思想。
快速排序 — 选一个基准值，比它小的放左边，大的放右边：
javascript
// JavaScript
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)]; // 选中间元素为基准
const left = arr.filter(x => x < pivot); // 小于基准
const equal = arr.filter(x => x === pivot); // 等于基准
const right = arr.filter(x => x > pivot); // 大于基准
return [...quickSort(left), ...equal, ...quickSort(right)];
}
// ⚠️ 这是好理解的版本，面试时可能要写原地交换版本python
# Python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # 选中间元素为基准
left = [x for x in arr if x < pivot] # 小于基准
equal = [x for x in arr if x == pivot] # 等于基准
right = [x for x in arr if x > pivot] # 大于基准
return quick_sort(left) + equal + quick_sort(right)归并排序 — 先拆成最小单元，再两两合并：
javascript
// JavaScript
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // 递归排左半
const right = mergeSort(arr.slice(mid)); // 递归排右半
return merge(left, right); // 合并两个有序数组
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}python
# Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 递归排左半
right = merge_sort(arr[mid:]) # 递归排右半
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]快排 vs 归并：
| 特性 | 快速排序 | 归并排序 |
|---|---|---|
| 平均时间 | O(n log n) | O(n log n) |
| 最坏时间 | O(n²)（基准选不好） | O(n log n)（稳定） |
| 空间 | O(log n)（原地版） | O(n)（需要额外数组） |
| 稳定性 | ❌ 不稳定 | ✅ 稳定 |
| 适用 | 一般排序（最常用） | 需要稳定排序、链表排序 |
8.3 排序的应用：合并区间、前 K 大元素
很多算法题不直接考排序，但排序是解题的第一步——先排序再用其他技巧。
题：合并区间（LeetCode 56）
javascript
// JavaScript — 先按起点排序，再逐一合并
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]); // 按起点排序
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]); // 有重叠，合并
} else {
merged.push(intervals[i]); // 无重叠，直接加入
}
}
return merged;
}
// merge([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]]python
# Python
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # 按起点排序
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # 有重叠，合并
else:
merged.append([start, end]) # 无重叠，直接加入
return merged💡 排序 + 贪心是区间问题的标准套路：先按起点排序，再逐一判断是否重叠。类似的题还有"无重叠区间""会议室安排"等。
前 K 大元素的常见解法：
方法 1：排序后取最后 k 个 → O(n log n)
方法 2：快速选择（QuickSelect）→ O(n) 平均
方法 3：堆（优先队列） → O(n log k)
算法题中最常用的是 方法 1（简单）和 方法 3（最优）python
# Python — 前 K 大元素最简解法
import heapq
def top_k(nums, k):
return heapq.nlargest(k, nums) # Python 内置，一行搞定
# 或者用排序
def top_k(nums, k):
return sorted(nums, reverse=True)[:k]8.4 JS sort() vs Python sorted()：内置排序的正确使用
算法题中 99% 的时候直接用内置排序。但 JS 的 sort() 有个大坑。
JS 的 sort() 陷阱：
javascript
// ⚠️ 致命陷阱：JS 的 sort() 默认按字符串排序！
[10, 9, 2, 1, 100].sort();
// → [1, 10, 100, 2, 9] ← 完全错误！"10" < "2" 因为 "1" < "2"
// ✅ 正确的数字排序：必须传比较函数
[10, 9, 2, 1, 100].sort((a, b) => a - b);
// → [1, 2, 9, 10, 100] ← 升序
[10, 9, 2, 1, 100].sort((a, b) => b - a);
// → [100, 10, 9, 2, 1] ← 降序Python 的 sorted() 没有这个问题：
python
# Python — 默认就是数字升序，不会出错
sorted([10, 9, 2, 1, 100])
# → [1, 2, 9, 10, 100] ✅
sorted([10, 9, 2, 1, 100], reverse=True)
# → [100, 10, 9, 2, 1] 降序
# 自定义排序规则
intervals = [[1,3], [2,6], [8,10]]
sorted(intervals, key=lambda x: x[0]) # 按第一个元素排序
sorted(intervals, key=lambda x: x[1]) # 按第二个元素排序自定义排序对照：
javascript
// JavaScript — 按对象属性排序
const people = [{name: "Bob", age: 25}, {name: "Alice", age: 30}];
people.sort((a, b) => a.age - b.age); // 按年龄升序
people.sort((a, b) => a.name.localeCompare(b.name)); // 按名字字典序python
# Python — 按对象属性排序
people = [{"name": "Bob", "age": 25}, {"name": "Alice", "age": 30}]
sorted(people, key=lambda p: p["age"]) # 按年龄升序
sorted(people, key=lambda p: p["name"]) # 按名字字典序
# 多级排序
sorted(people, key=lambda p: (p["age"], p["name"])) # 先按年龄，再按名字💡 Python 的
key=lambda比 JS 的比较函数优雅得多。特别是多级排序，Python 用元组(a, b)一行搞定，JS 需要写嵌套的三元表达式。
第 8 章核心知识回顾：
| 排序算法 | 时间 | 空间 | 稳定 | 何时用 |
|---|---|---|---|---|
| 冒泡/选择/插入 | O(n²) | O(1) | 冒泡✅选择❌插入✅ | 理解思想，实际不用 |
| 快速排序 | O(n log n) 平均 | O(log n) | ❌ | 一般排序 |
| 归并排序 | O(n log n) 稳定 | O(n) | ✅ | 需要稳定排序 |
| 内置 sort | O(n log n) | — | JS❌ Python✅ | 99% 的场景 |
| JS sort 陷阱 | 默认字符串排序 | — | — | 必须传 (a,b)=>a-b |
9. 二分查找：有序数组的终极武器
二分查找看似简单，但细节极多——边界处理稍不注意就死循环或漏答案。这一章彻底搞清楚二分的所有变体。
9.1 基础二分查找：精确匹配
在有序数组中找目标值，每次排除一半，O(log n)。
javascript
// JavaScript — 标准二分查找
function binarySearch(nums, target) {
let left = 0, right = nums.length - 1; // 左闭右闭 [left, right]
while (left <= right) { // ⚠️ 是 <=，不是 <
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // 没找到
}python
# Python — 标准二分查找
def binary_search(nums, target):
left, right = 0, len(nums) - 1 # 左闭右闭
while left <= right: # ⚠️ 是 <=
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1💡 左闭右闭
[left, right]的三个要点：①初始right = n-1②循环条件left <= right③更新时mid+1或mid-1。三者必须配套，改一个就要改全部。
9.2 二分查找变体：找左边界、右边界
当数组中有重复元素时，"找第一个等于 target 的"和"找最后一个等于 target 的"是不同的问题。
javascript
// JavaScript — 找左边界（第一个 >= target 的位置）
function lowerBound(nums, target) {
let left = 0, right = nums.length; // 注意：右边界是 n，不是 n-1
while (left < right) { // 注意：是 <，不是 <=
const mid = Math.floor((left + right) / 2);
if (nums[mid] < target) left = mid + 1;
else right = mid; // 注意：不是 mid-1
}
return left;
}
// 找右边界（最后一个 <= target 的位置）
function upperBound(nums, target) {
let left = 0, right = nums.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) left = mid + 1;
else right = mid;
}
return left - 1;
}python
# Python — 找左边界
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# Python 内置 bisect 模块（推荐！）
import bisect
bisect.bisect_left(nums, target) # 左边界
bisect.bisect_right(nums, target) # 右边界💡 Python 的
bisect模块是刷题神器——bisect_left和bisect_right一行搞定左右边界。JS 没有对应的内置工具。
9.3 二分答案：将问题转化为二分
有些题看起来和二分没关系，但可以二分答案：猜一个答案值，判断是否可行，用二分缩小范围。
二分答案的模式：
1. 确定答案的范围 [lo, hi]
2. 取中间值 mid，判断 mid 能否满足条件
3. 满足 → 尝试更优的（缩小右边界）
不满足 → 放宽条件（扩大左边界）例：分割数组的最大值最小化（LeetCode 410）
python
# Python — 二分答案
def split_array(nums, k):
def can_split(max_sum):
"""能否将数组分成 k 段，每段和不超过 max_sum？"""
count, current = 1, 0
for num in nums:
if current + num > max_sum:
count += 1
current = num
else:
current += num
return count <= k
lo, hi = max(nums), sum(nums) # 答案范围
while lo < hi:
mid = (lo + hi) // 2
if can_split(mid):
hi = mid # 可以，尝试更小
else:
lo = mid + 1 # 不行，放宽
return lo9.4 经典题实战：搜索旋转排序数组、寻找峰值
题：搜索旋转排序数组（LeetCode 33）
javascript
// JavaScript
function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) { // 左半段有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左半段
} else {
left = mid + 1;
}
} else { // 右半段有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target 在右半段
} else {
right = mid - 1;
}
}
}
return -1;
}python
# Python
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]: # 左半段有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半段有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1💡 旋转数组的关键：虽然整体无序，但至少有一半是有序的。先判断哪半边有序，再判断 target 是否在有序的那半边。
第 9 章核心知识回顾：
| 变体 | 循环条件 | 返回值 | 典型场景 |
|---|---|---|---|
| 精确匹配 | left <= right | mid 或 -1 | 查找目标值 |
| 左边界 | left < right | left | 第一个 >= target |
| 右边界 | left < right | left - 1 | 最后一个 <= target |
| 二分答案 | lo < hi | lo | 最小化最大值/最大化最小值 |
| 旋转数组 | left <= right | 判断哪半边有序 | 部分有序数组 |
10. 树与二叉树：层次化数据的处理
前端开发者每天都在和"树"打交道——DOM 就是一棵树。理解了 DOM 的父子关系、深度遍历，二叉树就是同样的思路。
10.1 从 DOM 到二叉树：树的基本概念
二叉树的结构：
1 ← 根节点（root）
/ \
2 3 ← 1 的左右子节点
/ \ \
4 5 6 ← 叶子节点（没有子节点）
术语：
- 根节点：最顶部的节点（1）
- 叶子节点：没有子节点的节点（4、5、6）
- 深度/高度：从根到叶子的最长路径（这棵树高度是 3）
- 左子树：根节点左边的所有节点
- 右子树：根节点右边的所有节点javascript
// JavaScript — 二叉树节点
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}python
# Python — 二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right10.2 二叉树的遍历：前序、中序、后序、层序
四种遍历——以上面的树为例：
前序（根→左→右）：1, 2, 4, 5, 3, 6 ← DFS，先处理自己
中序（左→根→右）：4, 2, 5, 1, 3, 6 ← BST 中序遍历是有序的！
后序（左→右→根）：4, 5, 2, 6, 3, 1 ← DFS，先处理子树
层序（逐层扫描）：1, 2, 3, 4, 5, 6 ← BFS，用队列javascript
// JavaScript — 递归遍历
function preorder(root) {
if (!root) return [];
return [root.val, ...preorder(root.left), ...preorder(root.right)];
}
function inorder(root) {
if (!root) return [];
return [...inorder(root.left), root.val, ...inorder(root.right)];
}
// 层序遍历（BFS）
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const level = [];
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}python
# Python — 递归遍历
def preorder(root):
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
# 层序遍历（BFS）
from collections import deque
def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result10.3 二叉搜索树（BST）：有序的树
BST 的核心性质：左子树所有值 < 根 < 右子树所有值。中序遍历 BST 得到的是有序序列。
10.4 经典题实战：最大深度、路径总和、验证 BST、层序遍历
题 1：二叉树的最大深度（LeetCode 104）
javascript
// JavaScript — 递归一行
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}python
# Python
def max_depth(root):
if not root: return 0
return 1 + max(max_depth(root.left), max_depth(root.right))题 2：验证二叉搜索树（LeetCode 98）
python
# Python — 递归 + 上下界
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if root.val <= lo or root.val >= hi:
return False
return (is_valid_bst(root.left, lo, root.val) and
is_valid_bst(root.right, root.val, hi))💡 树的递归思维：处理当前节点，然后"相信"左子树和右子树的递归能给出正确结果。树的大部分题都是这个套路。
第 10 章核心知识回顾：
| 概念 | 说明 |
|---|---|
| 前/中/后序 | DFS 的三种顺序，递归最直观 |
| 层序遍历 | BFS，用队列逐层处理 |
| BST 性质 | 左 < 根 < 右，中序遍历有序 |
| 树的递归 | base case: null → 处理当前 → 递归左右子树 |
| 最大深度 | 1 + max(左深度, 右深度) |
11. 图与 BFS/DFS：网络化数据的处理
图是最通用的数据结构——社交网络、课程依赖、地图导航都是图问题。DFS 和 BFS 在树中已经用过了，图只是多了"可能有环"和"多条路径"的处理。
11.1 图的表示：邻接表 vs 邻接矩阵
javascript
// JavaScript — 邻接表（最常用）
// 图：0→1, 0→2, 1→3, 2→3
const graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
};
// 或者用 Map
const graph2 = new Map();
graph2.set(0, [1, 2]);python
# Python — 邻接表
# 方式 1：字典
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
# 方式 2：defaultdict（推荐，不用初始化）
from collections import defaultdict
graph = defaultdict(list)
graph[0].append(1)
graph[0].append(2)11.2 深度优先搜索（DFS）：一条路走到黑
javascript
// JavaScript — 图的 DFS
function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node); // 处理当前节点
for (const neighbor of (graph[node] || [])) {
dfs(graph, neighbor, visited); // 递归访问邻居
}
}python
# Python — 图的 DFS
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node in visited:
return
visited.add(node)
print(node) # 处理当前节点
for neighbor in graph[node]:
dfs(graph, neighbor, visited)11.3 广度优先搜索（BFS）：层层推进
javascript
// JavaScript — 图的 BFS
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length) {
const node = queue.shift();
console.log(node);
for (const neighbor of (graph[node] || [])) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}python
# Python — 图的 BFS
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)💡 DFS vs BFS：DFS 用栈（递归本身就是栈），适合"找路径""判断连通性"；BFS 用队列，适合"找最短路径""层序遍历"。
11.4 经典题实战：岛屿数量、课程表（拓扑排序）、最短路径
题 1：岛屿数量（LeetCode 200）— DFS 染色
python
# Python — DFS
def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # 标记已访问（"染色"）
dfs(r+1, c) # 上下左右
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c) # 把整个岛屿染掉
return count题 2：课程表（LeetCode 207）— 拓扑排序
python
# Python — BFS 拓扑排序
from collections import deque, defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
completed = 0
while queue:
node = queue.popleft()
completed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return completed == num_courses # 全部完成 = 无环第 11 章核心知识回顾：
| 概念 | 说明 |
|---|---|
| 邻接表 | dict/Map 存储，空间 O(V+E)，最常用 |
| DFS | 递归/栈，适合路径搜索、连通性、岛屿问题 |
| BFS | 队列，适合最短路径、层序遍历 |
| visited 集合 | 图必须用 visited 防止重复访问（树不需要因为无环） |
| 拓扑排序 | BFS + 入度，判断有向图是否有环 |
12. 动态规划：从暴力递归到记忆化到 DP
动态规划（DP）是算法面试的终极 Boss。但它没有想象中那么难——核心就是把递归中重复计算的结果存起来。
12.1 什么是动态规划：重叠子问题 + 最优子结构
DP 的两个前提条件：
① 重叠子问题：子问题会被重复计算
→ fib(5) 会多次计算 fib(3)、fib(2)
② 最优子结构：大问题的最优解包含子问题的最优解
→ 最短路径的子路径也是最短的12.2 三步走方法论：暴力递归 → 记忆化 → 底层 DP
以斐波那契为例演示三步进化：
javascript
// JavaScript
// 第 1 步：暴力递归 — O(2^n)，太慢！
function fib1(n) {
if (n <= 1) return n;
return fib1(n-1) + fib1(n-2); // fib(3) 被重复算了很多次
}
// 第 2 步：记忆化递归 — O(n)，加个缓存
function fib2(n, memo = {}) {
if (n <= 1) return n;
if (n in memo) return memo[n]; // 算过了，直接返回
memo[n] = fib2(n-1, memo) + fib2(n-2, memo);
return memo[n];
}
// 第 3 步：底层 DP — O(n)，从底部建表
function fib3(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
}
return dp[n];
}python
# Python — 三步走
# 第 1 步：暴力递归
def fib1(n):
if n <= 1: return n
return fib1(n-1) + fib1(n-2)
# 第 2 步：记忆化递归（Python 的 lru_cache 是神器！）
from functools import lru_cache
@lru_cache(maxsize=None) # 自动记忆化！
def fib2(n):
if n <= 1: return n
return fib2(n-1) + fib2(n-2)
# 第 3 步：底层 DP
def fib3(n):
if n <= 1: return n
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]💡 Python 的
@lru_cache是刷 DP 题的大杀器——加一行装饰器就自动把暴力递归变成记忆化递归，不用手动管理 memo 字典。JS 没有对应的内置工具。
12.3 一维 DP：爬楼梯、打家劫舍、零钱兑换
题 1：爬楼梯（LeetCode 70）
python
# Python — dp[i] = 到达第 i 级的方法数
def climb_stairs(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2] # 从 i-1 跨 1 步 或 从 i-2 跨 2 步
return dp[n]题 2：零钱兑换（LeetCode 322）
javascript
// JavaScript — dp[i] = 凑出金额 i 的最少硬币数
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // 凑出 0 元需要 0 枚硬币
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}python
# Python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -112.4 二维 DP：最长公共子序列、编辑距离
题：最长公共子序列（LeetCode 1143）
python
# Python — dp[i][j] = text1[:i] 和 text2[:j] 的 LCS 长度
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # 字符相同，+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 取较大的
return dp[m][n]12.5 DP 实战心法：如何定义状态、写出转移方程
DP 解题四步法：
① 定义状态：dp[i] 或 dp[i][j] 代表什么？
→ 关键要让状态能表达子问题的答案
② 写转移方程：dp[i] 和 dp[i-1]（或其他）的关系
→ 思考"最后一步"做了什么决策
③ 确定初始值：dp[0] = ?
→ 最小的子问题的答案
④ 确定遍历顺序和返回值
→ 通常从小到大遍历，返回 dp[n]第 12 章核心知识回顾：
| 概念 | 一句话解释 |
|---|---|
| 重叠子问题 | 同一子问题被多次计算 → 用缓存 |
| 三步走 | 暴力递归 → 加 memo → 改 DP 数组 |
@lru_cache | Python 自动记忆化，刷题必备 |
| 一维 DP | dp[i] 依赖前几个状态 |
| 二维 DP | dp[i][j] 依赖左、上、左上 |
| 状态定义 | DP 最难的一步，决定了转移方程 |
13. 贪心算法：局部最优到全局最优
贪心的核心思想：每一步都选当前最好的选择，希望最终得到全局最优解。贪心比 DP 简单，但难在证明"局部最优确实能导致全局最优"。
13.1 贪心的核心思想：每一步选当前最好的
贪心 vs 动态规划：
贪心：每步选最优，不回头 → 简单但不总是正确
DP： 考虑所有可能，选最优 → 总是正确但更复杂
什么时候贪心有效？
→ 当问题具有"贪心选择性质"：每一步的最优选择不会影响后续的最优选择13.2 区间问题：无重叠区间、合并区间
题：无重叠区间（LeetCode 435）— 最少删几个区间让剩余不重叠
javascript
// JavaScript — 按结束时间排序，贪心选择
function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // 按结束时间升序
let count = 0, end = -Infinity;
for (const [start, finish] of intervals) {
if (start >= end) {
end = finish; // 不重叠，保留这个区间
} else {
count++; // 重叠，删除（贪心：删结束晚的）
}
}
return count;
}python
# Python
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # 按结束时间升序
count, end = 0, float('-inf')
for start, finish in intervals:
if start >= end:
end = finish # 不重叠，保留
else:
count += 1 # 重叠，删除
return count💡 区间贪心的套路：按结束时间排序 → 每次选结束最早的 → 这样留给后面的空间最大。
13.3 经典题实战：跳跃游戏、分发糖果、任务调度器
题：跳跃游戏（LeetCode 55）
javascript
// JavaScript — 贪心：维护能到达的最远位置
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // 当前位置超过最远距离
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}python
# Python
def can_jump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
return True题：跳跃游戏 II（LeetCode 45）— 最少跳几次
python
# Python — 贪心：每次跳到能让下一步到达最远的位置
def jump(nums):
jumps, current_end, farthest = 0, 0, 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end: # 到达当前跳跃的边界
jumps += 1
current_end = farthest # 更新边界为能到达的最远处
return jumps第 13 章核心知识回顾：
| 概念 | 说明 |
|---|---|
| 贪心 | 每步选局部最优，不回头 |
| 贪心 vs DP | 贪心更快但适用条件更严格 |
| 区间贪心 | 按结束时间排序，贪心选结束最早的 |
| 跳跃游戏 | 维护 maxReach，判断能否/最少几步到达 |
| 验证正确性 | 贪心的难点在于证明局部最优 = 全局最优 |
14. 实战专题：高频面试题 Top 20 精讲
前 13 章学了所有基础知识，这一章精选 LeetCode 高频面试题，综合运用前面的技巧。
14.1 数组与哈希：两数之和、盛最多水的容器、接雨水
接雨水（LeetCode 42）— 双指针法
javascript
// JavaScript — 双指针 O(n)
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left]; // 当前位置能接的水
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}python
# Python
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water14.2 字符串与栈：有效括号、最小覆盖子串
最小覆盖子串（LeetCode 76）— 滑动窗口的终极应用，已在第 3 章讲了滑动窗口模板，这里是其最难的变体，综合运用 Map 计数 + 滑动窗口。
14.3 树与图：二叉树的最近公共祖先、单词搜索
最近公共祖先（LeetCode 236）
python
# Python — 递归
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right: return root # p 和 q 分别在左右子树
return left or right # 都在同一边14.4 DP 与贪心：最长递增子序列、买卖股票最佳时机
买卖股票最佳时机（LeetCode 121）— 贪心
javascript
// JavaScript — 维护最低价格，计算最大利润
function maxProfit(prices) {
let minPrice = Infinity, maxProfit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}python
# Python
def max_profit(prices):
min_price, profit = float('inf'), 0
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price - min_price)
return profit最长递增子序列（LeetCode 300）— DP + 二分
python
# Python — O(n log n) 解法
import bisect
def length_of_lis(nums):
tails = [] # tails[i] = 长度为 i+1 的递增子序列的最小尾部
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num) # 比所有尾部都大，延长子序列
else:
tails[pos] = num # 替换，保持尾部尽可能小
return len(tails)14.5 综合设计题：LRU 缓存、前缀树（Trie）
LRU 缓存（LeetCode 146）— 哈希表 + 双向链表
python
# Python — 用 OrderedDict 简化实现
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # 移到末尾（最近使用）
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 删除最久未使用（头部）💡 Python 的
OrderedDict天然支持move_to_end和popitem，完美匹配 LRU 的需求。JS 的Map也保持插入顺序，可以用类似的思路实现。
全书总结与刷题路线图
恭喜你读到这里！回顾一下整个学习路径：
学习路线图：
第 1-2 章：基础建设
├── JS ↔ Python 语法对照
└── 复杂度分析（选算法的标尺）
第 3-6 章：线性数据结构
├── 数组 + 哈希表（双指针、滑动窗口）
├── 字符串（回文、变位词）
├── 栈与队列（单调栈、BFS 基础）
└── 链表（反转、快慢指针）
第 7-9 章：核心算法思想
├── 递归与回溯（排列、组合、子集）
├── 排序（快排、归并、内置排序）
└── 二分查找（精确、边界、二分答案）
第 10-11 章：非线性数据结构
├── 树与二叉树（遍历、BST）
└── 图与 BFS/DFS（岛屿、拓扑排序）
第 12-13 章：高级算法
├── 动态规划（三步走、一维/二维 DP）
└── 贪心算法（区间、跳跃游戏）
第 14 章：面试实战
└── Top 20 高频题精讲推荐刷题顺序（按难度递进）：
| 阶段 | 建议 | 题量 |
|---|---|---|
| 入门 | 数组 + 哈希表 + 字符串的 Easy 题 | 30 题 |
| 进阶 | 栈/队列 + 链表 + 二叉树 | 30 题 |
| 核心 | 回溯 + 二分 + 排序 | 20 题 |
| 挑战 | DP + 图 + 贪心 | 20 题 |
| 冲刺 | LeetCode Hot 100 + 面试高频 | 不限 |
💡 最后的建议：不要只"看懂"题解——一定要自己独立写出来。看懂和写出来之间有巨大的鸿沟。每道题先想 15 分钟，想不出来再看提示，看完提示后合上题解自己写。这才是刷题的正确姿势。