Skip to content

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']。

最低验收:

  1. 空森林返回 null。
  2. 根节点、深层节点、第二个根都能命中。
  3. 不存在的目标返回 null。
  4. 多次调用结果互不干扰,原森林不变。
  5. 能解释路径复制、遍历和递归深度带来的成本。

先写朴素版本,再考虑深度不可控时的显式栈。若改成标识不唯一、有环或共享节点,先重定义返回规则和访问语义,不要只给旧代码打补丁。

4. 提示区:尝试后再读 ​

  • 最早再次出现:保存已经见过的信息;返回下标时,需要记录位置。
  • 区间账单:观察多次求和中重复计算的部分;批量加值观察相邻差的变化。
  • 依赖顺序:统计尚未满足的前置依赖,优先处理数量为零的任务。
  • 菜单树:定义“当前路径”的不变量,或者让子调用返回是否找到以及对应路径。

对应文章:哈希、前缀和与差分、图、递归。

5. 用证据记录进步 ​

维度通过证据需要补课的信号
理解先说清输入、输出与契约写到一半才发现允许负数或重复
推导从朴素解法定位主要成本只记住某种模板,没有选择理由
实现闭卷写出并通过边界测试能读懂但离开答案不能写
验证主动构造反例和独立对照只运行题面一个样例
迁移改变约束后知道是否仍成立方法失效时仍坚持套用

不把一次失败等同于“算法差”。记录最小失败输入与具体错因,选择下一次练习;完成计划也不等于自动掌握。使用仓库 learning/algorithms/weekly/week-16.md 和进度表记录实际证据。

评论

正在加载评论…