1. 怎么使用这一页
本页是练习说明,不预置答案。先独立写出输入输出、朴素解法和主要成本,再选择优化方法;看过提示后如实标记“提示后完成”。每次选一题,不要求一次做完。
前 4 周可以使用数组任务;树图任务等对应阶段完成后再做。每题约 30~45 分钟,超过时间可以记录尝试再寻求一个提示。
2. 隐藏题型练习
2.1 最早再次出现的值
输入有限数值数组,返回从左到右第一次再次出现的值,没有则返回 null,不修改输入。[2, 1, 2, 1] 返回 2;[] 返回 null。
验收:空、单元素、重复不相邻、全相同、负数。解释“最早再次出现”和“出现次数最多”为何不是一个问题。完成后再把需求改成返回首次与再次出现的两个下标,检查保存的信息是否足够。
2.2 一批区间账单
输入不再修改的安全整数数组,以及若干左闭右开查询区间,返回每个区间的和;所有累计结果也在安全整数范围内。非法端点必须明确拒绝,空区间返回零。
验收:零次查询、空数组的合法查询、负值、全区间、越界。分别估计一次查询与大量查询的成本,说明预处理何时值得。约束变更为“批量区间加值后才读取结果”时,重新选择方法。
2.3 依赖是否能够全部完成
输入任务数与有向依赖边,边 [a, b] 表示完成 a 后才能执行 b,任务编号为 0 到 n - 1。返回一种完整合法顺序;存在环则返回 null。空任务集合返回 []。
验收:链、分叉、孤立任务、自环和多节点环。合法顺序可能不唯一,不应只与一份固定答案比较;应验证所有任务恰好出现一次且每条依赖先后关系满足。
3. 工程迁移:菜单树中查找路径
输入是一个菜单森林,节点形如 { id, children };children 是数组,叶子用空数组。约定结构有限、无环、没有共享子节点,所有标识唯一。给定目标标识,返回从某个根到目标的标识路径,找不到返回 null;不修改输入。
先手推以下结构:根 a 的孩子是 b,b 的孩子是 c,另有独立根 d。目标为 c 时返回 ['a', 'b', 'c'];目标为 d 时返回 ['d']。
最低验收:
- 空森林返回
null。 - 根节点、深层节点、第二个根都能命中。
- 不存在的目标返回
null。 - 多次调用结果互不干扰,原森林不变。
- 能解释路径复制、遍历和递归深度带来的成本。
先写朴素版本,再考虑深度不可控时的显式栈。若改成标识不唯一、有环或共享节点,先重定义返回规则和访问语义,不要只给旧代码打补丁。
4. 提示区:尝试后再读
- 最早再次出现:保存已经见过的信息;返回下标时,需要记录位置。
- 区间账单:观察多次求和中重复计算的部分;批量加值观察相邻差的变化。
- 依赖顺序:统计尚未满足的前置依赖,优先处理数量为零的任务。
- 菜单树:定义“当前路径”的不变量,或者让子调用返回是否找到以及对应路径。
5. 用证据记录进步
| 维度 | 通过证据 | 需要补课的信号 |
|---|---|---|
| 理解 | 先说清输入、输出与契约 | 写到一半才发现允许负数或重复 |
| 推导 | 从朴素解法定位主要成本 | 只记住某种模板,没有选择理由 |
| 实现 | 闭卷写出并通过边界测试 | 能读懂但离开答案不能写 |
| 验证 | 主动构造反例和独立对照 | 只运行题面一个样例 |
| 迁移 | 改变约束后知道是否仍成立 | 方法失效时仍坚持套用 |
不把一次失败等同于“算法差”。记录最小失败输入与具体错因,选择下一次练习;完成计划也不等于自动掌握。使用仓库 learning/algorithms/weekly/week-16.md 和进度表记录实际证据。
评论
正在加载评论…