简介面向使用《数据结构与算法分析Java语言描述》第三版的学生与自学者这份习题答案文档可用于课后对照、期末复习及算法基础查漏补缺适合正在巩固Java数据结构、递归思想和复杂度分析的读者。压缩包内仅含1个docx文件约1.52MB集中收录教材习题的解答与推导便于按章节检索、整理笔记和复盘证明过程。文档内容覆盖processFile递归处理文件包含、整数递归函数、数学归纳法证明对数性质、等比数列与差分求和、模运算证明2^100 mod 5、大O与对数估计以及斐波那契数列归纳证明等兼顾代码片段与数学推导。已有2435人学习可作为核对解题思路、理解证明步骤和补充算法分析练习的参考。1. 一份答案真正值钱的地方从 1.8 那道差分求和说起多数人拿到一份 Java 数据结构与算法分析的习题解答第一反应是翻到卡住的那道题对答案对完就合上。可 1.8 那道求和最能说明问题S 1 2/4 3/16 4/64 …答案写的是 4/9只记住 4/9下次换个系数照样不会。答案真正值钱的是它示范的一套动作——把 S 乘以公比再与原式相减让中间项成对消掉剩下 3S 4/3。这套错位相减在算法分析里反复出现递归式展开、等比级数收敛、摊还分析里都能看到同构写法。这份第三版解答从第 1 章的数学工具一路铺到第 3 章的链表指针每段都在回答同一个问题结论为什么成立凭什么相信它。搞懂这条推导链比记住任何一道题的最终数字都抗遗忘。2. 递归的两种用法processFile 的调用栈与 ones 的除基取余递归在教材里通常被讲成“自己调用自己”这句话正确但没有信息量。真正需要看懂的是两件事递归在内存里长什么样调用栈以及递归为什么能在有限步内停下来规模单调递减。第 1 章的两道题恰好各代表一面1.4 的processFile处理的是“递归调用可能形成环”的问题1.5 的ones处理的是“每次把规模减半”的问题。前者要额外维护状态后者靠数学性质自动收敛混为一谈就容易写出跑不完的代码。2.1 递归处理 #include为什么必须维护“尚未返回的文件”列表1.4 给的场景很具体写一个processFile(String fileName)打开文件、逐行处理、关闭文件一旦读到#include SomeFile这样的行就递归调用processFile(SomeFile)。这个需求在编译器预处理、构建脚本、配置继承里都能见到。问题出在“自我引用”上——A 包含 BB 又包含 A递归就会沿着调用链一路钻下去直到栈溢出。教材原答案的处理方式是维护一个“调用尚未终止的文件列表”每次发起新调用前先查一遍。这个列表的名字看着朴素本质上是图遍历里的“灰色节点集合”。用三色标记的说法更好理解白色是还没碰过的文件灰色是当前调用栈上正处理、还没返回的文件黑色是已经处理完的文件。判断一个 include 是不是环只需要看目标文件是不是灰色如果只是黑色那说明它在别的分支已经处理过重复出现是合法的菱形包含不是环。// 用 Set 充当 DFS 的“灰色节点”集合只记录当前调用链上的文件 private static final SetString inProgress new HashSet(); static void processFile(String fileName) throws IOException { if (inProgress.contains(fileName)) { // 目标还在栈上说明成环 throw new IllegalStateException(cyclic include: fileName); } inProgress.add(fileName); // 入栈前染灰 try (BufferedReader in new BufferedReader(new FileReader(fileName))) { String line; while ((line in.readLine()) ! null) { if (line.startsWith(#include )) { // 递归进入被包含文件调用返回后它才会变黑 processFile(line.substring(#include .length()).trim()); } else { // 正常行处理逻辑略 } } } finally { inProgress.remove(fileName); // 出栈后褪色允许菱形包含重复进入 } }代码里最容易写错的是finally里的remove。很多人凭直觉会想既然要防止重复处理那处理过的文件就一直留在集合里不就行了这样写会把合法的菱形包含误判成环——A 包含 B 和 CB 和 C 又都包含 DD 完全应该被处理两次或者至少被允许进入两次它不是环。remove放在finally里而不是函数末尾是为了让异常路径也能正确褪色否则一次 IO 异常就会让集合里残留一个永远灰色的文件后续所有引用它的地方全部误报。参数说明上fileName应当先规范化成绝对路径再入集合否则./a.h和a.h会被当成两个不同的文件环检测形同虚设。这一点原答案没有展开但在真实工程里是血泪经验路径不归一化环检测就只是个心理安慰。2.2 ones(n) 的递归拆解n%2 与 n/2 背后的除基取余1.5 的代码只有三行但它是理解“递归规模递减”最干净的样本public static int ones(int n) { if (n 2) return n; // 0 返回 01 返回 1 return n % 2 ones(n / 2); // 当前最低位 剩余高位里 1 的个数 }n % 2取的是二进制最低位n / 2是把最低位右移掉两者组合起来就是经典的除基取余法——把一个整数按进制逐位剥下来只不过这里剥的是二进制剥下来的位直接相加。递归深度是 ⌊log₂n⌋ 1每层只做取模、整除、加法三个常数操作所以时间 O(log n)空间 O(log n)栈帧。终止条件写成n 2而不是n 0值得说一句。写成n 0也能得到正确答案因为1 % 2 1、ones(0) 0只是多压了一层栈写成n 2相当于把 n 1 这个平凡情况提前短路省一次调用。这类小优化在大 O 记号里完全看不出来但它体现了一个习惯递归的基准情形应该覆盖“已经不需要再拆”的所有输入而不是只覆盖最小值一个点。这道题埋着一个材料里没提的坑Java 的%对负数返回负余数-3 % 2等于-1所以传负数进来会得到一个负数结果而不是“1 的个数”。工程代码里要么在入口断言n 0要么用Integer.bitCount(n)直接走硬件指令。后者在 HotSpot 上会被内联成一条popcnt比任何递归写法都快这也是“算法题的最优解和工程里的最优解常常不是同一个东西”的典型例子。2.3 递归的代价与替代从栈深度到 log N再到幂运算的迭代写法递归的第二个用法是“分治 合并”2.22 到 2.24 讨论的快速幂就是这类。教材给的思路是算 X^62不必做 61 次乘法先算出 X²、X⁴、X⁸、X¹⁶、X³²再组合成 X^62 X³² · X¹⁶ · X⁸ · X⁴ · X²一共 8 次乘法。2.24 还给出了通用的乘法次数公式当 N 1 时乘法次数是 ⌊log₂N⌋ b(N) − 1其中 b(N) 是 N 的二进制表示里 1 的个数。把这个递推改成迭代代码会比递归版本更短也省掉了栈static long pow(long x, int n) { long result 1; while (n 0) { if ((n 1) 1) result * x; // 当前二进制位是 1把这一档的幂累乘进结果 x * x; // 底数平方对应下一位的权重 n 1; // 右移处理下一位 } return result; }代码里x * x每轮必执行一次共 ⌊log₂N⌋ 次result * x只在遇到 1 位时执行除最高位之外的 1 的个数是 b(N) − 1两者相加正好对上前面的公式。这个“必然操作 条件操作”的结构是快速幂能在常数因子上做得比递归版本更好的原因递归版每层都有函数调用开销和返回时的额外乘法迭代版全部在寄存器里完成。这三道题连起来看递归的选型标准就清楚了当规模单调递减且子问题数量为 1如ones时递归只是把循环换了个写法收益主要是可读性当子问题数量为 2 但其中一半可以复用计算结果如快速幂的平方复用时递归/分治才有实质收益当递归涉及外部资源如processFile的文件句柄时必须在递归之外维护额外的状态否则环、句柄泄漏、重复处理会一起找上门。3. 渐进阶的排序与证明2.1 那条函数链凭什么这么站队第 2 章的核心不是背结论而是建立一套可复用的比较方法。教材给的函数序列看起来像一份需要死记的排行榜其实每两个相邻项之间都有一条明确的判定依据。把这套依据抽出来遇到没见过的函数也能现推。3.1 把函数钉在同一条数轴上2.1 的排序与“同阶”判定原题要求把 2/N、37、√N、N、N log log N、N log N、N log(N²)、N log²N、N^1.5、N²、N² log N、N³、2^(N/2)、2^N 按增长速度排序。逐项对着看判定依据可以整理成一张对照表函数与前一档的关系判定依据2/N、37常数或衰减归入 O(1)与 N 无关取 N → ∞ 后趋于 0 或常数√N慢于 NN^0.5 与 N^1 的指数比较N log log N略快于 Nlog log N 无界但增长极慢N log N、N log(N²)同阶log(N²) 2 log N只差常数因子 2N log²N快于 N log N多乘一个无界的 log NN^1.5快于 N log²N任何多项式幂最终都会超过对数幂N²、N² log N、N³依次递增主项指数或附加对数因子递增2^(N/2)、2^N指数级远超任何多项式底数固定时比较指数表里最容易被忽略的是“N log N 与 N log(N²) 同阶”这一行。大 O 记号丢掉的正是常数因子而log(N²)展开后就是2 log N常数 2 被丢掉之后两者完全一样。反过来说如果两个函数的比值在 N → ∞ 时趋于一个非零常数它们就同阶趋于 0 或 ∞才有快慢之分。这个比值判据比记排行榜可靠得多因为排行榜只覆盖被列出来的那十几个函数。2.6 的答案里出现了 O(log log D) 这种复杂度它和 √N 的对比也常被搞混。log log D 意味着对规模做了两次折半再折半比任何正次幂都慢但在实际数据范围内数值可能反超——D 要大到 2 的 2 的 k 次方这种量级log log D 才会显出优势。这就是渐进分析和工程实测的分歧点后面避坑一章还会回来讲。3.2 取对数 洛必达2.3 与 2.4 的证明骨架2.3 要证的是对任意小的正数 εN log N 的增长都慢于 N^(1ε)。直接看比值 N log N / N^(1ε) log N / N^ε 不好判断教材的处理是反证加两次取对数。假设结论不成立那么 N^ε 反而慢于 log N两边取对数得到 ε log N 慢于 log log N再令 L log N就变成 εL 慢于 log L等价于 ε²L 慢于 log²L。而 log²L 是 L 的低阶量矛盾。这个证明的动作叫“取对数降维”幂次比较通过一次 log 变成乘法比较再取一次 log 变成对数比较原本难处理的 N^ε 就被压成了常数 ε。这个技巧在分析递归式、比较指数级算法时反复出现值得单独记一笔。2.4 证明的是更强的结论对任意正整数 klog^k N o(N)。教材用的是洛必达法则归纳。把极限写成 lim (log^k N) / N分子分母同时对 N 求导分子求导得 k·log^(k−1)N / N分母求导得 1于是极限化成 lim k·log^(k−1)N / N。这是一个规模更小的同型极限归纳假设告诉我们对 k−1 次幂该极限为 0乘上常数 k 依然是 0归纳成立。用代码验证这类比值趋势比盯着公式看直观得多// 打印 f(N)/g(N) 的采样值比值单调下降且趋于 0说明 f 增长更慢 static void ratio(FunctionDouble, Double f, FunctionDouble, Double g, double... ns) { for (double n : ns) { System.out.printf(N%.0f\tf/g%.8f%n, n, f.apply(n) / g.apply(n)); } } public static void main(String[] args) { // 比较 N log N 与 N^1.1比值应当一路走低 ratio(n - n * Math.log(n), n - Math.pow(n, 1.1), 1e3, 1e4, 1e5, 1e6, 1e7); }这段代码只是采样验证不是证明。它的价值在于帮你建立直觉如果比值在采样范围内已经开始稳定下降那前面的推导大概率没写错如果比值反而在涨说明公式或者指数抄错了。采样能证伪不能证真这个边界要拎清楚。3.3 摆动的反例2.5 里 f/g 为什么可以既不收敛也不发散2.5 给出一个反例令 f(N) 在 N 为偶数时等于 1、为奇数时等于 Ng(N) 在 N 为奇数时等于 1、为偶数时等于 N。这样 f(N)/g(N) 在偶数处是 1/N在奇数处是 N随 N 增大在 0 和无穷之间来回摆没有极限。这个反例打击的是一种常见的偷懒做法直接用 lim f/g 是否趋于常数来判断同阶。极限不存在不代表两个函数不可比较只代表它们没有稳定的比值。大 O、Ω、Θ 的正式定义从来不依赖极限而是量词形式f(N) O(g(N)) 指存在常数 c 和 N₀使得所有 N N₀ 都有 f(N) ≤ c·g(N)。这个定义天然允许摆动只要上界常数存在就行。工程上的含义是复杂度上界是可以被构造出来的最坏情况它不承诺“平均表现”。一个算法在偶数输入上极快、奇数输入上极慢它的最坏情况上界由奇数决定平均情况则要看输入分布——这两件事必须分开说混着说就会得出“这个算法是 O(1)”这种荒谬结论。3.4 循环层数相乘为什么会高估2.7 的 O(N⁵) 与 O(N⁴)2.7 列了六段嵌套循环其中两段最能说明问题。第五段里 j 的上界是 i²k 的上界是 j如果直接把三层循环的规模相乘会得到 N·N²·N² O(N⁵)。这个上界没错但不紧。第六段更极端按循环次数相乘是 O(N³) 的外层可if语句真正为真的次数只有 O(N²)内层循环总共只跑 O(N²) 次每次 O(N²)合计 O(N⁴)。// 2.7(VI) 的骨架三层循环看起来是 N^3实际内层命中远少于这个数 long sum 0; for (int i 0; i n; i) { for (int j 0; j i * i; j) { if (j % i 0) { // 对每个 i恰好命中 i 次j 0, i, 2i, ... for (int k 0; k j; k) { sum; } } } }精确计算一下对固定的 i命中的 j 是 0, i, 2i, …, (i−1)i内层代价分别是 0, i, 2i, …, (i−1)i求和得 i·i(i−1)/2 ≈ i³/2。再对 i 从 1 到 N 求和得到约 N⁴/8所以紧界是 O(N⁴)比简单相乘得到的 O(N³) 外层估算要精细得多。这里的方法论值得记下来嵌套循环的复杂度不是各层上界的乘积而是“每层实际执行次数”的乘积。判断实际执行次数要看循环变量之间的依赖关系而不是各层自己的取值范围。j % i 0这种条件把内层从 O(N³) 压到了 O(N²)如果只用眼睛数循环嵌套有几层这个压缩完全看不出来。反过来如果内层条件更宽松乘积估算法就会低估那才是真正危险的方向。4. 就地修改的两类风险链表指针的顺序与洗牌的均匀性第 3 章的链表题和第 2 章的随机排列题在教材里分属两章但它们共享一个特征都在原数据结构上就地修改不允许开辟等量新空间。就地修改的代价是“中间状态”会短暂不满足不变量一旦某一步顺序写错结构就断了、或者分布就歪了。指针错误会立刻崩分布错误则悄无声息后者更难查。4.1 单链表交换相邻节点为什么参数必须是 beforeP3.2(a) 要求交换单链表中两个相邻节点。教材的答案把参数定为beforep也就是待交换的两个节点中前一个的前驱而不是直接传待交换的第一个节点// beforeP 指向两个待交换相邻节点的前驱p 与 afterP 均假定非 null public static void swapWithNext(Node beforeP) { Node p beforeP.next; Node afterP p.next; p.next afterP.next; // 1. p 跳过 afterP先接上后半段 beforeP.next afterP; // 2. 前驱改指 afterP afterP.next p; // 3. afterP 回指 p }三步的顺序是这段代码的全部难点。第一步必须先把p.next改成afterP.next因为一旦执行了第二步beforeP.next就不再指向 p如果此时还没保存afterP.next后半条链就永久丢失了。正确的思路是凡是会覆盖掉的指针先在覆盖前把它的值用掉或者存下来。这条规则在双向链表里会变得更啰嗦因为要覆盖的指针多了一倍。参数为什么必须是beforeP而不是p答案很直接单链表节点没有指向前驱的指针要修改前驱的next就必须持有前驱的引用。如果只传p在 O(1) 时间内根本无法找到它的前驱除非从头遍历一遍那样交换就退化成 O(N)。这里有个常见的替代方案值得对比不交换节点只交换两个节点里的data。这样只需要传p三行赋值就完事代码短得多。但它有一个隐蔽的副作用——如果外部代码持有这两个节点的引用交换数据之后那些引用的语义就悄悄变了原本指向节点 A 的变量现在读到的是 B 的值。在链表只被内部迭代器访问的场景下没问题一旦节点被缓存、被索引、被放进哈希表这个“假交换”就会翻车。教材选择交换节点而不是交换值是在为通用性付代价。4.2 双向链表的交换多出来的两次 prev 回写3.2(b) 的双向链表版本把参数改成了p本身因为双向链表能从p.prev直接拿到前驱。代价是指针赋值从三条变成六条// p 与 afterP 为待交换的两个相邻节点beforeP 是 p 的前驱 public static void swapWithNext(Node p) { Node beforeP p.prev; Node afterP p.next; p.next afterP.next; // 1. p 接上后半段 beforeP.next afterP; // 2. 前驱改指 afterP afterP.next p; // 3. afterP 回指 p p.next.prev p; // 4. 修后半段回指 p 的 prev p.prev afterP; // 5. p 的 prev 改成 afterP afterP.prev beforeP; // 6. afterP 的 prev 改成 beforeP }第 4 步依赖第 1 步的结果p.next已经被改成afterP.next所以这里的p.next.prev p修的是后半段那个节点的回指指针。如果第 1 步和第 4 步顺序颠倒p.next还是afterP这一行就会把afterP.prev错误地设成 p紧接着第 6 步又把它改成beforeP看起来结果碰巧对了但中间状态已经被污染一旦中间插入了别的操作比如在第 4、5 步之间回调了用户代码错误就会暴露。双向链表的不变量是对任意节点 x若 x.next 非空则 x.next.prev x。这个不变量可以用一个几行的检查函数兜住写完指针操作后立刻跑一遍比盯着代码看有效// 遍历检查双向链表的前后指针是否自洽可在每次指针操作后调用 static void assertLinkIntegrity(Node head) { for (Node x head; x ! null; x x.next) { if (x.next ! null x.next.prev ! x) { throw new AssertionError(prev/next mismatch at x); } } }这类断言在单测里开着、在生产里关掉是性价比很高的做法。指针类 bug 的特点是“写错一步崩在十步之外”等到崩的时候栈已经指向完全无关的位置回溯成本极高不如在每次修改后就近检查。4.3 洗牌的均匀性判据27 不能被 6 整除2.8 讨论三种随机排列算法。前两种都是“每次随机挑一个判重后再放”第三种是 Floyd 洗牌从后往前第 i 个位置与 [0, i] 之间的随机位置交换。教材特别指出如果把 Floyd 洗牌里的随机上界从 i 改成 n−1也就是每次都与全数组任意位置交换分布就不再均匀。它给的判据非常干净N 3 时三次交换各有 3 种随机取值共 3³ 27 条等概率的执行路径而 3 个元素的全排列只有 3! 6 种。27 不能被 6 整除所以不可能把 27 条路径平均分给 6 种排列必然有的排列被多映射、有的被少映射均匀性直接破掉。这个“路径总数必须能被结果数整除”的判据比跑一百万次统计频率快得多也更确定。// 正确的 Floyd 洗牌第 i 位只与 [0, i] 内的元素交换 static void shuffle(int[] a, Random rnd) { for (int i a.length - 1; i 0; i--) { int j rnd.nextInt(i 1); // 上界是 i1闭区间 [0, i] int t a[i]; a[i] a[j]; a[j] t; } } // 错误的写法上界写成 a.length每次都与全数组交换 // int j rnd.nextInt(a.length);正确版本的正确性可以用归纳证明处理到第 i 位时a[i]被设成从a[0..i]中均匀选出的一个元素剩下的a[0..i-1]仍然是原始集合的均匀随机排列递归下去每一位的边缘分布都是均匀的。错误版本破坏了“剩余集合”的封闭性——已经确定位置的后缀元素会被再次卷入交换均匀性在第一步就被稀释了。4.4 期望复杂度的推导N/(N−i) 从哪来三种算法的期望代价差别很大推导过程比结论更有价值。第一种算法在第 i 个位置填数时已有 i 个位置被占用随机命中未占用位置的概率是 (N−i)/N这是一次成功试验的几何分布期望试验次数就是 N/(N−i)。每次试验要扫描已填的 i 个位置判重花 O(i)所以总代价是 Σᵢ i·N/(N−i)。把求和换元令 k N−i可化为 N·Σ N/k 的量级结果是 O(N² log N)。第二种算法把判重方式从“线性扫描”换成“标记数组”每次试验的判重从 O(i) 降到 O(1)总代价变成 Σᵢ N/(N−i) N·H_NH_N 是调和数约等于 ln N于是 O(N log N)。这一项的改进完全来自数据结构的选择算法流程本身没变——这是“换个查找结构就能降一个量级”的经典案例。第三种 Floyd 洗牌只有一趟循环每次 O(1)总代价 O(N)。有意思的是它的最坏情况也是线性的无论随机数怎么取循环次数都是 N−1 次随机性只影响结果分布不影响执行时间。前两种算法的“最坏情况”则没有有限上界因为理论上随机数可以一直撞到已占用的位置只是概率趋近于 0。教材在这里点了一句关键区别那两种算法以概率 1 终止但不存在“最大运行时间”。工程含义很直接如果你的场景对延迟敏感比如服务端每次请求都要打乱一个小数组前两种“可能无限跑”的算法是不能用的哪怕期望值看起来还行Floyd 洗牌的确定性执行时间才是可交付的。4.5 Josephus 的取模优化M mod N 与反向等价3.6 的 Josephus 问题要求每次数 M 个删除一个。朴素做法是数 M 步但如果 M 远大于当前表长 N绕圈就是浪费。教材给的两个观察都很实用一是数 M 步等价于数 M mod N 步当前表长为 N二是当 M 超过 N/2 时向前数 M 步等价于向后数 N−M 步。第一个观察把复杂度里的 M 压到了 min(M, N)第二个观察在 M 接近 N 时再砍一半。合起来最坏复杂度是 O(N·min(M, N))但在 M 很大或接近 N 的常见参数下实际步数会比朴素实现少一个可观的常数。这里面没有玄学就是把“循环计数”换成“模运算”本质和环形缓冲区里用取模代替判断回绕是同一个思路。链表版本的 Josephus 要注意表长随删除动态变化每次删除后取模的基数都要更新写错这一步会导致下标错位删到不该删的节点。5. 避坑与排查五个最容易在习题里翻车的细节教材答案的正确率不等于照着抄就能跑对。下面五条是这份解答里最容易被误读、或者抄进代码就出问题的地方每条按现象、原因、解决写。5.1 算术与边界类坑一二分查找的递归区间不缩小程序不终止。现象是 2.31 里的情形——low 1, high 2时mid取 (12)/2 向下取整得 1递归调用依然是[1, 2]区间一点没变直接死循环。原因是向下取整的除法让 mid 可能等于 low如果递归分支写成search(mid, high)而不是search(mid1, high)区间就没有收缩。解决办法只有一条把 mid 算准之后保证两个分支里至少有一个端点被排除掉low mid 1或high mid − 1二选一并配一个low high的终止条件。坑二指数取模直接算幂中间结果溢出。2.10 要算 2¹⁰⁰ mod 5正确路径是利用 2⁴ ≡ 1 (mod 5)于是 2¹⁰⁰ (2⁴)²⁵ ≡ 1。如果直接Math.pow(2, 100)再取模double 的精度在 2⁵³ 之后就丢了得到的是个看似合理的错误答案。解决方式是全程在模意义下做乘法每一步都取模绝不让中间量超过模数的平方。坑三ones(n)传负数返回负数。现象是ones(-3)返回 −1 而不是 2。原因是 Java 的%保留被除数符号-3 % 2 -1累加下去自然是负的。解决方法是在入口加断言或者直接用Integer.bitCount(n)后者对负数按补码统计语义明确且是单条指令。5.2 指针与循环类坑四单链表交换顺序写反链断了但不报错。现象是交换后遍历只能走一半或者打印出重复节点。原因在 3.2 的三步里先改了beforeP.next才去读afterP.next此时后半段已经丢失但 Java 不会报错只是有个节点再也没人指向它。解决办法是把“先保存、后覆盖”当成硬规则并在每次结构修改后调用前一节给出的assertLinkIntegrity让错误在最近的位置暴露而不是等到几十行之后。坑五用循环层数相乘估复杂度把 O(N⁴) 写成 O(N⁵)。现象是分析结论比实际高一个量级导致明明能过的方案被误判为不可行。原因是把每层循环的上界直接相乘忽略了循环变量之间的依赖和if条件的过滤作用2.7 的第六段就是典型。解决办法是回到“每层实际执行次数”的定义先写出精确的求和式再化简实在拿不准就写个计数器跑几个规模采样看增长曲线落在哪个幂次上。采样不能替代证明但能立刻抓出量级错误。6. 设计取舍标准答案里的写法工程里该抄哪一半这份解答里的代码都是“教学正确”的写法不是“生产最优”的写法两者的差距集中体现在四个取舍上。第一个是递归与迭代。ones写成递归是为了展示规模递减快速幂写成递归是为了展示分治复用但真正落地的代码里这两处都该写成迭代——递归版的栈帧开销在小规模下看不出来在热路径上会被放大而且深递归在默认栈大小下有溢出风险。判断标准很简单如果递归的唯一收益是“代码短两行”那就换成循环只有当递归能表达出迭代难以表达的结构比如树的遍历、回溯时才值得付栈的代价。第二个是交换值与交换节点。3.2 选择交换节点代价是指针操作多、顺序敏感交换值只要三行但会在节点被外部持有时产生别名问题。我的取舍原则是看节点是否有“身份”如果节点只是容器值才是语义交换值完全够用如果节点本身被索引、被引用、被当作 map 的 key就必须交换节点否则会得到一批指向错乱数据的引用。第三个是均匀性与代价。Floyd 洗牌用一趟线性扫描换来了严格均匀和执行时间确定前两种算法靠拒绝采样省了证明却背上了“以概率 1 终止但无最坏上界”的包袱。在对延迟有承诺的系统里这个包袱不能背在离线批处理里拒绝采样的代码更短反而更不容易写错。均匀性判据路径数能否被排列数整除值得记住它能在你写出“看起来随机”的代码时第一时间报警。第四个是上界与紧界。大 O 给的是上界它保证“不会比这更慢”不保证“就是这么慢”。2.7 里 O(N⁵) 和 O(N⁴) 的差别、2.5 里摆动函数的存在都在提醒同一件事分析结论要区分“能证明的”和“实际发生的”。写文档时给上界是安全的做技术选型时必须拿到紧界或者实测数据否则容易把一个完全可行的方案误杀。我自己的习惯是每读完一道题的解答先合上答案把关键的三五行代码凭记忆重写一遍然后只做一件事——构造一个能让它出错的最小输入。ones(−3)、low1, high2的二分、上界写成n的洗牌这三个输入各自只需要几秒钟就能构造出来却分别戳破了三个“看起来没问题”的写法。从那以后我每次抄任何一段教材代码进项目都会先给它喂一个边界输入再谈别的。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/27 2:51:25 · 阅读 1.2k Java数据结构与算法分析：递归、复杂度与链表指针精解
简介面向使用《数据结构与算法分析Java语言描述》第三版的学生与自学者这份习题答案文档可用于课后对照、期末复习及算法基础查漏补缺适合正在巩固Java数据结构、递归思想和复杂度分析的读者。压缩包内仅含1个docx文件约1.52MB集中收录教材习题的解答与推导便于按章节检索、整理笔记和复盘证明过程。文档内容覆盖processFile递归处理文件包含、整数递归函数、数学归纳法证明对数性质、等比数列与差分求和、模运算证明2^100 mod 5、大O与对数估计以及斐波那契数列归纳证明等兼顾代码片段与数学推导。已有2435人学习可作为核对解题思路、理解证明步骤和补充算法分析练习的参考。1. 一份答案真正值钱的地方从 1.8 那道差分求和说起多数人拿到一份 Java 数据结构与算法分析的习题解答第一反应是翻到卡住的那道题对答案对完就合上。可 1.8 那道求和最能说明问题S 1 2/4 3/16 4/64 …答案写的是 4/9只记住 4/9下次换个系数照样不会。答案真正值钱的是它示范的一套动作——把 S 乘以公比再与原式相减让中间项成对消掉剩下 3S 4/3。这套错位相减在算法分析里反复出现递归式展开、等比级数收敛、摊还分析里都能看到同构写法。这份第三版解答从第 1 章的数学工具一路铺到第 3 章的链表指针每段都在回答同一个问题结论为什么成立凭什么相信它。搞懂这条推导链比记住任何一道题的最终数字都抗遗忘。2. 递归的两种用法processFile 的调用栈与 ones 的除基取余递归在教材里通常被讲成“自己调用自己”这句话正确但没有信息量。真正需要看懂的是两件事递归在内存里长什么样调用栈以及递归为什么能在有限步内停下来规模单调递减。第 1 章的两道题恰好各代表一面1.4 的processFile处理的是“递归调用可能形成环”的问题1.5 的ones处理的是“每次把规模减半”的问题。前者要额外维护状态后者靠数学性质自动收敛混为一谈就容易写出跑不完的代码。2.1 递归处理 #include为什么必须维护“尚未返回的文件”列表1.4 给的场景很具体写一个processFile(String fileName)打开文件、逐行处理、关闭文件一旦读到#include SomeFile这样的行就递归调用processFile(SomeFile)。这个需求在编译器预处理、构建脚本、配置继承里都能见到。问题出在“自我引用”上——A 包含 BB 又包含 A递归就会沿着调用链一路钻下去直到栈溢出。教材原答案的处理方式是维护一个“调用尚未终止的文件列表”每次发起新调用前先查一遍。这个列表的名字看着朴素本质上是图遍历里的“灰色节点集合”。用三色标记的说法更好理解白色是还没碰过的文件灰色是当前调用栈上正处理、还没返回的文件黑色是已经处理完的文件。判断一个 include 是不是环只需要看目标文件是不是灰色如果只是黑色那说明它在别的分支已经处理过重复出现是合法的菱形包含不是环。// 用 Set 充当 DFS 的“灰色节点”集合只记录当前调用链上的文件 private static final SetString inProgress new HashSet(); static void processFile(String fileName) throws IOException { if (inProgress.contains(fileName)) { // 目标还在栈上说明成环 throw new IllegalStateException(cyclic include: fileName); } inProgress.add(fileName); // 入栈前染灰 try (BufferedReader in new BufferedReader(new FileReader(fileName))) { String line; while ((line in.readLine()) ! null) { if (line.startsWith(#include )) { // 递归进入被包含文件调用返回后它才会变黑 processFile(line.substring(#include .length()).trim()); } else { // 正常行处理逻辑略 } } } finally { inProgress.remove(fileName); // 出栈后褪色允许菱形包含重复进入 } }代码里最容易写错的是finally里的remove。很多人凭直觉会想既然要防止重复处理那处理过的文件就一直留在集合里不就行了这样写会把合法的菱形包含误判成环——A 包含 B 和 CB 和 C 又都包含 DD 完全应该被处理两次或者至少被允许进入两次它不是环。remove放在finally里而不是函数末尾是为了让异常路径也能正确褪色否则一次 IO 异常就会让集合里残留一个永远灰色的文件后续所有引用它的地方全部误报。参数说明上fileName应当先规范化成绝对路径再入集合否则./a.h和a.h会被当成两个不同的文件环检测形同虚设。这一点原答案没有展开但在真实工程里是血泪经验路径不归一化环检测就只是个心理安慰。2.2 ones(n) 的递归拆解n%2 与 n/2 背后的除基取余1.5 的代码只有三行但它是理解“递归规模递减”最干净的样本public static int ones(int n) { if (n 2) return n; // 0 返回 01 返回 1 return n % 2 ones(n / 2); // 当前最低位 剩余高位里 1 的个数 }n % 2取的是二进制最低位n / 2是把最低位右移掉两者组合起来就是经典的除基取余法——把一个整数按进制逐位剥下来只不过这里剥的是二进制剥下来的位直接相加。递归深度是 ⌊log₂n⌋ 1每层只做取模、整除、加法三个常数操作所以时间 O(log n)空间 O(log n)栈帧。终止条件写成n 2而不是n 0值得说一句。写成n 0也能得到正确答案因为1 % 2 1、ones(0) 0只是多压了一层栈写成n 2相当于把 n 1 这个平凡情况提前短路省一次调用。这类小优化在大 O 记号里完全看不出来但它体现了一个习惯递归的基准情形应该覆盖“已经不需要再拆”的所有输入而不是只覆盖最小值一个点。这道题埋着一个材料里没提的坑Java 的%对负数返回负余数-3 % 2等于-1所以传负数进来会得到一个负数结果而不是“1 的个数”。工程代码里要么在入口断言n 0要么用Integer.bitCount(n)直接走硬件指令。后者在 HotSpot 上会被内联成一条popcnt比任何递归写法都快这也是“算法题的最优解和工程里的最优解常常不是同一个东西”的典型例子。2.3 递归的代价与替代从栈深度到 log N再到幂运算的迭代写法递归的第二个用法是“分治 合并”2.22 到 2.24 讨论的快速幂就是这类。教材给的思路是算 X^62不必做 61 次乘法先算出 X²、X⁴、X⁸、X¹⁶、X³²再组合成 X^62 X³² · X¹⁶ · X⁸ · X⁴ · X²一共 8 次乘法。2.24 还给出了通用的乘法次数公式当 N 1 时乘法次数是 ⌊log₂N⌋ b(N) − 1其中 b(N) 是 N 的二进制表示里 1 的个数。把这个递推改成迭代代码会比递归版本更短也省掉了栈static long pow(long x, int n) { long result 1; while (n 0) { if ((n 1) 1) result * x; // 当前二进制位是 1把这一档的幂累乘进结果 x * x; // 底数平方对应下一位的权重 n 1; // 右移处理下一位 } return result; }代码里x * x每轮必执行一次共 ⌊log₂N⌋ 次result * x只在遇到 1 位时执行除最高位之外的 1 的个数是 b(N) − 1两者相加正好对上前面的公式。这个“必然操作 条件操作”的结构是快速幂能在常数因子上做得比递归版本更好的原因递归版每层都有函数调用开销和返回时的额外乘法迭代版全部在寄存器里完成。这三道题连起来看递归的选型标准就清楚了当规模单调递减且子问题数量为 1如ones时递归只是把循环换了个写法收益主要是可读性当子问题数量为 2 但其中一半可以复用计算结果如快速幂的平方复用时递归/分治才有实质收益当递归涉及外部资源如processFile的文件句柄时必须在递归之外维护额外的状态否则环、句柄泄漏、重复处理会一起找上门。3. 渐进阶的排序与证明2.1 那条函数链凭什么这么站队第 2 章的核心不是背结论而是建立一套可复用的比较方法。教材给的函数序列看起来像一份需要死记的排行榜其实每两个相邻项之间都有一条明确的判定依据。把这套依据抽出来遇到没见过的函数也能现推。3.1 把函数钉在同一条数轴上2.1 的排序与“同阶”判定原题要求把 2/N、37、√N、N、N log log N、N log N、N log(N²)、N log²N、N^1.5、N²、N² log N、N³、2^(N/2)、2^N 按增长速度排序。逐项对着看判定依据可以整理成一张对照表函数与前一档的关系判定依据2/N、37常数或衰减归入 O(1)与 N 无关取 N → ∞ 后趋于 0 或常数√N慢于 NN^0.5 与 N^1 的指数比较N log log N略快于 Nlog log N 无界但增长极慢N log N、N log(N²)同阶log(N²) 2 log N只差常数因子 2N log²N快于 N log N多乘一个无界的 log NN^1.5快于 N log²N任何多项式幂最终都会超过对数幂N²、N² log N、N³依次递增主项指数或附加对数因子递增2^(N/2)、2^N指数级远超任何多项式底数固定时比较指数表里最容易被忽略的是“N log N 与 N log(N²) 同阶”这一行。大 O 记号丢掉的正是常数因子而log(N²)展开后就是2 log N常数 2 被丢掉之后两者完全一样。反过来说如果两个函数的比值在 N → ∞ 时趋于一个非零常数它们就同阶趋于 0 或 ∞才有快慢之分。这个比值判据比记排行榜可靠得多因为排行榜只覆盖被列出来的那十几个函数。2.6 的答案里出现了 O(log log D) 这种复杂度它和 √N 的对比也常被搞混。log log D 意味着对规模做了两次折半再折半比任何正次幂都慢但在实际数据范围内数值可能反超——D 要大到 2 的 2 的 k 次方这种量级log log D 才会显出优势。这就是渐进分析和工程实测的分歧点后面避坑一章还会回来讲。3.2 取对数 洛必达2.3 与 2.4 的证明骨架2.3 要证的是对任意小的正数 εN log N 的增长都慢于 N^(1ε)。直接看比值 N log N / N^(1ε) log N / N^ε 不好判断教材的处理是反证加两次取对数。假设结论不成立那么 N^ε 反而慢于 log N两边取对数得到 ε log N 慢于 log log N再令 L log N就变成 εL 慢于 log L等价于 ε²L 慢于 log²L。而 log²L 是 L 的低阶量矛盾。这个证明的动作叫“取对数降维”幂次比较通过一次 log 变成乘法比较再取一次 log 变成对数比较原本难处理的 N^ε 就被压成了常数 ε。这个技巧在分析递归式、比较指数级算法时反复出现值得单独记一笔。2.4 证明的是更强的结论对任意正整数 klog^k N o(N)。教材用的是洛必达法则归纳。把极限写成 lim (log^k N) / N分子分母同时对 N 求导分子求导得 k·log^(k−1)N / N分母求导得 1于是极限化成 lim k·log^(k−1)N / N。这是一个规模更小的同型极限归纳假设告诉我们对 k−1 次幂该极限为 0乘上常数 k 依然是 0归纳成立。用代码验证这类比值趋势比盯着公式看直观得多// 打印 f(N)/g(N) 的采样值比值单调下降且趋于 0说明 f 增长更慢 static void ratio(FunctionDouble, Double f, FunctionDouble, Double g, double... ns) { for (double n : ns) { System.out.printf(N%.0f\tf/g%.8f%n, n, f.apply(n) / g.apply(n)); } } public static void main(String[] args) { // 比较 N log N 与 N^1.1比值应当一路走低 ratio(n - n * Math.log(n), n - Math.pow(n, 1.1), 1e3, 1e4, 1e5, 1e6, 1e7); }这段代码只是采样验证不是证明。它的价值在于帮你建立直觉如果比值在采样范围内已经开始稳定下降那前面的推导大概率没写错如果比值反而在涨说明公式或者指数抄错了。采样能证伪不能证真这个边界要拎清楚。3.3 摆动的反例2.5 里 f/g 为什么可以既不收敛也不发散2.5 给出一个反例令 f(N) 在 N 为偶数时等于 1、为奇数时等于 Ng(N) 在 N 为奇数时等于 1、为偶数时等于 N。这样 f(N)/g(N) 在偶数处是 1/N在奇数处是 N随 N 增大在 0 和无穷之间来回摆没有极限。这个反例打击的是一种常见的偷懒做法直接用 lim f/g 是否趋于常数来判断同阶。极限不存在不代表两个函数不可比较只代表它们没有稳定的比值。大 O、Ω、Θ 的正式定义从来不依赖极限而是量词形式f(N) O(g(N)) 指存在常数 c 和 N₀使得所有 N N₀ 都有 f(N) ≤ c·g(N)。这个定义天然允许摆动只要上界常数存在就行。工程上的含义是复杂度上界是可以被构造出来的最坏情况它不承诺“平均表现”。一个算法在偶数输入上极快、奇数输入上极慢它的最坏情况上界由奇数决定平均情况则要看输入分布——这两件事必须分开说混着说就会得出“这个算法是 O(1)”这种荒谬结论。3.4 循环层数相乘为什么会高估2.7 的 O(N⁵) 与 O(N⁴)2.7 列了六段嵌套循环其中两段最能说明问题。第五段里 j 的上界是 i²k 的上界是 j如果直接把三层循环的规模相乘会得到 N·N²·N² O(N⁵)。这个上界没错但不紧。第六段更极端按循环次数相乘是 O(N³) 的外层可if语句真正为真的次数只有 O(N²)内层循环总共只跑 O(N²) 次每次 O(N²)合计 O(N⁴)。// 2.7(VI) 的骨架三层循环看起来是 N^3实际内层命中远少于这个数 long sum 0; for (int i 0; i n; i) { for (int j 0; j i * i; j) { if (j % i 0) { // 对每个 i恰好命中 i 次j 0, i, 2i, ... for (int k 0; k j; k) { sum; } } } }精确计算一下对固定的 i命中的 j 是 0, i, 2i, …, (i−1)i内层代价分别是 0, i, 2i, …, (i−1)i求和得 i·i(i−1)/2 ≈ i³/2。再对 i 从 1 到 N 求和得到约 N⁴/8所以紧界是 O(N⁴)比简单相乘得到的 O(N³) 外层估算要精细得多。这里的方法论值得记下来嵌套循环的复杂度不是各层上界的乘积而是“每层实际执行次数”的乘积。判断实际执行次数要看循环变量之间的依赖关系而不是各层自己的取值范围。j % i 0这种条件把内层从 O(N³) 压到了 O(N²)如果只用眼睛数循环嵌套有几层这个压缩完全看不出来。反过来如果内层条件更宽松乘积估算法就会低估那才是真正危险的方向。4. 就地修改的两类风险链表指针的顺序与洗牌的均匀性第 3 章的链表题和第 2 章的随机排列题在教材里分属两章但它们共享一个特征都在原数据结构上就地修改不允许开辟等量新空间。就地修改的代价是“中间状态”会短暂不满足不变量一旦某一步顺序写错结构就断了、或者分布就歪了。指针错误会立刻崩分布错误则悄无声息后者更难查。4.1 单链表交换相邻节点为什么参数必须是 beforeP3.2(a) 要求交换单链表中两个相邻节点。教材的答案把参数定为beforep也就是待交换的两个节点中前一个的前驱而不是直接传待交换的第一个节点// beforeP 指向两个待交换相邻节点的前驱p 与 afterP 均假定非 null public static void swapWithNext(Node beforeP) { Node p beforeP.next; Node afterP p.next; p.next afterP.next; // 1. p 跳过 afterP先接上后半段 beforeP.next afterP; // 2. 前驱改指 afterP afterP.next p; // 3. afterP 回指 p }三步的顺序是这段代码的全部难点。第一步必须先把p.next改成afterP.next因为一旦执行了第二步beforeP.next就不再指向 p如果此时还没保存afterP.next后半条链就永久丢失了。正确的思路是凡是会覆盖掉的指针先在覆盖前把它的值用掉或者存下来。这条规则在双向链表里会变得更啰嗦因为要覆盖的指针多了一倍。参数为什么必须是beforeP而不是p答案很直接单链表节点没有指向前驱的指针要修改前驱的next就必须持有前驱的引用。如果只传p在 O(1) 时间内根本无法找到它的前驱除非从头遍历一遍那样交换就退化成 O(N)。这里有个常见的替代方案值得对比不交换节点只交换两个节点里的data。这样只需要传p三行赋值就完事代码短得多。但它有一个隐蔽的副作用——如果外部代码持有这两个节点的引用交换数据之后那些引用的语义就悄悄变了原本指向节点 A 的变量现在读到的是 B 的值。在链表只被内部迭代器访问的场景下没问题一旦节点被缓存、被索引、被放进哈希表这个“假交换”就会翻车。教材选择交换节点而不是交换值是在为通用性付代价。4.2 双向链表的交换多出来的两次 prev 回写3.2(b) 的双向链表版本把参数改成了p本身因为双向链表能从p.prev直接拿到前驱。代价是指针赋值从三条变成六条// p 与 afterP 为待交换的两个相邻节点beforeP 是 p 的前驱 public static void swapWithNext(Node p) { Node beforeP p.prev; Node afterP p.next; p.next afterP.next; // 1. p 接上后半段 beforeP.next afterP; // 2. 前驱改指 afterP afterP.next p; // 3. afterP 回指 p p.next.prev p; // 4. 修后半段回指 p 的 prev p.prev afterP; // 5. p 的 prev 改成 afterP afterP.prev beforeP; // 6. afterP 的 prev 改成 beforeP }第 4 步依赖第 1 步的结果p.next已经被改成afterP.next所以这里的p.next.prev p修的是后半段那个节点的回指指针。如果第 1 步和第 4 步顺序颠倒p.next还是afterP这一行就会把afterP.prev错误地设成 p紧接着第 6 步又把它改成beforeP看起来结果碰巧对了但中间状态已经被污染一旦中间插入了别的操作比如在第 4、5 步之间回调了用户代码错误就会暴露。双向链表的不变量是对任意节点 x若 x.next 非空则 x.next.prev x。这个不变量可以用一个几行的检查函数兜住写完指针操作后立刻跑一遍比盯着代码看有效// 遍历检查双向链表的前后指针是否自洽可在每次指针操作后调用 static void assertLinkIntegrity(Node head) { for (Node x head; x ! null; x x.next) { if (x.next ! null x.next.prev ! x) { throw new AssertionError(prev/next mismatch at x); } } }这类断言在单测里开着、在生产里关掉是性价比很高的做法。指针类 bug 的特点是“写错一步崩在十步之外”等到崩的时候栈已经指向完全无关的位置回溯成本极高不如在每次修改后就近检查。4.3 洗牌的均匀性判据27 不能被 6 整除2.8 讨论三种随机排列算法。前两种都是“每次随机挑一个判重后再放”第三种是 Floyd 洗牌从后往前第 i 个位置与 [0, i] 之间的随机位置交换。教材特别指出如果把 Floyd 洗牌里的随机上界从 i 改成 n−1也就是每次都与全数组任意位置交换分布就不再均匀。它给的判据非常干净N 3 时三次交换各有 3 种随机取值共 3³ 27 条等概率的执行路径而 3 个元素的全排列只有 3! 6 种。27 不能被 6 整除所以不可能把 27 条路径平均分给 6 种排列必然有的排列被多映射、有的被少映射均匀性直接破掉。这个“路径总数必须能被结果数整除”的判据比跑一百万次统计频率快得多也更确定。// 正确的 Floyd 洗牌第 i 位只与 [0, i] 内的元素交换 static void shuffle(int[] a, Random rnd) { for (int i a.length - 1; i 0; i--) { int j rnd.nextInt(i 1); // 上界是 i1闭区间 [0, i] int t a[i]; a[i] a[j]; a[j] t; } } // 错误的写法上界写成 a.length每次都与全数组交换 // int j rnd.nextInt(a.length);正确版本的正确性可以用归纳证明处理到第 i 位时a[i]被设成从a[0..i]中均匀选出的一个元素剩下的a[0..i-1]仍然是原始集合的均匀随机排列递归下去每一位的边缘分布都是均匀的。错误版本破坏了“剩余集合”的封闭性——已经确定位置的后缀元素会被再次卷入交换均匀性在第一步就被稀释了。4.4 期望复杂度的推导N/(N−i) 从哪来三种算法的期望代价差别很大推导过程比结论更有价值。第一种算法在第 i 个位置填数时已有 i 个位置被占用随机命中未占用位置的概率是 (N−i)/N这是一次成功试验的几何分布期望试验次数就是 N/(N−i)。每次试验要扫描已填的 i 个位置判重花 O(i)所以总代价是 Σᵢ i·N/(N−i)。把求和换元令 k N−i可化为 N·Σ N/k 的量级结果是 O(N² log N)。第二种算法把判重方式从“线性扫描”换成“标记数组”每次试验的判重从 O(i) 降到 O(1)总代价变成 Σᵢ N/(N−i) N·H_NH_N 是调和数约等于 ln N于是 O(N log N)。这一项的改进完全来自数据结构的选择算法流程本身没变——这是“换个查找结构就能降一个量级”的经典案例。第三种 Floyd 洗牌只有一趟循环每次 O(1)总代价 O(N)。有意思的是它的最坏情况也是线性的无论随机数怎么取循环次数都是 N−1 次随机性只影响结果分布不影响执行时间。前两种算法的“最坏情况”则没有有限上界因为理论上随机数可以一直撞到已占用的位置只是概率趋近于 0。教材在这里点了一句关键区别那两种算法以概率 1 终止但不存在“最大运行时间”。工程含义很直接如果你的场景对延迟敏感比如服务端每次请求都要打乱一个小数组前两种“可能无限跑”的算法是不能用的哪怕期望值看起来还行Floyd 洗牌的确定性执行时间才是可交付的。4.5 Josephus 的取模优化M mod N 与反向等价3.6 的 Josephus 问题要求每次数 M 个删除一个。朴素做法是数 M 步但如果 M 远大于当前表长 N绕圈就是浪费。教材给的两个观察都很实用一是数 M 步等价于数 M mod N 步当前表长为 N二是当 M 超过 N/2 时向前数 M 步等价于向后数 N−M 步。第一个观察把复杂度里的 M 压到了 min(M, N)第二个观察在 M 接近 N 时再砍一半。合起来最坏复杂度是 O(N·min(M, N))但在 M 很大或接近 N 的常见参数下实际步数会比朴素实现少一个可观的常数。这里面没有玄学就是把“循环计数”换成“模运算”本质和环形缓冲区里用取模代替判断回绕是同一个思路。链表版本的 Josephus 要注意表长随删除动态变化每次删除后取模的基数都要更新写错这一步会导致下标错位删到不该删的节点。5. 避坑与排查五个最容易在习题里翻车的细节教材答案的正确率不等于照着抄就能跑对。下面五条是这份解答里最容易被误读、或者抄进代码就出问题的地方每条按现象、原因、解决写。5.1 算术与边界类坑一二分查找的递归区间不缩小程序不终止。现象是 2.31 里的情形——low 1, high 2时mid取 (12)/2 向下取整得 1递归调用依然是[1, 2]区间一点没变直接死循环。原因是向下取整的除法让 mid 可能等于 low如果递归分支写成search(mid, high)而不是search(mid1, high)区间就没有收缩。解决办法只有一条把 mid 算准之后保证两个分支里至少有一个端点被排除掉low mid 1或high mid − 1二选一并配一个low high的终止条件。坑二指数取模直接算幂中间结果溢出。2.10 要算 2¹⁰⁰ mod 5正确路径是利用 2⁴ ≡ 1 (mod 5)于是 2¹⁰⁰ (2⁴)²⁵ ≡ 1。如果直接Math.pow(2, 100)再取模double 的精度在 2⁵³ 之后就丢了得到的是个看似合理的错误答案。解决方式是全程在模意义下做乘法每一步都取模绝不让中间量超过模数的平方。坑三ones(n)传负数返回负数。现象是ones(-3)返回 −1 而不是 2。原因是 Java 的%保留被除数符号-3 % 2 -1累加下去自然是负的。解决方法是在入口加断言或者直接用Integer.bitCount(n)后者对负数按补码统计语义明确且是单条指令。5.2 指针与循环类坑四单链表交换顺序写反链断了但不报错。现象是交换后遍历只能走一半或者打印出重复节点。原因在 3.2 的三步里先改了beforeP.next才去读afterP.next此时后半段已经丢失但 Java 不会报错只是有个节点再也没人指向它。解决办法是把“先保存、后覆盖”当成硬规则并在每次结构修改后调用前一节给出的assertLinkIntegrity让错误在最近的位置暴露而不是等到几十行之后。坑五用循环层数相乘估复杂度把 O(N⁴) 写成 O(N⁵)。现象是分析结论比实际高一个量级导致明明能过的方案被误判为不可行。原因是把每层循环的上界直接相乘忽略了循环变量之间的依赖和if条件的过滤作用2.7 的第六段就是典型。解决办法是回到“每层实际执行次数”的定义先写出精确的求和式再化简实在拿不准就写个计数器跑几个规模采样看增长曲线落在哪个幂次上。采样不能替代证明但能立刻抓出量级错误。6. 设计取舍标准答案里的写法工程里该抄哪一半这份解答里的代码都是“教学正确”的写法不是“生产最优”的写法两者的差距集中体现在四个取舍上。第一个是递归与迭代。ones写成递归是为了展示规模递减快速幂写成递归是为了展示分治复用但真正落地的代码里这两处都该写成迭代——递归版的栈帧开销在小规模下看不出来在热路径上会被放大而且深递归在默认栈大小下有溢出风险。判断标准很简单如果递归的唯一收益是“代码短两行”那就换成循环只有当递归能表达出迭代难以表达的结构比如树的遍历、回溯时才值得付栈的代价。第二个是交换值与交换节点。3.2 选择交换节点代价是指针操作多、顺序敏感交换值只要三行但会在节点被外部持有时产生别名问题。我的取舍原则是看节点是否有“身份”如果节点只是容器值才是语义交换值完全够用如果节点本身被索引、被引用、被当作 map 的 key就必须交换节点否则会得到一批指向错乱数据的引用。第三个是均匀性与代价。Floyd 洗牌用一趟线性扫描换来了严格均匀和执行时间确定前两种算法靠拒绝采样省了证明却背上了“以概率 1 终止但无最坏上界”的包袱。在对延迟有承诺的系统里这个包袱不能背在离线批处理里拒绝采样的代码更短反而更不容易写错。均匀性判据路径数能否被排列数整除值得记住它能在你写出“看起来随机”的代码时第一时间报警。第四个是上界与紧界。大 O 给的是上界它保证“不会比这更慢”不保证“就是这么慢”。2.7 里 O(N⁵) 和 O(N⁴) 的差别、2.5 里摆动函数的存在都在提醒同一件事分析结论要区分“能证明的”和“实际发生的”。写文档时给上界是安全的做技术选型时必须拿到紧界或者实测数据否则容易把一个完全可行的方案误杀。我自己的习惯是每读完一道题的解答先合上答案把关键的三五行代码凭记忆重写一遍然后只做一件事——构造一个能让它出错的最小输入。ones(−3)、low1, high2的二分、上界写成n的洗牌这三个输入各自只需要几秒钟就能构造出来却分别戳破了三个“看起来没问题”的写法。从那以后我每次抄任何一段教材代码进项目都会先给它喂一个边界输入再谈别的。希望帮到你。本文还有配套的精品资源点击获取