算法应试与范式要点
大约 11 分钟
算法应试与范式要点
一、真实性说明（必读）
- 官方不公开标准题库；回忆版表述可能与原卷有出入。
- 本文 不伪造「某年必考某算法」；「考频」为 范式层级 的定性归纳。
- 按卷统计的空白表（范式×年份、程序语言×年份）见 真题统计与命题套路 § 算法与程序填空统计，请用同一套真题来源逐卷自填。
二、阅卷友好书写（简表）
| 书写行为 | 效果 |
|---|---|
| 变量名与题干 一致 | 减少误判 |
边界（null、0、n-1）先写 | 易拿步骤分 |
| 循环起止与题面下标约定一致 | 避免连锁错 |
| 不留白 | 空白 = 失分 |
三、DP / 分治 / 贪心 · 考场快判（摘要）
完整 概念、举例、复杂度表、决策流程图 → 算法设计填空 §〇。
| 范式 | 10 秒识别 | 下午先写什么 |
|---|---|---|
| DP | 最优子结构 + 重叠子问题；背包/切割/LCS | dp 含义 → 初值 → 转移 → 循环方向 |
| 分治 | 子问题 独立，合并 得解；假币/归并/快排 | mid、递归 出口、merge/partition |
| 贪心 | 局部最优 + 题意支持；活动/分数背包/霍夫曼 | 排序关键字 → 扫描 if → 累加器初值 |
一眼排除：0-1 背包 ≠ 贪心；假币 ≠ DP；分数背包 ≠ 0-1 背包（DP）。
四、算法范式 · 定性考频与复习要点
高 / 中 / 低 指在公开回忆卷与教辅中的常见程度，非官方。
| 范式 | 考频（定性） | 典型得分空 | 快速拿分 |
|---|---|---|---|
| 动态规划 | 高 | 状态、dp 转移、循环顺序、初值 | 先写 dp[i] 含义一行；01 背包内层常 逆序 |
| 贪心 | 高 | 排序关键字、if、累加器初值 | 按题干提示属性排序 |
| 分治 | 中 | mid、递归边界、merge/partition | mid = lo + (hi-lo)/2 防溢出 |
| 回溯 | 中 | 选/不选、撤销、剪枝 | dfs 模板：出口 → for 尝试 → 回溯 |
| 双指针 / 滑窗 | 中 | left/right 移动条件 | 先写合法窗口判定 |
| 图 BFS/DFS | 中 | visited、队列、邻接表 | 网格题注意边界 |
| 链表 / 快慢指针 | 中 | next 顺序 | 先接后继再断链 |
| 二叉树递归 | 中 | 先/中/后序位置 | 空树 return 先写 |
与 Java 程序填空的交汇
Java 常叠加 集合、String、Comparator 等空，详见 Java程序填空。复习：范式模板 + Java API 小块 并行。
五、复习侧重（推测 · 仅供参考）
- 仍以 可读过程 + 少量关键空 为主。
- 载体多为栈、队列、哈希、二叉树、图（含网格 BFS）。
- Java 与 C 并行准备 程序填空，以当年卷面为准。
- 极冷门数论在设计师下午 性价比低。
5.1 2017-2019 第四题样本带来的训练顺序
| 范式 | 样本题型 | 优先训练的空 |
|---|---|---|
| 分治/递归 | 假币问题 | 递归规模、终止条件、左右区间 |
| 回溯/图搜索 | Hamilton 回路、n 皇后 | visited、冲突判断、递归出口、撤销选择 |
| 动态规划 | 钢条切割、序列结构、0-1 背包 | 状态定义、初值、转移、循环方向 |
训练顺序：先 DP（背包/切割）→ 回溯（n 皇后/路径）→ 分治递归。贪心、双指针、树链表保持模板熟悉，但不要挤掉前三类时间。
六、考场时间策略
| 阶段 | 建议 |
|---|---|
| 第一轮 | 算法相关题 限时，强制写边界 |
| 第二轮 | 只刷 错题范式，同类连做 3 道 |
| 考前 | 过一遍本节 范式表 + Java 常考 API（各约 10 min） |
七、维护建议
固定一套真题来源；每做一套在 真题统计 增一行——两个月后「个人考频」会清晰到不必依赖二手统计文。仓库不收录真题原文。