简介面向正在学习普林斯顿大学算法课程、准备编程作业或希望用 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 冒烟测试三个必跑的最小用例每个作业都有一组官方样例但全跑一遍太慢。第一轮只挑三个最小规模、边界规模、已知反例。作业最小规模边界反例Percolationinput1.txtn1必须 percolatesinput10.txtinput10-no.txt必须 falseCollinear Pointsinput8.txt2 条线段input6.txt含重复点的自定义输入8-Puzzlepuzzle04.txt4 步puzzle3x3-unsolvable.txt随机 25 步打乱跑 8-Puzzle 的不可解用例时要特别留意Solver.isSolvable()返回 false 时moves()和solution()必须抛UnsupportedOperationException或者返回 -1 / null具体看作业说明的措辞。这套解答按说明实现但不同年份的说明文字有出入用之前先核对当前版本的 API 文档。// 冒烟测试不依赖任何测试框架直接在 main 里断言 public static void main(String[] args) { // 用例 1n1 必然 percolates Percolation p1 new Percolation(1); p1.open(1, 1); assert p1.percolates() : n1 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*n1就自然落在并查集的合法区间里不用额外的偏移运算。参数上唯一需要小心的是n1open(1,1)会同时触发row 1和row n两套并查集分别把该点连到顶部和底部percolates()立刻返回 true这是符合定义的。noBackwash的容量是n*n1而不是n*n2因为它压根不需要底部虚拟点。这个细节省下的内存不多但能让不小心把 bottom 并进去的错误在编译期就不可能发生。3.2 Deque 与 RandomizedQueue常数项比复杂度更致命这两道题的算法难度接近于零挂在评分器上的几乎都是常数和边界。Deque用双向链表哨兵节点省掉头尾判空RandomizedQueue用可扩容数组dequeue()时把被删位置和末尾元素交换再缩容保证数组里没有 null 空洞。public class RandomizedQueueItem implements IterableItem { 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个位置永远没有 nulliterator()里就不需要写跳过 null 的分支——而那个分支恰恰是next()抛NoSuchElementException的高发地。第二缩容阈值取length/4而不是length/2避免在临界点反复扩容缩容的抖动。第三a[size] null那行删掉不会影响正确性但会让被删元素一直被数组引用着内存测试过不去。Deque那边同理链表的每个节点都是独立对象每个对象有 16 字节的对象头开销。作业的内存上限卡得很紧时链表实现可能比数组实现多吃一倍的堆这不是算法问题是常数问题。3.3 Collinear Points斜率排序如何避免输出子线段暴力解法四重循环n2000时是 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); ListLineSegment 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-PuzzleA* 的优先级函数与不可解判定A* 本身不难难的是三件事优先级函数必须是 admissible 的、必须做 critical optimization、必须能判定无解。优先级取moves manhattan。曼哈顿距离是 admissible 的每次移动最多把总距离减少 1所以第一次从优先队列弹出目标状态时就是最优解。critical optimization 指入队时不要把刚走过来的那个状态再放回去。少了这一步搜索树会指数级膨胀puzzle32.txt这种用例直接爆内存。public Solver(Board initial) { if (initial null) throw new IllegalArgumentException(null board); MinPQSearchNode pq new MinPQ(); MinPQSearchNode 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, j1)再从最后一行最小值往上回溯。写成递归记忆化也能过但栈深度到n的时候容易栈溢出迭代写更稳。4. 评分器到底在测什么时间、内存与 API 三项硬约束本地跑通不等于能拿分。评分器有三类检查每一类都有明确的阈值摸清阈值比优化代码更省时间。4.1 时间复杂度只看增长阶但常数决定生死评分器的时间检查本质是用倍增法测增长阶跑n和2n看耗时比值落在哪个区间。Percolation 的n200要求接近线性如果isFull()里写成了遍历整列找顶部连通比值会明显偏离。几个实际的量级参考作业测试规模期望增长阶经验耗时Percolationn 200O(n²) 总操作数百毫秒FastCollinearPointsn 2000O(n² log n)12 秒8-Puzzle4×425 步打乱A* 节点数秒级取决于启发式KdTree数十万点O(log n) 单次查询亚秒常数上最容易踩的是输出。解答里留一句StdOut.println做调试n200时打 40000 行光 I/O 就够超时了。提交前全局搜一遍System.out和StdOut。4.2 内存上限每个对象的固定开销评分器用-Xmx限制堆并且按n的倍数卡。Java 里每个对象有 16 字节头一个Point带两个int也要 24 字节左右如果用Integer装箱同样两个数变成两个对象加一个引用内存直接翻几倍。这就是 8-Puzzle 内存容易爆的根源Board每次neighbors()都新建 24 个棋盘每个棋盘内部若用int[][]是数组的数组每个子数组都是独立对象头开销累加。改成扁平的一维int[]加n字段内存能省下接近一半。本地测内存不用装 profiler加参数就行# 限制堆到 64MB跑通说明内存基本达标 java -Xmx64m -cp lib/algs4.jar:out Solver test/puzzle/puzzle20.txt4.3 API 契约签名、异常类型与不可变性API 检查是纯粹的形式检查但挂在这一项上的人不少。三条硬规则第一public 方法签名必须和说明里逐字一致包括参数名不影响、但返回类型和参数类型必须一致。多写一个 public 辅助方法会被判违规。第二异常类型必须精确。传入 null 要抛IllegalArgumentException不是NullPointerException空队列dequeue要抛NoSuchElementException不是IllegalStateException。这套解答按说明实现但不同年份的措辞有出入用之前核对当前版本。第三不可变类必须真的不可变。Board和Point都要求不可变如果构造时直接持有外部传入的数组引用调用方改数组内容你的对象就变了。构造函数里做一次防御性拷贝。注意Point的compareTo必须先比 y 再比 x。写反了在 Collinear 里不会立刻报错只会让输出的线段端点顺序错乱属于典型的看起来能跑但结果不对。5. 避坑与排查五条踩过的记录这一章是整套解答里最值钱的部分。下面五条都是现象明确、原因单一、解决起来很快的问题但不知道的话能卡一整天。5.1 本地三秒跑完提交后报时间超限现象本地用官方样例跑得好好的注释里写着n200也就几百毫秒提交后返回 timing limit exceeded。原因本地样例的n太小测不出增长阶。评分器会跑到n200甚至更大而代码里某个操作是 O(n) 的总复杂度悄悄退化成 O(n³)。Percolation 里最常见的写法是通过遍历整列来判断某格是否与顶部连通单个调用 O(n)加上open()里对四个邻居各调一次整体就爆了。解决把isFull()改成并查集查一次连通性O(α(n))。改完再用n200自己生成随机输入实测别只信样例。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结果n1的边界用例把一个未处理的数组越界藏了整整两天——样例里根本没有n1。从那以后我每次改完任何一道题的实现都强制走一遍最小规模 边界 随机倍增三件套跑完才允许自己点提交。希望帮到你。本文还有配套的精品资源点击获取