Java算法编程作业解答：从并查集到A*的避坑与自测

简介：面向正在学习普林斯顿大学算法课程、准备编程作业或希望用 Java 夯实数据结构与算法基础的读者，这份项目提供课程编程习题的参考解答，可用于对照题意梳理实现思路、验证结果并复盘常见错误。压缩包共 20 个文件，以 18 个 Java 源码为核心，另含 1 个 Markdown 说明和 1 个许可证文件，整体约 28KB，体量轻便，便于按主题查阅和本地运行。已有 245 人学习下载。内容围绕排序与搜索、图算法、动态规划、基础及高级数据结构展开，并涉及面向对象编程、异常处理、集合框架与时间/空间复杂度分析；读者可从中理解如何把算法分析落到 Java 实现，借助调试与对照练习提升独立完成课程作业和应对算法面试的能力。

1. 从一道卡在时间限制上的作业说起：这套 Java 解答能省下什么

算法课的编程作业，最容易出问题的不是思路，而是细节：并查集少开一个虚拟点，isFull()就把底部的连通性也算进来；A* 少一个剪枝，内存直接超限。这份资源是一套完整的 Java 编程作业解答集合，对应某高校算法公开课的 Part I 与 Part II 全部编程题，覆盖 Percolation、Deque、Collinear Points、8-Puzzle、Kd-Tree、WordNet、Seam Carving、Boggle、Burrows-Wheeler 等题目。每个题目给出可直接编译运行的实现，以及配套的本地测试入口。适合两类人：跟着课程做作业卡在某个测试用例上的，以及想对照一份工业级风格 Java 实现来校准自己代码的。下面按“跑通、读懂、避坑、自测”的顺序拆。

2. 拿到解答先跑通：目录结构、classpath 与第一轮冒烟

这套解答不是一堆散落的.java，而是按作业题目分目录组织的。直接双击打开 IDE 往往能跑通单个文件，但一端到课程提供的测试客户端上就开始报NoClassDefFoundError。原因基本集中在两处：课程标准库没挂进 classpath，以及解答文件带了包声明而运行命令没带对应的包路径。

2.1 解答包的目录结构与文件职责

常见做法是下面这种扁平结构，每个作业一个目录，测试数据和解答分开：

algs-solutions/ ├── lib/ │ └── algs4.jar # 课程标准库，提供 StdIn/StdOut/In/Stopwatch 等 ├── out/ # 编译产物，别和源码混在一起 ├── test/ # 各题官方样例输入 │ ├── percolation/ │ │ ├── input10.txt │ │ └── input10-no.txt │ ├── collinear/ │ │ └── input8.txt │ └── ... └── src/ ├── Percolation.java ├── Deque.java ├── RandomizedQueue.java ├── Permutation.java ├── Point.java ├── LineSegment.java ├── BruteCollinearPoints.java ├── FastCollinearPoints.java ├── Board.java ├── Solver.java ├── KdTree.java └── ...

把编译产物单独放到out/不是为了好看。后面做性能基线的时候，要靠javac -d保证每次都是干净重编，避免用旧 class 文件测出来的时间骗自己。源码目录里不要出现package语句——多数课程作业的评分器默认提交的是默认包下的类，加了包声明本地能跑，提交上去就是找不到类。

提示：如果从 IDE 新建工程导入，先把 IDE 自动生成的module-info.java和package行删掉，再把lib/algs4.jar加到模块依赖里，否则会出现同名类在两个 classpath 条目里冲突的怪现象。

2.2 编译运行：把课程库挂进 classpath

命令行是最不容易出问题的方式，-cp里同时放课程库和编译输出目录，Windows 上分隔符是;：

cd algs-solutions # 1) 干净重编，所有类落到 out/ javac -encoding UTF-8 -cp "lib/algs4.jar" -d out src/*.java # 2) 冒烟：用官方样例喂给 Percolation 的交互式测试客户端 java -cp "lib/algs4.jar:out" Percolation < test/percolation/input10.txt

第一步里-encoding UTF-8不是可选项。解答里的注释和部分输出是中文，在默认 GBK 的终端里编译会直接报unmappable character，报错行号还会飘。

第二步的-cp顺序有讲究：课程库在前，自己的out在后。如果把out放前面，而你的src里恰好有一份自己写的同名工具类，就会覆盖课程库的实现，跑出来的结果和评分器不一致，这种问题极难定位。

Percolation这个类本身不是为读标准输入写的，上面这条命令只是验证类能加载、静态初始化不炸。真正验证逻辑要用课程给的测试客户端，见下一节。

2.3 冒烟测试：三个必跑的最小用例

每个作业都有一组官方样例，但全跑一遍太慢。第一轮只挑三个：最小规模、边界规模、已知反例。

跑 8-Puzzle 的不可解用例时要特别留意：Solver.isSolvable()返回 false 时，moves()和solution()必须抛UnsupportedOperationException或者返回 -1 / null，具体看作业说明的措辞。这套解答按说明实现，但不同年份的说明文字有出入，用之前先核对当前版本的 API 文档。

// 冒烟测试：不依赖任何测试框架，直接在 main 里断言 public static void main(String[] args) { // 用例 1：n=1 必然 percolates Percolation p1 = new Percolation(1); p1.open(1, 1); assert p1.percolates() : "n=1 should percolate"; assert p1.numberOfOpenSites() == 1; // 用例 2：边界索引必须抛异常，而不是静默返回 false try { p1.isOpen(0, 1); throw new AssertionError("expected IllegalArgumentException"); } catch (IllegalArgumentException expected) { // 符合预期 } }

这段的关键在第二个用例。很多解答只保证了正常路径正确，越界时返回false而不是抛IllegalArgumentException，评分器的 API 检查会直接把这一项判掉。参数说明：assert需要java -ea才生效，所以运行命令要写成java -ea -cp ...，漏掉-ea的话所有断言都是空转，看起来"全绿"其实什么都没测。

3. 五个高频作业的实现骨架：从并查集到 A*

中间这几道题是整套解答里最值得对照阅读的部分，因为它们各自代表一种典型的"复杂度够用但常数要命"的场景。下面挑五个，把关键实现和取舍讲清楚。

3.1 Percolation：加权并查集与"回渗"的第二套集合

这道题的核心陷阱是回渗（backwash）。如果只用一个并查集，上下各挂一个虚拟点，那么当系统渗流之后，从底部虚拟点连通上来的空格子会被isFull()误判为"与顶部连通"，而那格水其实永远流不到。

解法是维护两套并查集：一套带上下两个虚拟点，只用来回答percolates()；另一套只带上虚拟点，用来回答isFull()。

public class Percolation { private final int n; private final boolean[] open; // 1-based 扁平化：idx = (row-1)*n + col private final WeightedQuickUnionUF uf; // 含上下虚拟点，判 percolates private final WeightedQuickUnionUF noBackwash; // 只含上虚拟点，判 isFull private final int top, bottom; private int openSites; public Percolation(int n) { if (n <= 0) throw new IllegalArgumentException("n must be positive"); this.n = n; this.open = new boolean[n * n + 1]; this.uf = new WeightedQuickUnionUF(n * n + 2); this.noBackwash = new WeightedQuickUnionUF(n * n + 1); this.top = n * n; this.bottom = n * n + 1; } private void check(int row, int col) { if (row < 1 || row > n || col < 1 || col > n) throw new IllegalArgumentException("index out of bounds"); } public void open(int row, int col) { check(row, col); int p = (row - 1) * n + col; if (open[p]) return; // 重复 open 不增加计数 open[p] = true; openSites++; if (row == 1) { uf.union(p, top); noBackwash.union(p, top); } if (row == n) { uf.union(p, bottom); } // 注意：这里不并进 noBackwash int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int r = row + d[0], c = col + d[1]; if (r < 1 || r > n || c < 1 || c > n) continue; int q = (r - 1) * n + c; if (open[q]) { uf.union(p, q); noBackwash.union(p, q); } } } public boolean isOpen(int row, int col) { check(row, col); return open[(row - 1) * n + col]; } public boolean isFull(int row, int col) { check(row, col); int p = (row - 1) * n + col; return open[p] && noBackwash.connected(p, top); } public int numberOfOpenSites() { return openSites; } public boolean percolates() { return uf.connected(top, bottom); } }

逻辑说明：open数组用一维扁平化存储，索引从 1 开始，索引 0 空置，这样top = n*n和bottom = n*n+1就自然落在并查集的合法区间里，不用额外的偏移运算。参数上唯一需要小心的是n=1：open(1,1)会同时触发row == 1和row == n，两套并查集分别把该点连到顶部和底部，percolates()立刻返回 true，这是符合定义的。

noBackwash的容量是n*n+1而不是n*n+2，因为它压根不需要底部虚拟点。这个细节省下的内存不多，但能让"不小心把 bottom 并进去"的错误在编译期就不可能发生。

3.2 Deque 与 RandomizedQueue：常数项比复杂度更致命

这两道题的算法难度接近于零，挂在评分器上的几乎都是常数和边界。Deque用双向链表，哨兵节点省掉头尾判空；RandomizedQueue用可扩容数组，dequeue()时把被删位置和末尾元素交换再缩容，保证数组里没有 null 空洞。

public class RandomizedQueue<Item> implements Iterable<Item> { private Item[] a = (Item[]) new Object[2]; private int size; public void enqueue(Item item) { if (item == null) throw new IllegalArgumentException("null item"); if (size == a.length) resize(a.length * 2); a[size++] = item; } public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("queue is empty"); int i = StdRandom.uniformInt(size); Item val = a[i]; a[i] = a[--size]; // 用末尾元素填洞，保证 [0, size) 连续 a[size] = null; // 断开引用，避免对象滞留 if (size > 0 && size == a.length / 4) resize(a.length / 2); return val; } private void resize(int cap) { Item[] tmp = (Item[]) new Object[cap]; for (int i = 0; i < size; i++) tmp[i] = a[i]; a = tmp; } }

三个关键点。第一，a[i] = a[--size]这一步是"用末尾填洞"，它保证了数组前size个位置永远没有 null，iterator()里就不需要写跳过 null 的分支——而那个分支恰恰是next()抛NoSuchElementException的高发地。第二，缩容阈值取length/4而不是length/2，避免在临界点反复扩容缩容的抖动。第三，a[size] = null那行删掉不会影响正确性，但会让被删元素一直被数组引用着，内存测试过不去。

Deque那边同理，链表的每个节点都是独立对象，每个对象有 16 字节的对象头开销。作业的内存上限卡得很紧时，链表实现可能比数组实现多吃一倍的堆，这不是算法问题，是常数问题。

3.3 Collinear Points：斜率排序如何避免输出子线段

暴力解法四重循环，n=2000时是 1.6×10¹³ 次比较，必挂。正解是对每个点p，把其余点按相对p的斜率排序，然后在有序数组里扫出斜率相同的连续段，长度 ≥ 3 就是共线。

真正的难点是去重：四个共线点从每一个点出发都能扫出一段，直接加进去会得到 4 条互相包含的线段，评分器要求只输出极大线段。

public FastCollinearPoints(Point[] points) { if (points == null) throw new IllegalArgumentException("null array"); Point[] copy = points.clone(); for (Point p : copy) if (p == null) throw new IllegalArgumentException("null point"); Arrays.sort(copy); // 先按坐标排，相邻相同即为重复点 for (int i = 1; i < copy.length; i++) if (copy[i].compareTo(copy[i - 1]) == 0) throw new IllegalArgumentException("duplicate points"); List<LineSegment> segs = new ArrayList<>(); for (Point p : copy) { Point[] others = copy.clone(); Arrays.sort(others, p.slopeOrder()); // 只按斜率排，不破坏原顺序 int j = 1; while (j < others.length) { int k = j; double s = p.slopeTo(others[j]); while (k < others.length && Double.compare(p.slopeTo(others[k]), s) == 0) k++; if (k - j >= 2) { // 同斜率除 p 外至少 3 个点 Point min = p, max = p; for (int t = j; t < k; t++) { if (others[t].compareTo(min) < 0) min = others[t]; if (others[t].compareTo(max) > 0) max = others[t]; } // 只从该共线集合里坐标最小的点出发，保证每条极大线段只被记录一次 if (min.compareTo(p) == 0) segs.add(new LineSegment(min, max)); } j = k; } } this.segments = segs; }

逻辑说明：min.compareTo(p) == 0是整个去重策略的核心。一条极大线段上有若干点，只有从其中坐标最小的那个点出发扫描时才会记录，其余点出发时min都小于p，直接跳过。

参数上要注意斜率比较用Double.compare而不是==。竖直线段的斜率是Double.POSITIVE_INFINITY，两个无穷大用==比较碰巧能过，但-0.0和0.0用==会判等而Double.compare判不等，反过来NaN用==永远 false。用Double.compare至少保证行为和Arrays.sort的排序结果一致，避免"排序认为相同、扫描认为不同"的错位。

3.4 8-Puzzle：A* 的优先级函数与不可解判定

A* 本身不难，难的是三件事：优先级函数必须是 admissible 的、必须做 critical optimization、必须能判定无解。

优先级取moves + manhattan。曼哈顿距离是 admissible 的（每次移动最多把总距离减少 1），所以第一次从优先队列弹出目标状态时就是最优解。

critical optimization 指：入队时不要把"刚走过来的那个状态"再放回去。少了这一步，搜索树会指数级膨胀，puzzle32.txt这种用例直接爆内存。

public Solver(Board initial) { if (initial == null) throw new IllegalArgumentException("null board"); MinPQ<SearchNode> pq = new MinPQ<>(); MinPQ<SearchNode> pqTwin = new MinPQ<>(); pq.insert(new SearchNode(initial, 0, null)); pqTwin.insert(new SearchNode(initial.twin(), 0, null)); // 交换两个相邻块得到孪生 SearchNode goal = null; while (!pq.isEmpty()) { SearchNode cur = pq.delMin(); if (cur.board.isGoal()) { goal = cur; break; } // 孪生盘面同步搜索：任一方先到目标即可判定可解性 SearchNode twinCur = pqTwin.delMin(); if (twinCur.board.isGoal()) { goal = null; break; } for (Board next : cur.board.neighbors()) { // critical optimization：跳过父节点，避免来回震荡 if (cur.prev != null && next.equals(cur.prev.board)) continue; pq.insert(new SearchNode(next, cur.moves + 1, cur)); } for (Board next : twinCur.board.neighbors()) { if (twinCur.prev != null && next.equals(twinCur.prev.board)) continue; pqTwin.insert(new SearchNode(next, twinCur.moves + 1, twinCur)); } } ... }

SearchNode里的priority要缓存成 final 字段，在构造时算一次。如果在compareTo里现算board.manhattan()，每次堆比较都要遍历一遍棋盘，puzzle32的时间会翻好几倍——这是这套解答里最容易被忽略的性能细节。

不可解判定用孪生盘面：把一个盘面的两个相邻非空格交换，得到的孪生盘面与原盘面一个可解一个不可解。两个同时搜，谁先到目标就知道原盘面可不可解。注意twin()不能固定交换前两个格子，那两个格子可能有一个是空格，交换后还是原盘面，判定直接失效。

3.5 Kd-Tree 与 Seam Carving：剪枝与拓扑序

Kd-Tree 的三问（contains、range、nearest）里，nearest是唯一需要剪枝的。递归下降时维护当前最近距离best，回溯前用查询点到矩形边界的最小距离平方去比，比best大就直接剪掉整棵子树。

private void nearest(Node node, Point target, Rect rect, Point[] best, double[] bestDist) { if (node == null) return; double d = target.distanceSquaredTo(node.point); if (d < bestDist[0]) { bestDist[0] = d; best[0] = node.point; } // 查询点落在分割线哪一侧，先去那一侧 boolean left = node.point.x() > target.x() ... // 用矩形距离平方剪枝，别用开方，浮点开方既慢又可能引入误差 if (rect.distanceSquaredTo(target) >= bestDist[0]) return; }

矩形距离用平方，全程不开根号。这不只是性能问题，Math.sqrt在临界情况下可能把"相等"算成"略大"，导致明明该剪的没剪、或者该访问的被剪掉。

Seam Carving 那题的关键是找竖直缝的顺序。每个像素的能量只依赖上下左右四个邻居，所以按行从上到下做一遍动态规划就是天然的拓扑序，不需要显式建图。energy[i][j] = 原能量 + min(上一行 j-1, j, j+1)，再从最后一行最小值往上回溯。写成递归记忆化也能过，但栈深度到n的时候容易栈溢出，迭代写更稳。

4. 评分器到底在测什么：时间、内存与 API 三项硬约束

本地跑通不等于能拿分。评分器有三类检查，每一类都有明确的阈值，摸清阈值比优化代码更省时间。

4.1 时间复杂度：只看增长阶，但常数决定生死

评分器的时间检查本质是用倍增法测增长阶：跑n和2n，看耗时比值落在哪个区间。Percolation 的n=200要求接近线性，如果isFull()里写成了遍历整列找顶部连通，比值会明显偏离。

几个实际的量级参考：

常数上最容易踩的是输出。解答里留一句StdOut.println做调试，n=200时打 40000 行，光 I/O 就够超时了。提交前全局搜一遍System.out和StdOut。

4.2 内存上限：每个对象的固定开销

评分器用-Xmx限制堆，并且按n的倍数卡。Java 里每个对象有 16 字节头，一个Point带两个int也要 24 字节左右；如果用Integer装箱，同样两个数变成两个对象加一个引用，内存直接翻几倍。

这就是 8-Puzzle 内存容易爆的根源：Board每次neighbors()都新建 2～4 个棋盘，每个棋盘内部若用int[][]，是"数组的数组"，每个子数组都是独立对象，头开销累加。改成扁平的一维int[]加n字段，内存能省下接近一半。

本地测内存不用装 profiler，加参数就行：

# 限制堆到 64MB，跑通说明内存基本达标 java -Xmx64m -cp "lib/algs4.jar:out" Solver < test/puzzle/puzzle20.txt

4.3 API 契约：签名、异常类型与不可变性

API 检查是纯粹的形式检查，但挂在这一项上的人不少。三条硬规则：

第一，public 方法签名必须和说明里逐字一致，包括参数名不影响、但返回类型和参数类型必须一致。多写一个 public 辅助方法会被判违规。

第二，异常类型必须精确。传入 null 要抛IllegalArgumentException，不是NullPointerException；空队列dequeue要抛NoSuchElementException，不是IllegalStateException。这套解答按说明实现，但不同年份的措辞有出入，用之前核对当前版本。

第三，不可变类必须真的不可变。Board和Point都要求不可变，如果构造时直接持有外部传入的数组引用，调用方改数组内容，你的对象就变了。构造函数里做一次防御性拷贝。

注意：Point的compareTo必须先比 y 再比 x。写反了在 Collinear 里不会立刻报错，只会让输出的线段端点顺序错乱，属于典型的"看起来能跑但结果不对"。

5. 避坑与排查：五条踩过的记录

这一章是整套解答里最值钱的部分。下面五条都是现象明确、原因单一、解决起来很快的问题，但不知道的话能卡一整天。

5.1 本地三秒跑完，提交后报时间超限

现象：本地用官方样例跑得好好的，注释里写着n=200也就几百毫秒，提交后返回 "timing limit exceeded"。

原因：本地样例的n太小，测不出增长阶。评分器会跑到n=200甚至更大，而代码里某个操作是 O(n) 的，总复杂度悄悄退化成 O(n³)。Percolation 里最常见的写法是通过遍历整列来判断某格是否与顶部连通，单个调用 O(n)，加上open()里对四个邻居各调一次，整体就爆了。

解决：把isFull()改成并查集查一次连通性，O(α(n))。改完再用n=200自己生成随机输入实测，别只信样例。

5.2 RandomizedQueue 的next()偶发空指针

现象：iterator()遍历时随机抛NullPointerException，重跑一次可能不复现，看着像玄学。

原因：dequeue()只写了a[i] = null而没有把末尾元素搬过来填洞，数组中间出现空洞。iterator()直接按下标从 0 走到size，读到 null 就炸。另一种写法是保留空洞但在next()里跳过 null，那样更糟——hasNext()和next()的计数会对不上。

解决：按 3.2 的写法，用末尾元素填洞，保证[0, size)区间连续无空。这条改完以后iterator()里不需要任何 null 判断。

5.3 8-Puzzle 本地能出解，提交后内存超限

现象：puzzle32.txt本地跑半分钟能出结果，提交直接判内存超限。

原因：漏了 critical optimization。A* 每次扩展都把父节点对应的盘面重新入队，搜索在两个状态之间来回震荡，优先队列里的节点数呈指数增长。加上默认的Manhattan已经 admissible，问题不在启发式，在入队条件。

解决：入队前判断next.equals(cur.prev.board)，相等就跳过。另外在SearchNode构造时把priority = moves + board.manhattan()算好存成字段，compareTo里直接比字段，省掉每次堆比较重算曼哈顿距离的开销。

5.4 Collinear Points 的输出里混进了子线段

现象：input8.txt期望输出 2 条线段，实际输出 4 条甚至更多，每条都是期望线段的一部分。

原因：没有做"只从最小点出发"的去重。四个共线点会从每个点出发各扫出一段，各自都被判定为长度 ≥ 3，于是全部入列。

解决：扫描出同斜率段后，先求出段内最小点和最大点，只有当前起点p等于最小点时才记录。另外重复点必须在构造函数第一行检查并抛IllegalArgumentException，用排序后相邻比较比HashSet稳，因为Point的equals和hashCode要自己实现，写漏了hashCode去重就失效。

5.5 "could not find or load main class" 类错误

现象：编译没有任何报错，out/下也确实生成了.class，一运行就报找不到主类。

原因：三个可能，按概率从高到低。一是源码顶部有package xxx;而运行时没加对应的包路径；二是-cp里只写了lib/algs4.jar忘了加out；三是 Windows 下用了:做分隔符，实际需要;。

解决：先javac -d out src/*.java编译，再确认ls out/里直接是.class文件而不是一个子目录。如果是子目录，说明源码里有package声明，删掉。然后核对-cp完整包含课程库和out两段。这三个检查做完基本就通了，剩下的是 JDK 版本问题——课程库是按 Java 8 编译的，用 17 以上版本跑可能遇到模块系统限制。

6. 自己造数据与对拍：把"能过样例"变成"敢改代码"

官方样例就那么几个，改完代码只跑样例，很容易出现"样例过了、随机数据崩了"。我一般会给每道题配一个生成器和一个计时壳，改完立刻跑一轮。

生成器用 Python 写最省事，输出直接喂给 Java 程序的标准输入：

# 生成 Percolation 的随机输入：第一行 n，随后 n 行 0/1 import random, sys n = int(sys.argv[1]) if len(sys.argv) > 1 else 200 p = float(sys.argv[2]) if len(sys.argv) > 2 else 0.6 random.seed(20240101) # 固定种子，保证两次跑的是同一份数据 print(n) for _ in range(n): print(''.join('1' if random.random() < p else '0' for _ in range(n)))

固定随机种子这一行别省。不固定的话，出了错没法复现，只能靠猜；固定之后，同一个n和p每次给的数据完全一样，性能对比才有意义。

计时壳直接写在解答的main里，跑完打印一句耗时：

public static void main(String[] args) { In in = new In(args[0]); int n = in.readInt(); boolean[][] grid = new boolean[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) grid[i][j] = in.readInt() == 1; long t0 = System.nanoTime(); Percolation p = new Percolation(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (grid[i][j]) p.open(i + 1, j + 1); // 注意 1-based 转换 long ms = (System.nanoTime() - t0) / 1_000_000; StdOut.printf("n=%d percolates=%b time=%dms%n", n, p.percolates(), ms); }

把n从 50 一路倍增到 400，看耗时的比值。理论上n翻倍耗时该接近 4 倍（操作数是 n²），如果实测接近 8 倍，说明有隐藏的 O(n) 操作没消掉，回去查isFull()和邻居遍历里有没有循环。这套倍增法比凭感觉判断靠谱得多，也比等评分器返回结果快。

最后说个血泪教训。我早期图省事，改完代码只跑input10.txt，结果n=1的边界用例把一个未处理的数组越界藏了整整两天——样例里根本没有n=1。从那以后，我每次改完任何一道题的实现，都强制走一遍"最小规模 + 边界 + 随机倍增"三件套，跑完才允许自己点提交。希望帮到你。

本文还有配套的精品资源，点击获取