《算法》第一章的这39道练习题是很多人在算法这条路上的第一道坎。我当年刷这套题的感受不是“难”而是“绕”——1.1.1这种题表面看是一行表达式实际考的是Java的类型转换和运算符优先级1.1.18这种函数长得像魔法拆开才发现是经典乘法算法的二进制版本。这套题的价值不在“做出答案”而在于把语言细节、递归思维、数组特性和随机性实验一次性揉进你的基础能力里。这篇博文按知识点把1.1.1到1.1.39完整过一遍每道题给出思路、可运行的Java代码以及我实际踩过的坑适合正在啃这本书的学生也适合想快速查漏补缺的开发者。1. 表达式与基本语法1.1.1-1.1.8先过语言关1.1 1.1.1到1.1.3求值、类型判断、输入比较1.1.1这类题目原题会给你几个表达式让你写出打印结果。常见的是这三类// a (0 15) / 2 // b 2.0e-6 * 100000000.1 // c true false || true truea的结果是7不是7.5。Java里两个整数相除直接截断小数部分这是很多刚从Python转过来的同学第一个踩的坑。b的结果是200.0000002浮点数运算是近似值不要指望精确相等。c的结果是true关键在运算符优先级的优先级高于||所以先算两边再算中间的或结果是false || true true。如果对优先级没把握直接加括号别靠记忆硬扛。1.1.2是类型升级和字符串拼接的经典陷阱(1 2.236) / 2 // 1.618 1 2 3 4.0 // 10.0 4.1 4 // true 1 2 3 // 33最后一行的结果不是数字6而是字符串33。Java的运算从左到右结合1 2先算出整数3再和字符串3拼接变成33。如果你写的是3 1 2结果是312因为第一个操作数已经定了字符串类型。前两行则是数值类型自动提升只要表达式中出现double整数会自动转成double再参与运算。1.1.3是第一个动手题从命令行接收三个整数都相等就打印equal否则打印not equal。这题考察的是命令行参数和Integer.parseInt的用法public class Equality { public static void main(String[] args) { int a Integer.parseInt(args[0]); int b Integer.parseInt(args[1]); int c Integer.parseInt(args[2]); System.out.println((a b b c) ? equal : not equal); } }我提醒一句话写多条件判断时永远别省掉、||两边的括号哪怕你觉得优先级很清楚。代码是写给人看的不是写给编译器过关的。1.2 1.1.4到1.1.5语法陷阱与边界判断1.1.4是一组语句正误判断题核心是Java里if语句的写法。常见的错误写法有这么几种if (a b) then c 0; // 错误Java没有then关键字 if (a b) { c 0; } // 正确 if (a b) c 0; // 正确单条语句可以省略花括号 if (a b) c 0; else b 0; // 正确这道题本身不难但我建议你把“有没有then”和“花括号加不加”这类细节当成语法清单背下来。很多后来写C#、JavaScript的同学在这道题上反复错不是因为脑子不好使而是因为别的语言的语法习惯带过来了。1.1.5要求判断两个double变量是否都严格位于0和1之间。直接写条件double x 0.05; double y 0.8; boolean ok (x 0 x 1 y 0 y 1);注意Java不支持0 x 1这种连写编译直接报错。另外题目要求“严格介于”那就不能带上等于号。边界条件在算法题里永远要单独问自己一句题目说的是open区间还是closed区间这道题答案是严格开区间写错等于白做。1.3 1.1.6到1.1.8循环输出与字符拼接1.1.6是经典的斐波那契生成程序原题给一段代码让你写出输出int f 0; int g 1; for (int i 0; i 15; i) { System.out.println(f); f f g; g f - g; }这段代码输出的是斐波那契数列的前16项0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610。它的巧妙之处在于没有使用临时变量用g f - g实现了一次性的双变量更新。这个写法在内存敏感的嵌入式代码里很常见值得记下来。1.1.7给三个循环段让你求输出。三段分别考牛顿迭代、双重循环计数和log循环计数。第一段是用牛顿法求9的平方根循环条件不断逼近最终t趋近于3.0第二段是sum i的双重循环结果是1到999的累加499500第三段外层i按1, 2, 4, 8, ..., 512翻倍共10轮内层每次加1000结果是10000。这题真正想让你掌握的是“数循环次数”而不是立刻跑代码。我有一次直接偷懒跑代码结果面试时候手算循环次数卡壳了后来就老实练手算。1.1.8是字符与字符串拼接的经典考题System.out.println(b); // b System.out.println(b c); // 197 System.out.println((char) (a 4)); // eb是字符打印出来是b但b c是两个char做加法升级成int运算98 99 197强转回char之后a 4 101对应字符e。这里真正的坑是System.out.println(b c)输出197而不是bc很多初学者把字符的加法当成字符串拼接。2. 数组与矩阵1.1.9-1.1.13、1.1.15把工具函数写熟练2.1 1.1.9-1.1.10进制转换与数组初始化1.1.9要求把正整数N转换成二进制字符串思路是反复除以2把余数往字符串头部追加int N Integer.parseInt(args[0]); String s ; for (int n N; n 0; n / 2) { s (n % 2) s; } System.out.println(s);有一个边界会被大多数人忽略N 0时循环不执行输出空字符串。正确做法是单独特判输出0。这道题背后其实考察了两个概念一是/和%的配合使用二是字符串的不可变性——每次n % 2) s都会创建一个新对象虽然在这道题里无所谓但后续写大字符串拼接时要想到用StringBuilder。1.1.10给了一段看起来没问题实际运行必炸的代码int[] a; for (int i 0; i 10; i) a[i] i * i;问题在于只是声明了int[] a没有用new int[10]初始化。Java数组声明之后并不会自动分配元素空间直接赋值会报空指针异常。我知道有些同学会在心里嘀咕“我明明只写错了一行怎么就空指针了”这就是Java和C语言的一个重大区别C里面数组一经声明就有栈空间Java里对象一律要到堆上分配。2.2 1.1.11-1.1.12二维数组打印与下标自引1.1.11要求打印二维布尔数组true用*表示false用空格表示。为了可读性最好带上行号列号boolean[][] a new boolean[5][5]; for (int i 0; i a.length; i) { for (int j 0; j a[i].length; j) { System.out.print(a[i][j] ? * : ); } System.out.println(); }一个小技巧用三元表达式? :直接代替if-else代码短很多输出对齐也方便。二维数组的行数用a.length列数用a[i].length交叉着用是这题的加分项。1.1.12给了一段数组自引用变换的代码让你推最终打印结果。这个题特别适合在纸上逐步画int[] a new int[10]; for (int i 0; i 10; i) a[i] 9 - i; for (int i 0; i 10; i) a[i] a[a[i]]; for (int i 0; i 10; i) System.out.println(a[i]);你绝对不能直接猜“倒过来再倒过来”因为第二层循环是原地修改后面的索引读取的是被改过的值。逐步模拟的结果是0, 1, 2, 3, 4, 4, 3, 2, 1, 0。看中间那两个4就知道了数组在索引4、5处会变得对称。这种题没有技巧老老实实画表格一画就清楚。2.3 1.1.13与1.1.15转置与直方图1.1.13要求把M行N列的二维数组转置成N行M列。核心就是行列互换int M a.length, N a[0].length; int[][] b new int[N][M]; for (int i 0; i M; i) for (int j 0; j N; j) b[j][i] a[i][j];转置题最容易犯的错是在原数组上原地交换。方阵可以靠swap(a[i][j], a[j][i])完成但非方阵的原地转置非常复杂还要处理未访问元素完全没有必要。老老实实开一个新数组逻辑清晰也不容易错。1.1.15是实现一个histogram函数接收int数组a和整数M返回长度M的数组第i个元素等于a中值为i的元素个数public static int[] histogram(int[] a, int M) { int[] h new int[M]; for (int v : a) { if (v 0 v M) h[v]; } return h; }这里一定要做越界判断。原题对超出[0, M)范围的值没有明确规定但常见做法是直接忽略。我写的时候加了这个判断后来测试大数据时发现确实有负数进来帮我省了不少调试时间。3. 递归专题1.1.16-1.1.20、1.1.22、1.1.24理解调用栈和终止条件3.1 1.1.16-1.1.17递归求值与常见的错误写法1.1.16是写出递归函数exR1(6)的返回值public static String exR1(int n) { if (n 0) return ; return exR1(n - 3) n exR1(n - 2) n; }这题的输出是311361142246。手工推的时候要按递归树展开exR1(6) exR1(3) 6 exR1(4) 6exR1(3) exR1(0) 3 exR1(1) 3 3 11 3 3113exR1(4) exR1(1) 4 exR1(2) 4 11 4 22 4 114224最后拼起来就是3113 6 114224 6 311361142246。递归题的精髓是永远先展开基础情形再往上回溯。很多人喜欢从n6往下猜那是自找麻烦。1.1.17是给一段几乎一样的递归但基础情形放错了位置public static String exR2(int n) { String s exR2(n - 3) n exR2(n - 2) n; if (n 0) return ; return s; }这段代码会无限递归下去因为String s exR2(...)这行在if (n 0)之前执行。我强调一下递归的两条底线第一基础情形必须在递归调用前判断第二每次递归调用都必须朝基础情形方向靠近。这两条在后续所有树的递归题里都适用现在不纠正后面写快排和二叉树会痛不欲生。3.2 1.1.18俄罗斯农民乘法1.1.18给了一个叫mystery的函数public static int mystery(int a, int b) { if (b 0) return 0; if (b % 2 0) return mystery(a a, b / 2); return mystery(a a, b / 2) a; }这个函数实现的是“俄罗斯农民乘法”本质是二进制的快速乘法。mystery(2, 25)的结果是50mystery(3, 11)的结果是33。它的逻辑是如果b是偶数就把a翻倍、b减半继续递归如果b是奇数额外加上一个a。我可以给你看一个追踪过程mystery(2, 25)先把25拆成二进制11001奇数位分别贡献2、8和16加起来正好是50。这个算法和快速幂是一对兄弟它们都是利用二进制展开把复杂度从O(n)降到O(log n)。原题后面问“如果把加法改成减法会怎样”你可以试试——答案是实现除法的基础这也是很多大整数库的底层思路。3.3 1.1.19-1.1.20斐波那契优化与ln(N!)1.1.19直击递归效率问题斐波那契的朴素递归实现F(N) F(N-1) F(N-2)N40就跑不动了因为调用次数是指数级增长。书里给出的建议是用循环或数组保存中间值public static long fib(int N) { long f 0, g 1; for (int i 0; i N; i) { long t f g; f g; g t; } return f; }这个题本身的答案很简单但它背后暴露了一个严重问题很多人能写出递归但意识不到递归的“性能账本”。斐波那契递归调用树里F(3)会被重复计算好多次缓存或者迭代是把指数变成线性的关键。我当年第一次跑N50的朴素递归等了半分钟都没出结果果断改成迭代秒出。从那以后我但凡看到递归都会下意识问一句有没有重复子问题1.1.20要求用递归计算ln(N!)也就是自然对数的阶乘。直接算阶乘再取对数N稍微大一点就会溢出或损失精度。正确思路是利用对数性质把乘法转成加法public static double lnFact(int N) { if (N 0) return 0; return Math.log(N) lnFact(N - 1); }这个解法看着简单但体现了一个数学直觉求和比求积稳定对数运算天然适合把阶乘降维。后续在概率计算里这种“先取对数再算”的手法会反复出现。3.4 1.1.22与1.1.24带输出的递归与欧几里得过程1.1.22要求给二分查找递归版本添加缩进输出让我们能看到每次lo和hi的区间变化。核心函数签名加上深度参数public static int rank(int key, int[] a, int lo, int hi, int depth) { for (int i 0; i depth; i) System.out.print( ); System.out.println(lo lo , hi hi); if (lo hi) return -1; int mid lo (hi - lo) / 2; if (key a[mid]) return rank(key, a, lo, mid - 1, depth 1); else if (key a[mid]) return rank(key, a, mid 1, hi, depth 1); else return mid; }这里我想强调一个细节mid lo (hi - lo) / 2而不是mid (lo hi) / 2。后者在lo和hi非常大时可能溢出前者不会。这个写法在很多面试题里是隐藏扣分点。1.1.24是欧几里得算法打印递归过程。我给函数加上输出public static int gcd(int p, int q) { System.out.println(gcd( p , q )); if (q 0) return p; return gcd(q, p % q); }题目让你算gcd(1111111, 1234567)打印过程会是gcd(1111111, 1234567) gcd(1234567, 1111111) gcd(1111111, 123456) gcd(123456, 7) gcd(7, 4) gcd(4, 3) gcd(3, 1) gcd(1, 0)最终结果是1。注意第一次调用时p小于q函数会先自动交换一次这是模运算的特性。欧几里得算法的收敛速度非常快平均情况下迭代次数是O(log min(p,q))这是为什么它至今仍是求最大公约数的主流算法。4. 查找与白名单应用1.1.21、1.1.23、1.1.28、1.1.29、1.1.384.1 1.1.21格式化表格输出1.1.21要求从标准输入读若干行每行包含名字和两个整数打印它们以及第一个数除以第二个数的结果保留三位小数。用教材配套库写起来很简洁while (!StdIn.isEmpty()) { String name StdIn.readString(); int x StdIn.readInt(); int y StdIn.readInt(); StdOut.printf(%-10s %8d %8d %8.3f\n, name, x, y, (double) x / y); }重点是(double) x / y这个强转。如果不转两个整数相除直接截断输出全是0.000。格式化字符串%-10s是左对齐%8.3f是保留三位小数且至少占8个字符宽。这类格式化输出在后续很多实验结果打印里都会用到建议直接背下来。4.2 1.1.23与1.1.28-1.1.29白名单、去重与等值键1.1.23是二分查找的客户端应用核心场景是从白名单里过滤数据读入一组键判断它是否在白名单数组里根据需求打印命中或不命中的键。实现上就是不断调用rank(key, a)然后根据返回值是否为-1决定输出。1.1.28要求对有序数组去重。因为数组已经有序重复元素一定相邻只需一趟遍历public static int[] removeDuplicates(int[] sorted) { int[] tmp new int[sorted.length]; int cnt 0; for (int v : sorted) { if (cnt 0 || tmp[cnt - 1] ! v) tmp[cnt] v; } return Arrays.copyOf(tmp, cnt); }方便的地方在于tmp[cnt-1]记录的是上一个没被跳过的元素所以每次只用和它比较一次。如果数组无序你就得先排序或者用哈希表那是后面章节的事。1.1.29是在有序数组上实现两个方法rank(key)返回小于key的元素个数count(key)返回等于key的元素个数。我直接用二分查找的变体——找左边界public static int rank(int key, int[] a) { int lo 0, hi a.length; while (lo hi) { int mid lo (hi - lo) / 2; if (a[mid] key) lo mid 1; else hi mid; } return lo; // 第一个 key 的下标也就是小于key的元素个数 } public static int count(int key, int[] a) { int left rank(key, a); int idx left; while (idx a.length a[idx] key) idx; return idx - left; }这里lo最终指向第一个不小于key的位置天然就是“小于key的元素个数”。不要小看这个边界写法它比普通二分查找的mid判定更不容易出错而且很多标准库的lower_bound用的就是这套逻辑。4.3 1.1.38暴力查找和二分查找到底差多远1.1.38的实验思路很直接准备一个有序数组对同一批查询键分别用顺序查找和二分查找测出总耗时。顺序查找实现就是遍历数组找相等的值二分查找用递归rank。我实际操作时用了System.nanoTime()来计时顺序查找在10万元素规模、10万次查询时已经明显卡顿而二分查找几乎瞬间完成。这里有个话要说明白复杂度不是“快一点”而是“数量级碾压”。顺序查找平均要比较 n/2 次二分查找只要 log2 n 次。n 1e6 时前者5万次比较后者20次相差2500倍。这还只是常数不是指数对线数。这道题做完你应该对“二分查找是O(log n)”这句话产生真正的体感而不是单纯背诵结论。5. 概率、随机性与模拟1.1.27、1.1.35-1.1.37、1.1.395.1 1.1.27二项分布递归的爆炸与优化1.1.27要求实现二项分布概率的递归计算。公式是public static double binomial(int N, int K, double p) { if (N 0 K 0) return 1.0; if (N 0 || K 0) return 0.0; return (1 - p) * binomial(N - 1, K, p) p * binomial(N - 1, K - 1, p); }这个递归在N100时直接爆炸因为重复状态太多了。书里给的建议是用数组保存中间计算结果也就是自顶向下的记忆化搜索或者干脆自底向上填表。public static double binomialDP(int N, int K, double p) { double[][] dp new double[N 1][K 1]; dp[0][0] 1.0; for (int i 1; i N; i) { dp[i][0] Math.pow(1 - p, i); for (int j 1; j K; j) { dp[i][j] (1 - p) * dp[i - 1][j] p * dp[i - 1][j - 1]; } } return dp[N][K]; }从这道题开始你就进入了“动态规划”的思考模式先看递归有没有重叠子问题有就缓存没有才是真递归。这个判断标准应该刻进脑子。5.2 1.1.35-1.1.37骰子概率与乱序质量检验1.1.35要求验证两个骰子点数之和的概率。理论分布可以直接用穷举算和为2的概率1/36和为7的概率6/36这是眼见的对称分布。然后用随机数模拟若干次把理论概率和模拟频率打印对比。模拟部分用Math.random()或者教材的StdRandom.uniform(1, 7)都行。我实验时发现模拟10万次之后频率基本贴着理论值模拟1000次时偏差还是肉眼可见。这道题告诉我们随机模拟的精度和样本量是平方根关系想精确到小数点后两位至少要上万次实验。1.1.36和1.1.37是乱序检查核心是验证洗牌算法是否均匀。做法是拿一个初始数组反复洗很多次统计每个元素在洗完后落到每个位置上的次数。如果是均匀洗牌每个格子次数应该大致相等。实现计数时需要一张二维表int n 10; int trials 1000; int[][] count new int[n][n]; for (int t 0; t trials; t) { int[] a new int[n]; for (int i 0; i n; i) a[i] i; // 这里替换成不同的shuffle算法 for (int i 0; i n; i) { int r i StdRandom.uniform(n - i); // 标准 Fisher-Yates int tmp a[i]; a[i] a[r]; a[r] tmp; } for (int i 0; i n; i) count[a[i]][i]; }标准Fisher-Yates的要点是r的取值范围是[i, n)只在未处理的区间里选。1.1.37里糟糕的乱序则是每次都在整个数组范围取随机下标比如r StdRandom.uniform(n)再和a[i]交换。表面看也随机实际上会把某些位置的元素以更高概率留在某些位置跑一遍1.1.36的统计表就能看到明显的不均匀条纹。我的实测结论是N10、试验3000次时标准版每格计数在300左右浮动有偏版某几格能差出一倍多。洗牌算法是最容易“看着对、其实错”的代码没有统计检验根本发现不了。5.3 1.1.39随机匹配实验的0.632经验值1.1.39是第一章的压轴实验生成两个长度N的随机数组元素都在[0, N)之间统计两个数组交集中的匹配数量对N 10^3、10^4、10^5、10^6分别做实验。标准做法是对第二个数组排序然后对第一个数组的每个元素做二分查找public static void main(String[] args) { int N Integer.parseInt(args[0]); int[] a randomArray(N); int[] b randomArray(N); Arrays.sort(b); int count 0; for (int v : a) { if (rank(v, b) 0) count; } StdOut.println(count); }实验结论非常稳定count/N大约在0.632附近徘徊和N的规模几乎无关。原因很简单对任意一个0到N-1之间的值v它出现在第二个数组中至少一次的概率是1 - (1 - 1/N)^N当N趋近无穷时这个值等于1 - 1/e ≈ 0.632。这个常数会让你后续在哈希表、布隆过滤器、随机抽样等场景里反复遇到。几乎每个第一次跑到这个数字的人都会惊讶但数学早已写好答案。6. 剩余零散题快速通关1.1.14、1.1.25、1.1.26、1.1.30、1.1.31-1.1.346.1 对数、gcd证明与三数排序1.1.14是实现一个不比用Math库的lg(N)返回不大于log2(N)的最大整数。一个可行的循环写法是public static int lg(int N) { int k 0; while (N 1) { N / 2; k; } return k; }注意N为0或负数时这个实现不适用原题限定了正整数。循环的次数就是N不断除以2直到变成1的次数这个思路和后面的二分查找次数计数一致。1.1.25是证明欧几里得算法的正确性属于理论题。核心是证明gcd(p, q) gcd(q, p % q)思路是p % q可以写成 p - kq任何同时整除p和q的数都能整除p - kq反过来任何同时整除q和p%q的数也能整除p所以两边的公因数集合完全相同。对这种证明我不会要求写得像数学系论文但至少要能说清楚“公因数集合相同”这个本质。1.1.26是给三个整数排序只能用交换语句。最常见的手法是三次if交换if (a b) { int t a; a b; b t; } if (b c) { int t b; b c; c t; } if (a b) { int t a; a b; b t; }这段代码的陷阱是第二次交换之后a可能又变得比b大了所以第三个if不能省。我每次看到“三个数排序”都不由自主想到这个问题写排序的时候你的变量是否始终满足局部不变量如果没有交换完还得复查一遍。6.2 互质矩阵与绘图题1.1.30要求生成一个NxN的布尔数组a[i][j]为true当且仅当i和j互质。实现要用到gcd函数直接复用1.1.24的思路boolean[][] a new boolean[N][N]; for (int i 0; i N; i) for (int j 0; j N; j) a[i][j] gcd(i, j) 1;这题有个隐含边界i或j为0时gcd(0, k) k所以a[0][1]是true、a[0][2]是falsea[0][0]要看你怎么定义。大多数实现会把gcd(0,0)当作0于是false。想清楚这一格其他都好说。1.1.31是随机连接图用教材的StdDraw画圆和连线。代码思路是先把N个点均匀放在圆周上然后对每一对点以概率p画线StdDraw.circle(0.5, 0.5, 0.4); double angle 2 * Math.PI / N; double[] x new double[N], y new double[N]; for (int i 0; i N; i) { x[i] 0.5 0.4 * Math.cos(angle * i); y[i] 0.5 0.4 * Math.sin(angle * i); } for (int i 0; i N; i) for (int j i 1; j N; j) if (StdRandom.bernoulli(p)) StdDraw.line(x[i], y[i], x[j], y[j]);N太大了线会密集到看不清我建议N20、p0.2体验一下看起来确实有“随机网络”的味道。1.1.32是画直方图本质是把标准输入的数据按区间分桶计数然后用StdDraw画矩形条核心还是一个“分段计数”的循环。6.3 矩阵库与过滤分类1.1.33是一个小型矩阵工具库要求实现向量点积、矩阵乘法、转置、矩阵乘向量、向量乘矩阵。我给出其中最常用的三个public static double dot(double[] x, double[] y) { double sum 0; for (int i 0; i x.length; i) sum x[i] * y[i]; return sum; } public static double[][] mult(double[][] a, double[][] b) { int m a.length, n b[0].length, inner b.length; double[][] c new double[m][n]; for (int i 0; i m; i) for (int j 0; j n; j) for (int k 0; k inner; k) c[i][j] a[i][k] * b[k][j]; return c; } public static double[][] transpose(double[][] a) { int m a.length, n a[0].length; double[][] t new double[n][m]; for (int i 0; i m; i) for (int j 0; j n; j) t[j][i] a[i][j]; return t; }矩阵乘法三层循环的边界条件经常写错我的经验是先在纸上写清楚输出矩阵的维度m x n然后确定最内层沿k遍历的是b矩阵的行数也就是a的列数。这个习惯能让你少调试半小时。1.1.34是一道判断题问哪些“过滤”操作必须把所有输入值保存在内存里才能完成。这里给一个速查结论操作是否必须保存所有值原因最大值否边读边更新最小值否边读边更新平均值否维护总和和计数标准差否维护平方和或在线方差中位数是需要全局有序信息排序后输出是必须整体有序随机选一个样本否蓄水池抽样这道题的意义在于引导你区分“流式算法”和“离线算法”。最大值、平均值都可以流式处理但中位数和排序不行。这个理解对后面的外部排序和流式计算场景特别有用。到这里1.1.1到1.1.39就全部过了一遍。我自己的体会是第一章最宝贵的不是某一道题的答案而是逼着你在“动手写代码”和“动手推过程”之间来回切换。1.1.12你推一下数组的原地变换胜过写十遍排序1.1.39你把0.632跑出来比背十遍期望公式都记得牢。这套题刷完之后你的语言细节、递归直觉、数组操作和随机实验能力会有一个整体提升后面进入栈、队列、排序和查找时你会明显感觉自己站得更稳了。