1 打家劫舍系列 1.1 主线 三题共享同一个决策：当前这个位置，选还是不选 选了，就必须跳过与它相邻的位置 不选，就继承邻居的最优解 区别只在"相邻"的拓扑长什么样： 题 相邻结构 处理办法 198 一条链 直接线性 DP 213 一个环 拆成两条链各做一次 198 337 一棵树 后序遍历，每个节点向上返回一对值 1.2 打家劫舍 状态定义： dp[i] = 考虑区间 [0, i] 的房间时，能偷到的最大金额 注意"考虑"两个字 定义是"前 i 间里随便选"，不是"必须偷第 i 间"。所以答案直接是 dp[n-1]，不需要打擂台。这跟后面 300/718 那种"必须以 i 结尾"的定义正好是一对反例，可以拿来对照记。 状态转移： 偷第 i 间： dp[i] = nums[i] + dp[i-2] 不偷第 i 间： dp[i] = dp[i-1] dp[i] = max(dp[i-1], nums[i] + dp[i-2]) 初始化： dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) 代码（滚动数组）： ...
0 Basic 什么是回溯？ 回溯是在“解空间树”上做DFS，进入分支时选择，退出分支时撤销选择 模板：考虑 路径path: 已经做出的选择，如一个全局list 选择列表：当前层还能做的选择，如for loop范围 终止条件：长度/和等等 1def backtrack(path, 选择列表): 2 if 满足终止条件: 3 res.append(path[:]) # 注意拷贝 4 return 5 6 for 选择 in 选择列表: 7 if 不合法(选择): 8 continue / break # 剪枝 9 path.append(选择) # ① 做选择 10 backtrack(path, 新的选择列表) # ② 递归 11 path.pop() # ③ 撤销 收集时期：全节点收集 vs 叶子收集 1# 子集型：树上每个节点都是一个合法答案 2def dfs(start): 3 res.append(path[:]) # 写在开头，不 return 4 for i in range(start, n): 5 ... 6 7# 排列/定长组合：只有叶子是答案 8def dfs(): 9 if len(path) == n: 10 res.append(path[:]); return # 写在终止条件里 11 for i in range(n): 12 ... 复杂度估计：总时间 = 树的节点数 × 每个节点的处理代价 题 节点 / 叶子数 单节点代价 复杂度 78 子集 2ⁿ 个节点 拷贝 O(n) O(n · 2ⁿ) 46 全排列 n! 个叶子 拷贝 O(n) O(n · n!) 77 组合 C(n,k) 个叶子 O(k) O(k · C(n,k)) 22 括号生成 第 n 个卡特兰数 Cₙ O(n) O(n · Cₙ) 79 单词搜索 每步最多 3 个新方向 O(1) O(m·n·3^L) 51 N 皇后 ≤ n! O(n) O(n!) 经验：n ≤ 20 才敢直接写纯回溯（2²⁰ ≈ 10⁶）；排列型n ≤ 10（10! ≈ 3.6×10⁶）。数据范围超了，就该往 DP / 记忆化想 ...
0 Basic 位运算基础 1# 基本操作 2a & b # 按位与：两个都是 1 才为 1 3a | b # 按位或：有一个 1 就为 1 4a ^ b # 按位异或：不同为 1，相同为 0 5~a # 按位取反 6a << n # 左移 n 位（×2^n） 7a >> n # 右移 n 位（÷2^n） 8 9# 异或的重要性质 10a ^ 0 = a # 任何数异或 0 不变 11a ^ a = 0 # 任何数异或自身为 0 12a ^ b ^ a = b # 异或可以"消除"成对出现的数 1. 只出现一次的数字 | Easy 题目：非空数组，除一个元素只出现一次外，其余元素均出现两次。找出那个数。要求 O(n) 时间、O(1) 空间 思路分析： 朴素做法：哈希表/Counter统计每个数字出现次数，空间为O(n) 位运算异或：a ^ 0 = a, a ^ a = 0, a ^ b ^ a = b 踩坑记录： ...
0 Basic 矩阵索引 1matrix[i][j] 2matrix[i][0] # 第i行第一个 3matrix[0][j] # 第j列第一个 原生list没有列的概念： 1matrix[:, j] # TypeError: list indices must be integers or slices, not tuple 2matrix[:][j] # 不报错,但取到的是第 j 行,而且改的是临时副本 嵌套 list 是一维列表装着 m 个互不相干的行对象引用,每行甚至可以长度不同: 1[[1, 2, 3], [4], [5, 6]] # 完全合法 1row = row[::-1] # ✗ 只是把局部名字 row 重新绑定到新列表,matrix 纹丝不动 2row.reverse() # ✓ 原地反转,改的是对象本身 3matrix[i][:] = [0]*n # ✓ 先索引到真实行对象,再对它的切片赋值 → 原地 4matrix[:][i] = [0]*n # ✗ 先切片(造新对象)再索引 → 改的是临时对象 1 Matrix 1.1 矩阵置零 | Medium 题目: 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。 要求原地算法。进阶:使用 O(1) 额外空间 ...
0 Basic 贪心是什么？ 每一步都做当前看起来最优的选择，期望最终得到全局最优解 与动态规划的区别： DP：考虑所有子问题的组合，自底向上构建全局最优 贪心：只看当前一步，不回头，不考虑未来 贪心：每个岔路口走看起来最近的路 DP ：先算出所有路的长度，再选最优 贪心快（O(n)），但不是所有问题都适用 DP 慢（O(n²) 或更高），但一定正确 贪心常见策略： 策略 描述 典型题 排序贪心 先排序再按顺序决策 合并区间、划分字母区间 维护极值 遍历中维护当前最优 买卖股票、跳跃游戏 区间贪心 按端点排序选最优区间 无重叠区间、合并区间 反悔贪心 先贪心选，发现更优时替换 较少见，进阶题 1 买卖股票的最佳时机 | Easy 题目：prices[i] 是第 i 天的价格。只能买一次卖一次(先买后卖),求最大利润;不交易返回0 [7,1,5,3,6,4] → 5（第 2 天买，第 5 天卖，6-1=5） 思路分析： 贪心直觉：我想在之前的最低点买入，在今天卖出 遍历价格，维护到目前为止的最低买入价。对于每一天，计算"今天卖出的利润"并更新最大值 踩坑记录： 想好初始值设置，一般最低就设置为float("inf")，最高设置为float("-inf") 代码： 1class Solution: 2 def maxProfit(self, prices: List[int]) -> int: 3 min_price = float("inf") 4 best = 0 5 6 for p in prices: 7 best = max(best, p - min_price) 8 min_price = min(p, min_price) 9 10 return best 复杂度： ...
0 Binary Search Basic 什么是二分查找？ 二分查找（Binary Search）是在有序数据中通过每次排除一半来快速定位目标的算法。时间复杂度 O(log n) 适用条件： 数据有序（或具有某种单调性/二段性） 能通过中间元素判断答案在哪一半 模板一： 1l, r = 0, n - 1 # 闭区间 [l, r]；值域二分时换成 值域下界, 值域上界 2while l < r: 3 mid = (l + r) // 2 4 if check(mid): 5 r = mid # mid 可能是答案，保留 6 else: 7 l = mid + 1 # mid 一定不是答案，排除 8return l # 退出时 l == r 模板二： 1l, r = 0, n - 1 2while l < r: 3 mid = (l + r + 1) // 2 4 if check(mid): 5 l = mid 6 else: 7 r = mid - 1 8return l 二分一定有解，但是不一定是题目的解 二分的解一定属于[0, n - 1]，但是答案可能是- 1 or n，在循环外考虑 二分答案的三步套路 确认答案可分 ： 大了行小了不行(或反过来) 写 check(x) ：通常是 O(n) 的模拟或贪心 定 l, r 的值域：下界取最小合法值,上界取一个保证可行的值 1 二分模板 1.1 搜索插入位置 | Easy 题目：排序数组 + target,存在返回下标,不存在返回按序插入的位置。要求 O(log n) ...
0 Basic 二叉树是什么? 每个节点最多有两个子节点（左子节点、右子节点）的树结构。 1 ← 根节点 (root) / \ 2 3 ← 深度 1 / \ \ 4 5 6 ← 深度 2（叶子节点） Python节点定义 1class TreeNode: 2 def __init__(self, val=0, left=None, right=None): 3 self.val = val 4 self.left = left 5 self.right = right 四种遍历方式 1# 前序遍历（Pre-order）：根 → 左 → 右 2def preorder(root): 3 if not root: return 4 print(root.val) # 先处理根 5 preorder(root.left) 6 preorder(root.right) 7 8# 中序遍历（In-order）：左 → 根 → 右 9def inorder(root): 10 if not root: return 11 inorder(root.left) 12 print(root.val) # 中间处理根 13 inorder(root.right) 14 15# 后序遍历（Post-order）：左 → 右 → 根 16def postorder(root): 17 if not root: return 18 postorder(root.left) 19 postorder(root.right) 20 print(root.val) # 最后处理根 21 22# 层序遍历（Level-order）：BFS，逐层从左到右 23from collections import deque 24def levelorder(root): 25 if not root: return 26 queue = deque([root]) 27 while queue: 28 node = queue.popleft() 29 print(node.val) 30 if node.left: queue.append(node.left) 31 if node.right: queue.append(node.right) 记忆口诀： 前/中/后指的是根节点在遍历中的位置（前面、中间、后面），左右顺序永远是先左后右。 ...
0 Linked List Basic 链表是什么？ 链表是一种通过指针将节点串联起来的线性数据结构。每个节点包含数据和指向下一个节点的指针 head ↓ [1] → [2] → [3] → [4] → None 与数组的对比： 操作 数组 链表 按下标访问 O(1) O(n) 头部插入/删除 O(n) O(1) 中间插入/删除（已知位置） O(n) O(1) 空间 连续内存 分散内存 Python 中的链表节点 1class ListNode: 2 def __init__(self, val=0, next=None): 3 self.val = val 4 self.next = next 链表的核心操作 1# 遍历 2cur = head 3while cur: 4 print(cur.val) 5 cur = cur.next 6 7# 在 node 后面插入 new_node 8new_node.next = node.next 9node.next = new_node 10 11# 删除 node 的下一个节点 12node.next = node.next.next 链表题的三大神器 哑节点（Dummy Node）：在链表头部加一个虚拟节点，避免处理"头节点可能被删除/改变"的特殊情况 1dummy = ListNode(0) 2dummy.next = head 3# ... 操作 ... 4return dummy.next # 新的头节点 快慢指针：两个指针以不同速度遍历链表 1# 找链表中点（慢指针走一步，快指针走两步） 2slow = fast = head 3while fast and fast.next: 4 slow = slow.next 5 fast = fast.next.next 6# slow 现在指向中点（偶数个节点时是中间偏左） 7 8# 检测环 9slow = fast = head 10while fast and fast.next: 11 slow = slow.next 12 fast = fast.next.next 13 if slow == fast: 14 return True # 有环 递归：链表天然适合递归，处理当前节点 + 递归处理剩余链表。 1def process(node): 2 if not node: 3 return None # base case 4 # 递归处理剩余部分 5 node.next = process(node.next) 6 # 处理当前节点 7 return node 1 快慢指针系 1.1 环形链表 | Easy 题目：给链表头节点 head,判断链表中是否有环。要求 $O(1)$ 空间 ...
0 Stack Basic 栈是什么？ 栈是一种受限的线性表：只允许在同一端（栈顶 top）进行插入和删除。 LIFO（Last In, First Out）：后进先出 两个核心操作：push（入栈）、pop（出栈） 辅助操作：peek/top（看栈顶不弹出）、isEmpty、size 栈 Stack 队列 Queue 顺序 LIFO 后进先出 FIFO 先进先出 操作端 同一端 两端（尾进头出） 典型算法 DFS、回溯、单调栈、表达式求值 BFS、拓扑排序、滑动窗口(单调队列) Python 实现 list collections.deque 实现方式： 数组实现（顺序栈）： 1stack = [] 2stack.append(x) # push, 摊还 O(1) 3x = stack.pop() # pop, O(1) 4x = stack[-1] # peek, O(1) 5if not stack: ... # isEmpty 6len(stack) # size 链表实现（链式栈）：头插法建链表，头结点即栈顶 1class Node: 2 def __init__(self, val, nxt=None): 3 self.val, self.next = val, nxt 4 5class LinkedStack: 6 def __init__(self): 7 self.head = None # 栈顶 8 self.n = 0 9 10 def push(self, val): 11 self.head = Node(val, self.head) # 新节点指向旧栈顶 12 self.n += 1 13 14 def pop(self): 15 val = self.head.val 16 self.head = self.head.next 17 self.n -= 1 18 return val 操作 数组栈 链表栈 push/pop 摊还 O(1) 严格 O(1) 空间 可能有预留空位 每个元素多一个指针 缓存友好 连续内存 节点分散 1 栈的设计与模拟 1.1 最小栈 | Medium 题目：设计支持 push / pop / top / getMin 的栈，所有操作 O(1) ...
0 Prefix Sum Basic 0.1 前缀和定义（1-indexed） 数列前n项和： 1-indexed: $$\text{prefixSum}[i] = \sum_{j=1}^{i} a[j] = a[i] = a[1] + a[2] + \cdots + a[i]$$ 0-indexed: $$\text{prefixSum}[i] = \sum_{j=0}^{i-1} a[j] = a[i]= a[0] + a[1] + \cdots + a[i-1]$$ 前缀和分为两类： 类型 预处理 查询 一维前缀和 $O(n)$ $O(1)$ 二维前缀和 $O(nm)$ $O(1)$ 区间和公式： 1-indexed：$\text{sum(l, r) = prefixSum[r] - prefixSum[l - 1]}$ 0-indexed：$\text{sum(l, r) = prefixSum[r + 1] - prefixSum[l]}$ 适用场景: 数组不变(静态),多次查询区间和 → 前缀和 数组会被修改 → 需要树状数组 / 线段树(前缀和不适用) “子数组和满足某条件"的计数问题 → 前缀和 + 哈希表 0.1.1 一维前缀和 区间[l , r]的和：$$\text{sum}(l, r) = S[r] - S[l - 1]$$ ...