外观
算法速记手册
摘要
先把业务问题写成输入、输出和约束,再依据数据范围与操作选择算法。速记关注适用条件、复杂度和边界,代码与证明链接回正文。复杂度默认使用相应操作为常数成本的模型,实际速度仍受数据分布、硬件和实现影响。
快速入口
知识速记
| 知识点 | 结论与条件 |
|---|---|
| 复杂度 | 看输入规模增长下的操作次数,区分最坏、平均和摊还;O(n) 不直接对应毫秒 |
| 数组与链表 | 数组按下标常数访问,链表定位通常线性;已知位置改链快不代表查找加插入快 |
| Hash | 平均查询成本依分布和扩容等条件;键的 equals/hashCode 契约与可变性影响正确性 |
| 栈与队列 | 栈后进先出适合嵌套,队列先进先出适合层序;单调结构用不变量排除无用候选 |
| 二分 | 必须有有序性或单调判定;固定区间语义,每次严格缩小未决范围 |
| 滑动窗口 | 依靠边界移动可维护的状态;含负数的和约束等场景不一定具备单调性 |
| 排序 | 稳定性、空间、比较成本及最坏情况分别决定选择;比较器还要满足一致的顺序规则 |
| Top K | 保留最大 K 常用大小 K 小顶堆,O(n log K);堆中结果不自然整体有序 |
| 区间 | 闭区间与半开区间决定相接是否冲突;相同端点事件先后必须与规则一致 |
| 图搜索 | 无权图最短跳数用 BFS,有向边方向与 visited 时机要明确;DFS 不默认求最短路 |
| 最短路径 | Dijkstra 要求非负边权;负权场景选择能处理负边及负环的方法 |
| 拓扑与并查集 | 拓扑排序处理 DAG 依赖;并查集处理增量合并后的同组判断,不提供一般删除和路径 |
| 贪心与 DP | 贪心需证明局部选择不丢全局最优;DP 明确状态、转移、初值和顺序 |
| 背包 | 一维 0-1 背包容量倒序避免重复选,完全背包正序允许重用;恰好装满初值不同 |
| Bloom 与一致性哈希 | Bloom 阳性需再确认,常规过滤器不支持直接删除;一致性哈希减少迁移但不执行数据搬迁 |
常见结构与复杂度直接选型
| 结构或方法 | 常用成本 | 适合什么 |
|---|---|---|
| 数组 | 下标 O(1),中间插删常 O(n) | 连续遍历与随机访问 |
| 链表 | 定位 O(n),已持相应节点/前驱改链 O(1) | 特定位置改链,不适合按下标频繁查 |
| Hash 表 | 通常期望 O(1),最坏依实现/碰撞 | 完整键查找;键契约必须稳定 |
| 平衡搜索树 | 通常 O(log n) 查插删 | 范围、前驱后继与有序遍历 |
| 堆 | 看顶 O(1),插入/弹顶 O(log n) | 动态极值和 Top K,遍历不保证有序 |
| Trie | 路径成本与词长有关,输出另算 | 前缀检索,节点内存需预算 |
| 并查集 | 路径压缩和按大小合并后摊还极低 | 增量连通判断,不提供一般删除/路径 |
O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2^n) 是增长关系,不是固定秒数。分析要加上比较、字符串处理、分配和输出成本;摊还便宜不代表每次便宜。
二分、窗口和排序的可用规则
二分固定 [l,r) 时,未决范围是左闭右开;求第一个满足条件的位置,条件成立保留左半,更新 r=mid,不成立更新 l=mid+1,结束 l==r。使用 l+(r-l)/2,避免直接 l+r 的溢出风险;不变量仍要求索引范围合法。
滑动窗口复用状态以减少重复扫描。成立前提是移动边界能安全排除候选;含负数的和约束通常不能套正数窗口的单调推理。单调队列维护候选极值,被删除候选需证明以后不可能更优。
归并典型 O(n log n)、辅助空间 O(n),可稳定;堆排 O(n log n)、常见原地但不稳定;快排平均 O(n log n)、最坏 O(n²),通常不稳定;插入适合小规模或局部有序但最坏 O(n²)。标准库内部实现依 API/版本,选择时先看稳定性与输入契约。比较器不要用可能溢出的 a-b,使用安全比较。
图、区间和贪心怎么判断
BFS 在无权/同权边图上求最少跳数,Dijkstra 适用于非负边权;有负权需能处理负边的算法并判断相关负环。DFS 做遍历、搜索与结构分析,不默认得到最短路。visited 时机应避免重复入队或无穷递归。
拓扑排序处理 DAG:统计入度,取入度零节点,移除出边后让新零入度入队。输出少于节点数说明存在循环相关部分;合法顺序可不唯一。排序顺序只满足依赖,不替代执行调度的资源与失败处理。
半开区间 [a,b) 与 [b,c) 可相接不重叠;闭区间则要重新定义。会议室峰值按端点事件扫描,同时间先释放还是先占用必须与区间契约一致。最大数量区间调度选最早结束需要交换论证,带权收益问题不能直接沿用。
DP、背包、回溯与字符串
DP 五步:定义状态含义 → 写转移 → 初值/不可达值 → 计算顺序 → 返回位置。状态压缩要保留转移需要的旧值;把二维改一维不能随意改变读写顺序。0-1 背包容量倒序,每件最多一次;完全背包正序允许重用。恰好装满时不可达状态与“收益为零”不同,哨兵加法前应判可达和溢出。
LIS 是递增子序列,允许跳过、不改顺序;LCS 是两个序列公共子序列,不要求连续。KMP 的 LPS 描述已匹配前缀可复用的最长前后缀,失配时移动匹配状态,不反复退回文本扫描起点。Java 字符串索引常按 UTF-16 代码单元,不等于任意用户可见字符位置。
回溯按选择 → 递归 → 撤销组织,撤销必须恢复所有路径状态;去重排除等价答案,剪枝排除不可能成功的分支,两者依据不同。递归要有缩小尺度和终止条件,极深树需显式栈及资源预算。
Top K、位运算和概率结构
最大 K 用大小 K 小顶堆:未满插入,满后只有更大值替换堆顶;总成本通常 O(n log K),要排序输出再付 O(K log K)。Quickselect 常见平均线性但需考虑最坏和是否改输入。
n & (n-1) 清最低位的 1;位移与掩码要明确 int/long 宽度和合法位数,不能拿 32 位表达任意大集合。Bloom 的阴性保证依构建、哈希和更新契约,阳性仅表示可能存在;普通位数组不能直接删键。近似最优哈希数 k≈(m/n)ln2,目标误判率 p 下 m≈-n ln p/(ln2)^2,仅在相应理想假设下估容量。
正确性测试与性能验收
先明确空输入、重复、负数、边界与输出顺序,再小规模全枚举或差分,固定 seed 并保存最小反例。检查结构性质:排序后元素集合未变、路径相邻有边、区间不重叠、方案成本正确。两个实现一致不证明两者都无错;有限测试不替代不变量或证明。
性能测量保持输入分布、规模、JDK、预热、硬件和结果消费一致。输出本身巨大时先调整需求,不把 O(n) 误记为任意规模都足够快。
常见问题排查
| 现象 | 检查顺序 | 证据与下一步 |
|---|---|---|
| 样例对,边界错 | 写清合法输入 → 查空值、零、单元素、最大值 → 比较暴力基线 | 固定种子输出最小反例,别只增加随机运行次数。 |
| 输入放大后超时 | 估操作数 → 查嵌套循环和重复搜索 → 看分配与输出规模 | 区分算法增长、比较成本、GC 和 I/O;先改重复工作再讨论常数优化。 |
| 二分死循环或漏值 | 检查区间开闭 → 查 mid 更新 → 手推两元素与全重复 | 不变量要证明目标未被排除,区间必须严格缩小。 |
| 窗口遗漏答案 | 查约束是否单调 → 查移出元素状态 → 查重复与负数 | 边界不可安全移动时换模型;不把所有连续区间问题都套窗口。 |
| 排序错乱或溢出 | 查比较器传递性与相等规则 → 查减法溢出 → 查输入可变性 | 比较整数使用安全比较方式,不用 a-b 代替全部大小关系。 |
| DP 结果虚高或无解变有解 | 查状态含义 → 查初值与不可达值 → 查遍历方向 | 0-1 正序可能重复选;负无穷哨兵参与加法前先判可达。 |
| 图遍历不结束 | 查环、visited 时机、方向 → 查共享节点 → 查递归深度 | 排除重复入队和栈溢出,输出量本身巨大时需重新限定需求。 |
| 内存超预算 | 分输入、辅助结构、结果与临时对象 → 查规模上限 | 状态压缩不能破坏上一轮依赖;空间 O(n) 仍要估对象与实际字节成本。 |
高频问题:可复用代码与边界
下面给出可编译的 Java 17 最小类。所有方法使用 int[] 输入;复杂度不包含调用方读取数据的成本。
二分:找第一个大于等于目标的位置
lowerBound 返回 [0,n];n 表示没有满足条件的元素。前提是数组升序;空数组、重复值、目标越界都使用同一规则。
Top K:选最大的 K 个并升序返回
使用大小不超过 K 的小顶堆,时间 O(n log K),最后输出排序 O(K log K)。K=0 返回空数组;K<0 或 K>n 拒绝,重复值保留。
0-1 背包:容量上限与恰好装满不能混用
下面 knapsack01 求总重量不超过 capacity 的最大价值,允许不选任何物品;重量为正、价值非负。容量倒序确保同一物品只用一次。若要求恰好装满,必须把不可达状态设为负无穷并在转移前检查,不能沿用全部初始化为零。
java
import java.util.Arrays;
import java.util.PriorityQueue;
public class QuickAlgorithms {
static int lowerBound(int[] a, int target) {
int l = 0, r = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
static int[] topK(int[] a, int k) {
if (k < 0 || k > a.length) throw new IllegalArgumentException();
if (k == 0) return new int[0];
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int value : a) {
if (heap.size() < k) heap.add(value);
else if (value > heap.peek()) {
heap.poll();
heap.add(value);
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) result[i] = heap.remove();
return result;
}
static long knapsack01(int[] weight, int[] value, int capacity) {
if (capacity < 0 || weight.length != value.length)
throw new IllegalArgumentException();
long[] dp = new long[capacity + 1];
for (int i = 0; i < weight.length; i++) {
if (weight[i] <= 0 || value[i] < 0)
throw new IllegalArgumentException();
for (int c = capacity; c >= weight[i]; c--)
dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
}
return dp[capacity];
}
public static void main(String[] args) {
System.out.println(lowerBound(new int[]{1, 2, 2, 5}, 2));
System.out.println(lowerBound(new int[]{}, 2));
System.out.println(Arrays.toString(topK(new int[]{3, 1, 3, 2}, 2)));
System.out.println(knapsack01(new int[]{2, 3}, new int[]{4, 5}, 4));
}
}保存为 QuickAlgorithms.java,运行 javac QuickAlgorithms.java 和 java QuickAlgorithms。预期依次输出 1、0、[3, 3]、5。背包容量为 4 时不能重复选重量 2 的同一物品,因此不是 8。大 capacity 会造成内存/时间压力,应先做资源上限校验。
图和窗口:先检查能否使用模板
无权最少边数用 BFS,入队时标记 visited 防止重复;非负权最短路用 Dijkstra,堆中旧距离条目应跳过;存在负边不能直接沿用。拓扑排序输出节点数少于总数时存在环相关剩余部分,不把部分顺序当作完整可执行顺序。
正数窗口能依赖扩张使和增、收缩使和减;含负数时此前提失效。例如 [2,-1,2] 的目标和问题应先检查是否需要前缀和与哈希,而不是只把正数窗口复制过来。
上线前边界:用反例检查规则
| 方法 | 必须覆盖的输入 | 应检查的性质 |
|---|---|---|
| lowerBound | 空、全小于、全大于、重复、目标等于边界 | 返回前面都 < target,返回及后面都 >= target |
| Top K | K=0、K=n、重复、负数 | 与完整排序取最后 K 个一致;原数组未改变 |
| 背包 | 空物品、容量 0、全部超重、单件不可重复 | 小规模枚举所有子集所得最优值一致 |
用固定随机种子生成小输入,和线性查找/完整排序/子集枚举做差分;保存失败输入。性能测量另固定规模和分布,不把小输入正确当作大输入资源可接受。
工具与参数
算法专题以操作和验证方法为工具。运行 Java 示例时按文章所需 JDK,record、var 等版本要求不能省略;性能测量先证明结果正确,先固定输入、环境和预期结果。
| 工具或操作 | 速查用途 | 条件与边界 |
|---|---|---|
| 顺序扫描/全枚举 | 小输入的正确性基线 | 只限可控规模,基线也要独立检查业务语义 |
| 差分测试 | 同输入比较不同实现 | 固定随机种子,记录输入、规则与结果;两个相同错误可同时通过 |
| 不变量检查 | 验证循环每轮保留的条件 | 二分范围、堆候选、路径合法性应具体描述,不只检查最终值 |
| JMH | 测 Java 微基准 | 需要依赖与注解处理,预热、多 fork、结果消费;不是端到端容量证明 |
Arrays.sort / List.sort | 标准库排序入口 | 原地/对象/基本类型与稳定性条件按 API 区分;不承诺固定内部算法 |
PriorityQueue.peek/poll/offer | 堆顶、移除、加入 | peek 看极值,不等于遍历有序;比较器决定最小/最大含义 |
| HashMap / TreeMap | 精确查找与有序导航 | 一个侧重哈希,一个侧重有序关系,键不可变性与比较规则需一致 |
| BFS queue / DFS stack | 最短跳数或深度搜索 | visited 与入队/出栈时机要匹配算法;无限或巨大图需限范围 |
| n、K、边数、容量、位数 | 估时间空间上限 | DP 容量维度可能是伪多项式,位移和计数要检查整数宽度 |
易错点与记忆提示
- 先约束,再模型,再证明,再实现:同题不同约束可能是不同问题。
- 最大 K 用小堆,输出排序另付成本:K 合法范围先校验。
- 0-1 倒序,完全正序:只针对相应一维背包转移,不能推广到所有 DP。
- BFS 看跳数,Dijkstra 看非负权:路径成本模型先明确。
- 有序不等于单调答案,平均不等于最坏:边界假设写清楚。
- 测试找反例,证明讲保证:性能数据不能替代正确性。
原理与完整示例
需要原因、源码或完整实验时再阅读:
- A - 算法正确性、测试与基准方法
- 01 - 代码能跑不等于能用:时间复杂度如何决定系统上限
- 06 - 二分查找不只是在数组里找数:边界与答案搜索
- 07 - 双指针与滑动窗口:把嵌套扫描降为线性处理
- 08 - 排序算法怎么选:稳定性、内存与数据分布
- 22 - 背包问题:预算、资源与收益之间如何选择
- 17 - 图的 DFS 与 BFS:依赖关系、社交网络与最短跳数
- 25 - 位运算不是炫技:权限掩码、集合运算与状态压缩
- 03 - 数组与链表没有谁更高级:从 CPU Cache 到随机访问
- 04 - Hash 表为什么快:从用户缓存到冲突处理
- 05 - 栈与队列:浏览器回退、消息消费和单调结构
- 09 - Top K 问题:排行榜为什么不需要每次全量排序
- 10 - 区间问题统一解法:会议冲突、合并与并发峰值
- 19 - 最短路径算法:BFS、Dijkstra 与负权边
- 18 - 拓扑排序:任务依赖如何安排出合法执行顺序
- 16 - 并查集:如何快速判断两个对象是否属于同一组
- 20 - 贪心算法:为什么局部最优有时能得到全局最优
- 21 - 动态规划入门:从重复计算到状态转移
- 26 - 海量数据如何近似判断存在:Bloom Filter 原理与误判边界
- 28 - 一致性哈希:节点扩缩容时如何减少缓存迁移