知识库K28
编码、架构与项目 · KNOWLEDGE CHAPTER
K28

数据结构与算法

算法题的核心不是模板名，而是契约、不变量与成本模型。先规定输入和输出含义，再找一个每轮保持成立的事实，证明结束时它推出答案；复杂度要同时计算遍历、辅助存储、调用栈和输出规模。

编码、架构与项目2 道章节练习10 道主练关联
先修知识：K07 · 值、对象与集合K08 · 作用域、函数与生命周期

核心模型

算法题的核心不是模板名，而是契约、不变量与成本模型。先规定输入和输出含义，再找一个每轮保持成立的事实，证明结束时它推出答案；复杂度要同时计算遍历、辅助存储、调用栈和输出规模。

原理与机制

对象、数组与图的身份不能丢

数组扁平化用显式栈逆序压入，保持输出左到右并避开递归栈；这只适用于明确约定的稠密、无环输入。重复引用的子数组应展开两次，全局 visited 不能冒充路径上的环检测。克隆则恰好需要原对象→新对象映射：先登记空壳再处理属性，才能保留环和共享引用。空槽、Symbol、访问器和原型都是独立契约，JSON 往返无法保真；复制描述符和读取 getter 的值也不同。

映射把全表搜索变成局部操作

列表转森林先建立 id 映射，再连接父子，不要求父先于子；重复 ID、缺父与环分别诊断。在每个非根恰有一个合法父节点的前提下，从全部根可达数量不足可识别环及其附属节点，该结论不能推广到任意图。LRU 则利用 Map 插入顺序：命中或更新时 delete 后 set，淘汰最前键；has 与 get 是否刷新应写清。TTL 判断是否过期，LRU 判断容量不足时先扔谁，按条数限额还不等于内存限额。

搜索正确性来自不变量

无权图 BFS 按距离层扩展，首次发现即记录前驱并入队，可防同层重复；数组加 head 游标避免反复 shift。首次发现路径的边数最短，代价 O(V+E)，若要枚举全部最短路径，还需多个前驱且计算输出规模。二分查找则保持左侧都小于 target、右侧都不小于 target 的区间不变量。每步排除确定的一半，区间为空时收敛到插入位置；未排序、NaN 或比较器不一致会破坏证明前提。

排序后扫描与分治有不同证据

闭区间合并先复制端点并按起点排序，再维护最后合并段；相等端点相交，半开语义要另定。归并排序从有序小段两指针合成大段，每层总工作 O(n)，段长翻倍共 O(log n) 层；相等时先取左段保证稳定，复用辅助数组仍需 O(n) 空间。现代原生 sort 要求稳定，但标准不强制特定算法或复杂度。复制外层数组不会深拷贝对象，比较器成本也未必恒定。

状态递推与标准解析各自减少歧义

无限硬币最少枚数令 dp[s] 表示金额 s 的最优值，dp[0]=0。枚举最后一枚正面额 c，取 dp[s-c]+1 的最小值；若子方案不最优，替换后会改进原方案，因此递推成立。时间 O(金额×面额数)、空间 O(金额)，是按数值展开的伪多项式算法。URL 则优先使用标准解析器而非手拆：保留重复键，区分空值与缺失，按白名单验证数值和跳转目的地。Map 能避开原型键冲突，但不会自动提供授权。

最小示例

javascript
javascript
function lowerBound(sorted, target) {
  let lo = 0, hi = sorted.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
console.log(lowerBound([1, 2, 2, 5], 2)); // 1
console.log(lowerBound([1, 2, 2, 5], 6)); // 4
console.log(lowerBound([], 1));           // 0

相等时仍收缩右边界，所以重复的2得到第一个位置。答案允许等于数组长度，右开区间不会漏掉插入末尾的情况。函数假设输入已按有限数字升序排列，复杂度 O(log n)；若先验排序，不能把整个流程也说成 O(log n)。

核验：Node v24.19.0：空数组、重复值首位置、末端插入和全大于目标断言通过；未验证未排序或非法数值输入。

边界与取舍

边界

  • 面额1、3、4凑6时，贪心为三枚，最优是3+3；零或负面额会破坏递推的先后依赖。
  • BFS 最短指无权图的边数最少；带权图不能直接沿用首次发现结论。
  • Map 常见哈希实现近似常数访问，但 ECMAScript 只要求平均次线性，不能声称规范保证严格 O(1)。

取舍

  • 显式栈消除调用栈限制，却仍要付出工作栈与输出内存；极大输入应考虑分段或流式输出。
  • 保留引用身份忠于原图，深度隔离值则可能改变语义；先定义数据契约，再决定复制范围。

口述示范

我会先澄清数据、边界和输出，再讲不变量与终止条件，最后分开分析算法成本和语言运行时成本。用重复、空值、环和反例验证契约，比只背一段代码更可靠。

章节练习

练习 1

实现稳定归并与闭区间合并时，各自最关键的不变量是什么？

展开检查点
  • 归并相等取左，验证键序、稳定性和输入不变。
  • 区间先排序，仅与最后段比较；明确端点相等以及浅拷贝边界。
相关题目：X11D19
练习 2

把最少硬币和森林校验各找一个独立验证方法，并说明资源上限。

展开检查点
  • 小金额用 BFS 与 DP 对照，覆盖1/3/4凑6和不可达。
  • 森林覆盖重复ID、孤儿、自环及正常树旁的不可达环，分析 O(n) 映射假设。
相关题目：X05D16D17

参考来源与核验边界

2026-10-04 核验。算法证明在本章输入契约内成立；硬币题契约和归并实现均属教学延伸，不能据企业面经主题推断现场完整题面。

内容版本：2026-10-04.2 · 题目和来源 ID 保持原样，本站不将面经标签解释为企业官方出题或高频保证。