剑指 Offer
题型映射

01概述 · 类型

• 复杂度比较类：先写清最好 / 平均 / 最坏，平均必须带分布或随机化前提。大 O 是上界。
• 递归与迭代改写类：递归深度可能到 n，空间不是「免费」。若用显式栈模拟递归，须计入额外栈空间；能直接改成普通循环的不一定需要栈（可能 O(1) 额外空间）。

02线性表 · 类型

• 有序序列合并类：双指针扫两个有序源。顺序表按下标 O(1)；链表只能顺指针，仍 O(n+m)。
• 单链表删除 / 倒数类：改链要前驱。倒数第 k：声明 1≤k≤n；快指针先走 k 步（不足 k 步判非法），然后快慢同步推进至快指针为 null，慢指针即指向倒数第 k 个。定位仍是 O(n)。
• 环检测类：从同一起点按 next 推进：快慢在非空结点相遇 → 有环；快指针或其 next 到 null → 无环。未相遇的中间时刻不能判无环。这是链表走法，不是图的 DFS 染色。

03栈与队列 · 类型

• 两栈实现队列：两个 LIFO 对倒模拟 FIFO，均摊转移，单次最坏仍可 O(n)。摊还不是平均。
• 队列实现栈：用 FIFO 队列——单队列入队后把旧元素转到队尾，或双队列来回搬运。不要写成「两个 LIFO」。
• 括号 / 配对类：遇开入栈、遇闭看栈顶是否匹配。栈是 LIFO。
• 循环队列满空类：空 front==rear；满 (rear+1)%M==front（浪费一格）。不要写成「牺牲元素以外的另一种满」还不声明。

04串 · 类型

• 朴素匹配复杂度类：设 1≤m≤n。最坏 Θ((n−m+1)m)；最好成功匹配第一次对齐就成功时 Θ(m)，不是无条件最好。
• KMP next 类：本站用严 1 下标，next[1]=0。abaabc → 0 1 1 2 2 3。next 与 nextval 分开声明。

05树 · 类型

• 遍历与重建类：前序+中序或后序+中序可重建（无重复键）。层序是队列，不是递归栈的另一种名字。
• 完全二叉树下标类：1 下标，左子 2i 当 2i≤n，右子 2i+1 当 2i+1≤n。根在第 1 层。n0=n2+1 只对非空二叉树。

06查找树 · 类型

• BST 合法性 / 第 k 小类：键互异时中序严格递增；允许重复键须先声明放置规则（等键放左/右），中序非降本身不能表达该策略。查找、插入、删除都是 O(h)；随机插入期望才 O(log n)。
• AVL 平衡因子类：bf ∈ {−1,0,1}。旋转恢复高度对数，不必默全部情形编号。
• B / B+ 口径类：根若非叶至少 2 叉；非根内部至少 ⌈m/2⌉；单结点根可为叶。B+ 记录只在叶，分隔键可重复。

07图 · 类型

• 遍历应用类：邻接表 BFS/DFS 均为 O(V+E)。连通块、拓扑（仅 DAG）走这套。
• 最短路选型类：非负 → Dijkstra。有负权边但无负环：全源用 Floyd（允许负边禁负环）；单源可能负边用 Bellman-Ford，只报告源点可达负环。
• MST 类：Prim / Kruskal 可用于带负权的无向图；不要和 Dijkstra 的非负前提捆在一句里。

08查找 · 类型

• 有序顺序表折半类：必须有序且随机访问。边界与不变式见 珠玑。
• 局部有序段查找类：旋转后仍有一半有序，先判断哪半有序再折。不是打乱数组上的对数查找。

09散列 · 类型

• 值到下标映射类：均匀假设下平均 O(1)，最坏 O(n)。开放定址 α<1。
• 开放定址删除类：墓碑，同一散列/探查序列才能继续走。本站二次探查 h+i²。

10排序 · 类型

• 第 k 大 / 选择类：堆选择或划分。建堆 O(n)。快排式划分平均要随机输入或随机枢轴，最坏 Θ(n²)。
• 稳定性判断类：直接插入、相等不换的冒泡、归并、按位稳定的基数稳定；希尔、堆、默认快排通常不稳。

章末自测