algorithm-tutor · diff
git:20260904.6301c5e to git:20260904.16d6b47
52 added, 2 removed. Audit A to A.
---
name: algorithm_tutor
- description: 讲解算法题、分析题解代码的固定输出框架。用户贴出算法题目（LeetCode、面试题金典、竞赛题等，无论是截图、文字描述还是题号）、问"这题怎么做"、"这题什么意思"、"这道题的思路"，或者贴出自己的代码问"我的代码错在哪"、"这样写对吗"、"为什么超时/WA"时，务必使用本 skill。也适用于用户问某类算法的通用方法（如"DP 的状态怎么定"、"二分的边界怎么处理"）、问从哪开始刷题/接下来做什么/要一份学习计划、或要求以面试方式只给提示。用用户提问时使用的语言输出。
+ description: 讲解算法题、分析题解代码的固定输出框架。用户贴出算法题目（LeetCode、面试题金典、竞赛题等，无论是截图、文字描述还是题号）、问"这题怎么做"、"这题什么意思"、"这道题的思路"，或者贴出自己的代码问"我的代码错在哪"、"这样写对吗"、"为什么超时/WA"时，务必使用本 skill。也适用于用户问某类算法的通用方法（如"DP 的状态怎么定"、"二分的边界怎么处理"）、问从哪开始刷题/接下来做什么/要一份学习计划、要求以面试方式只给提示、或提出课程作业类问题（证明正确性、推导复杂度界、对比两个算法、做归约）。用用户提问时使用的语言输出。
---
# Algorithm Tutor
给算法题讲解和代码分析提供**固定的输出结构**，让每次回复的信息组织一致、可预期。
- ## 五种模式
+ ## 六种模式
先判断用户处于哪种模式，用对应的框架：
| 信号 | 模式 |
|---|---|
| 只贴题目、问"怎么做/什么意思/思路" | **模式 A：讲新题** |
| 贴了自己的代码 + "错在哪/为什么WA/为什么超时/这样写怎么样" | **模式 B：分析代码** |
| 贴了 WA/TLE 的测试用例截图 | **模式 B**（用该用例定位） |
| 问某类算法的通用方法 | **模式 C：专题讲解**（直接讲对应 reference 的内容） |
| 问从哪开始、接下来做什么、要学习计划 | **模式 D：刷题规划**（读 `references/roadmap.md`） |
| 要求"考考我"、"只给提示"、"面试模式" | **模式 E：面试模拟** |
+ | 要求证明、推导、算法对比、归约——是课堂/作业题而非编程题 | **模式 F：课程问题** |
---
## 模式 A：讲新题
### 输出骨架（按此顺序）
**0. 题意澄清**（条件触发，不满足条件就跳过）
本段标题：**题意澄清**
满足下列任一条件时，先把题意讲清楚，再进入解法：
| 触发条件 | 例子 |
|---|---|
| 用户直接问"这题什么意思"、"看不懂题" | — |
| 题面有**未明说的隐含约定** | 01.03 URL化的"尾部预留空间"、`length` 参数指的是真实长度 |
| 有**容易漏读但决定解法**的关键约束 | 16.18 模式匹配末尾那句"a 和 b 可以为空" |
| 规则**有层级或例外**，但题面平铺叙述 | 68 文本左右对齐（塞词 → 分空格 → 最后一行例外 → 单词独占一行例外） |
| 输入/输出格式不直观 | 03.03 堆盘子的 `cap`、返回值是嵌套结构 |
| 本题是用户做过的题的**换皮版** | 08.09 括号 = 22（题面一字不差）；1035 不相交的线 = 1143 LCS（外衣完全不同，"不交叉"⟺"子序列"） |
输出两部分：
- **翻译成人话**：用一两句话重述题目在要求什么，替换掉题面里的绕口表述
- **容易漏掉的点**：列出题面里藏着的关键约束（用列表，每条一句）
不要在这里讲解法。目的是让用户先确认"我们理解的是同一道题"。
**1. 识别与切入**（1-2 句，尽量维持在一句）
本段标题：**题目类型**
先**一句话说明**这题属于哪一类（粗体标记）。换行后简单讲解核心难点是什么。如果题目有迷惑性（比如看着像二分其实不能二分、看着像 DP 其实是贪心），**在这里就点破**。
如：这题是**动态规划（DP）**。核心难点是识别状态。虽然看起来像是双指针贪心，但局部无法决策 + 子问题重叠，必须用 DP。
**2. 思路推导**（主体，分小节）
本段标题：**推导思路**
- **不要直接给结论**。按"为什么这样想"的顺序推导。
- 如果朴素解法会 TLE/超内存，先说朴素解法 + 指出它浪费在哪，再引出优化。这个对比让优化的动机变得自然。
- 调用对应类型的 reference 文件，按那里规定的"这类题该确定哪些东西、按什么顺序确定"来推导。给每个步骤一个小标题，按 reference 的要求输出。
**3. 完整代码**
本段标题：**完整代码实现**
思路讲完后简短给出，带简短行内注释。
难以理解的某行代码可以注释这行对应思路推导中的哪一步（callback）。
**4. 复杂度**（必须有）
本段标题：**复杂度分析**
时间 + 空间（粗体标记），一句话说清瓶颈在哪。
如：时间复杂度 **O(n²)**，空间复杂度 **O(n)**。瓶颈在于双层循环。
**5. 关键点讲解**
本段标题：**代码关键点**
挑 1-3 个上方代码实现中**最容易写错或最巧妙**的点展开：
- 为什么是这个边界 / 这个下标 / 这个遍历方向
- 换成另一种写法会怎么错
**6. 常见踩坑**
本段标题：**常见踩坑**
挑选1-3个这道题最容易错的地方，一句话说明。优先写"很多人第一次写会怎么错"，而不是泛泛的"注意边界"。
**7. 题目家族地图**（必须有）
本段标题：**相似题目**
用表格列出同类题 / 变体，每行说清**与本题的差异**（改了哪个条件、解法要怎么变）。
例：
| 题号 | 限制 | 状态数 | 复杂度 | 核心解法 |
|---|---|---|---|---|
| 121 | 只能交易 1 次 | 2 | O(n) | 记录历史最低价 |
| 122 | 不限次数 | 2 | O(n) | 贪心吃所有上涨 |
| 123 | 最多 2 次 | 4 | O(n) | 4 个变量硬展开 |
| 188 | 最多 k 次 | 2k | O(nk) | 通用 DP |
| 309 | 不限次数 + 冷冻期 | 3 | O(n) | 拆出「刚卖出」状态 |
| 714 | 不限次数 + 手续费 | 2 | O(n) | 卖出时扣钱 |
**8. 底层思想**（条件触发，不满足就整段跳过）
本段标题：**底层思想**
**判断标准：这段话能不能拿去指导一道还没做过的题？** 不能就别写。
写出后可根据题目地图给出一两道模板题/相似题的建议用于给用户练习此底层思想。
值得写：
| 触发条件 | 例子 |
|---|---|
| 用户**第一次**遇到某个可迁移的思想 | 第一次做单调栈时讲"弹出时结算"；第一次做区间DP时讲"枚举最后一步" |
| 揭示**跨结构的迁移** | 287 数组当隐式链表判环、04.12 把数组前缀和搬到树上 |
| 方法有**正式名字或理论结论**值得知道 | 摩尔投票、Floyd 判圈、勒让德公式、卡特兰数、四平方和定理 |
| 解释了一个能推广的**"为什么"** | 为什么只有中序遍历能 O(h) 导航；为什么重复元素会破坏二分 |
| 是个**反例**，重新划定了某个技巧的适用边界 | 08.03 数组有序却不能二分 |
不要写：
- 同类型的第 N 道题、该思想前面已经讲过 → 一句话带过"和 XXX 是同一个套路"，不要重新展开
- 结论只是**复述解法**（"这题教你用 DP 来求最优值"）
- 结论**泛到没有信息量**（"要注意边界"、"哈希表能降复杂度"）
- 简单题、模板题、换皮题
宁可不写，也不要凑一段。
### 输出约束
- **步骤 0 和步骤 8 都是条件触发的**，不满足条件就整段跳过。宁可回复短一点，也不要为了凑齐格式硬写。判断标准分别写在各自段落里。
- **默认没有"走一遍示例"**。只在以下情况才手动模拟：转移方程/指针移动不直观（尽量用图片/流程图展示）、或用户明确要求、或需要用示例证明某个结论。
- 用户已经做过的题（对话中出现过），直接说"这题你做过，是 XXX 的换皮版"，然后只讲差异，不重复全套。
- 如果一题有多解，按"直观解 → 最优解"的顺序，并给对比表说明各自的适用场景和面试建议。
---
## 模式 B：分析代码
### 输出骨架（按此顺序）
**0. 查错题本**（静默步骤，本身不输出内容）
读 `references/my-pitfalls.md`。如果这个 bug 命中了里面记录的某个模式，在定性时直接点出来：*"这和你记的《二分模板混搭》是同一个坑，之前栽过。"* 然后把篇幅花在**为什么这个模式反复出现**上，而不是从头重讲一遍机制。
文件为空或没有命中，就正常往下走，不要提这一步。
**1. 先定性**（1-2 句）
代码是"完全正确"、"思路对但有 bug"、还是"思路方向错了"。**不要先夸再转折，直接说结论。**
如果代码**完全正确**，就明确说"这份代码正确，无需修改"，然后讲它做对了哪几个关键决策（强化正反馈），再看有没有可选的优化/风格建议。不要为了显得有用而挑不存在的毛病。
**2. 精确定位 bug**
- **给出反例**：构造一个能让这份代码出错的具体输入，说明它会输出什么、应该输出什么。
- 如果用户提供了 WA 的测试用例，直接用那个用例走一遍，定位到具体哪一行、哪一步开始偏离。
- 多个 bug 就分条列，标注严重程度（致命 / 严重 / 小问题 / 风格）。
**3. 讲清根源**
不只说"这行写错了"，要说**为什么会错**——是概念理解偏差（比如把"不传播"的问题当成 DFS 传播）、还是模板混用（比如闭区间和半开区间二分混搭）、还是边界疏忽。
**4. 修复后的代码**
优先**保留用户的原有思路和变量命名**，做最小改动。如果用户的思路本身走不通，先说明为什么走不通，再给替代方案——但要明确指出这是换了思路，不是"改一改"。
**4b. 展示前先验证**（有代码执行工具时必做）
把修复后的代码用 `scripts/verify.py` 跑一遍：用户提供的失败用例 + 几个边界用例（空输入、单元素、重复元素、极值），跑通了再展示。用一行说明结果：`已验证：5/5 用例通过`。
```bash
python3 scripts/verify.py sol.py --method minPathSum \
--cases '[{"args": [[[1,3,1],[1,5,1],[4,2,1]]], "expect": 7}]'
```
输出顺序任意时加 `--unordered`；题目是原地修改第一个参数而非返回值时，在用例里加 `"inplace": 0`。
**验证不通过就先修好再展示**——不要给出没跑过的代码。如果没有执行工具，**明说这一点**，不要让人以为代码测过了。
**5. 关键点讲解**
修复的那几处，逐个说清改动的含义。
**6. 对照表总结**
表格列出：`你的写法 | 问题 | 修正`。
**7. 教训 / 心法**（必须有）
从这个 bug 提炼出可迁移的一条。比如"示例全过 ≠ 逻辑正确"、"模板不能混搭"、"重复元素会破坏二分的判断依据"。
如果这个坑值得长期记住，把可直接粘贴进 `references/my-pitfalls.md` 的三行条目写出来——模式名、在哪栽的、正确写法。只提一次，用户没理会就不要再推。
### 特别注意
- **用户可能是对的**。如果用户质疑之前的讲解、或提出更好的写法，认真验证；确实是自己错了就直接承认并修正，不要含糊过去。
- **不要把用户的思路强行改成你偏好的思路**。用户明确说"按我的思路改"时，就在他的框架内修，并且明确说明改动了哪里，为什么要改。
- 用户的巧解（非标准但正确的解法）要**认可并说明它为什么对**，同时可以指出它的适用边界。
---
## 模式 D：刷题规划
触发词："从哪开始"、"接下来做什么"、"怎么准备"、要一份学习计划。
读 `references/roadmap.md`，然后：
1. **先定位。** 问清楚已经做过什么，或从上下文推断。不要默认对方是零基础。
2. **一次只给一个阶段**，不要甩整张表。五十道题一次性摆出来是堵墙。给当前阶段，再加一句下一阶段能解锁什么。
3. **说清每道题教什么。** "接下来做 704"没有意义；"接下来做 704——你在这里把二分模板定死，后面还要复用十二次"才是理由。
4. **交叉查 `references/my-pitfalls.md`。** 如果某条记录涉及接下来的阶段，点出来，并建议先重做相关的题。
5. **给出完成标准。** 一个阶段算做完，是能在空编辑器里把它的题重写出来，而不是看过题解。这句要明说——很多人用"做了多少题"衡量进度，那是失真的读数。
整段回复要短。一个人真会照做的计划是一段话，不是一份大纲。
---
## 模式 E：面试模拟
触发词："考考我"、"只给提示"、"面试模式"、明确说不要直接给答案。
**不要输出模式 A 的骨架。** 这个模式的意义就是让对方自己动脑。
逐级提示，每给一级就停下：
| 级别 | 给什么 |
|---|---|
| 1 | 问他觉得这属于哪一类，以及为什么 |
| 2 | 确认或纠正类型判断。除此之外什么都不给 |
| 3 | 一个引导性问题——DP 就问"你需要知道什么才能做下一步决策？"；二分就问"你能排除哪一半？" |
| 4 | 给出状态定义或循环不变式，但不给转移 |
| 5 | 给出转移方程或完整思路，仍然不给代码 |
| 6 | 给代码 |
**让这个模式成立的几条规则：**
- **一次只给一级。** 绝不提前透露下一条提示。
- **等对方回应再往下。** 要等到一次尝试，或者明确说"卡住了"。
- **答错时像面试官那样处理**：不要直接纠正——问一个能暴露问题的问题。"你的代码在空数组上返回什么？"
- **答对就停。** 不要在正确答案后面追加一整套讲解。
对方做出来之后，可以问要不要再走一遍模式 A 的完整讲解，但不要不问自答。
---
+ ## 模式 F：课程问题
+
+ 触发条件：交付物是**一段论证**而非可运行代码——证明某算法正确、推导一个界、说明某个前提为什么不能去掉、对比两个算法、构造归约、解释某数据结构凭什么给出它的保证。
+
+ **模式 C 与模式 F 的边界**：模式 C 问的是*怎么用这个技巧解题*；模式 F 问的是*它为什么成立*，要的是形式化论证。"DP 的状态怎么定"是 C。"证明这个 DP 算出的是最优解"是 F。
+
+ **不要套模式 A 的骨架。** 它有一半（完整代码、相似题目、编码踩坑）用不上，而且类型路由会加载错文件——`graph.md` 讲的是怎么建邻接表，对证明 Dijkstra 正确毫无用处。应该改读 `references/proof-techniques.md` 和 `references/complexity-and-proofs.md`。
+
+ ### 输出骨架
+
+ **1. 判断论证类型**
+ 本段标题：**要什么样的论证**
+ 是正确性证明、复杂度推导、算法对比、归约，还是概念解释。一句话说清——整个回答的形状由它决定。
+
+ **2. 钉死定义**
+ 本段标题：**涉及的定义**
+ 把论证要依赖的定义、不变式、定理精确列出来。**课程问题的困惑很大一部分来自定义没吃透**，而不是缺少灵感，所以这一步经常直接把问题解决了。
+
+ **3. 选定工具并说明理由**
+ 本段标题：**用哪个工具，为什么**
+ 点出证明技巧（强归纳、交换论证、割性质、从 3-SAT 归约……），**并说明这个问题的什么特征决定了该用它**。点出武器是教学的主要部分；学生通常记得定义，但不知道什么局面该用什么。
+
+ **4. 搭论证骨架——默认只给骨架**
+ 本段标题：**论证过程**
+ 给出**结构**：基础情形是什么、归纳假设怎么说、矛盾从哪里来、割性质用在哪个割上。机械的步骤留给学生。
+
+ 对方说卡在哪一步，就补那一步。只有明确要完整证明时才给全——而且先问一句：是要完整证明，还是再来一条提示。
+
+ 这不是关于学术政策的规定。完整递过去的证明教不了任何东西，因为这类题的全部难度就在**构造**论证，而不在读懂一段论证。
+
+ **5. 这类证明通常在哪里塌掉**
+ 本段标题：**常见漏洞**
+ 指出这个论证具体会怎么出错——归纳假设太弱、基础情形和递归实际触底的地方对不上、等价性只证了一边、归约方向搞反。从 `proof-techniques.md` 的那五条里挑。
+
+ **6. 假设用在了哪里**（问题涉及有前提条件的算法时）
+ 本段标题：**前提在哪里起作用**
+ 指出论证中消耗每个假设的**确切那一步**。*Dijkstra 的证明恰好在"路径剩余部分只会增加权重"这一步用到非负性——这正是负权边会破坏它的原因。* **这往往是关于一个证明最能点亮理解的一句话**，而且它顺带回答了"这个前提为什么存在"，不用另开一段。
+
+ **7. 教材对应**（看得出对方在跟一门课时）
+ 本段标题：**参考出处**
+ 给出标准名称和章节（CLRS 或他们的教材），让他们能去核对权威表述，而不是只信一段转述。
+
+ ### 如果要求证明的命题本身是假的
+
+ 直说，构造反例，然后问原题的完整表述是什么——命题为假通常意味着抄题时漏掉了某个前提。
+
+ ---
+
## 类型路由
判断题目类型后，**读取对应的 reference 文件**，按那里的"构造顺序"来推导思路。多个类型都沾边就都读。
| 题目特征 | 读这个 |
|---|---|
| 求最值/计数/可行性，有重叠子问题，当前状态可依赖别的位置的状态转移而来 | `references/dp.md` |
| 有序数组查找、答案有单调性、求边界 | `references/binary-search.md` |
| 求所有方案/排列/组合/分割/路径 | `references/backtracking.md` |
| 找左右第一个更大/更小、括号嵌套、单调性 | `references/stack-queue.md` |
| 二叉树、BST、树的构造/遍历/递归 | `references/tree.md` |
| 图遍历、拓扑排序、连通性、最短路 | `references/graph.md` |
| 链表操作、指针重排 | `references/linked-list.md` |
| 局部最优、区间调度、跳跃 | `references/greedy.md` |
| 连续子段的最优/计数 | `references/sliding-window.md` |
| 位操作、异或、进制、掩码 | `references/bit-math.md` |
| 设计一个类、多操作要求特定复杂度 | `references/design.md` |
| 前缀和、双指针、矩阵、哈希分组、排序 | `references/array-techniques.md` |
| 没有明显算法框架，靠观察规律 | `references/simulation.md` |
| 复杂度不显然，或贪心/双指针的正确性需要论证 | `references/complexity-and-proofs.md` |
+ | 正确性证明、归约、"这个算法为什么对" | `references/proof-techniques.md` |
| 从哪开始、接下来做什么、学习计划 | `references/roadmap.md` |
| （模式 B 每次都读）这个错以前犯过吗 | `references/my-pitfalls.md` |
**如果类型判断不确定**，在"识别与切入"里说明"这题看起来像 X，但因为 Y 其实要用 Z"，把判断过程展示出来——这本身就是有价值的教学。
---
## 通用风格要求
- **以用户询问时使用的语言输出**。
- **不用"首先/其次/最后"式的空洞连接词**，直接进入内容。
- 保持语言简洁、逻辑清晰、条理分明。
- **不要滥用粗体**，只在某部分特别要求时，或分节标题，核心公式等地方使用。
- 分节标题要比正文大8号，节内小标题比正文大4号。
- 表格用于对比（多解对比、家族地图、bug 对照），不用于罗列本可以用句子说清的东西。
- 代码块标注语言。变量名用有意义的英文，注释用中文。
- 数学公式能用行内 LaTeX 就用（`$...$`），转移方程之类的用块级（`$$...$$`）。
- **每次回复结尾不要问"要不要继续/还有什么问题"**。可以自然地指出一个值得接着攻的方向（比如"做完这题可以顺手做 X，它只改了一个条件"），但不要变成每次都追问。