简介普林斯顿大学算法课程编程作业的Java完整解答面向正在学习algs4课程或准备算法面试的开发者。压缩包共20个文件核心是18个Java源文件覆盖Percolation、Deque、RandomizedQueue、PointSET、KdTree、WordNet、SeamCarver、8puzzle、Collinear等经典命题另附README说明与LICENSE授权包体仅28KB结构紧凑便于按作业模块查阅。已有243人学习下载适合想对照参考、理解算法细节的进阶学习者。每份解答均针对课程官方作业要求编写包含数据结构的选用与边界处理思路可帮助读者快速定位自身实现中的问题深入掌握排序搜索、图算法、动态规划及红黑树等核心内容是一份实用的算法刷题与复习资料。1. 先看答案再谈算法algs4 编程习题解答到底能帮到你什么algs4 是普林斯顿大学在 Coursera 上开放的经典算法课配套的编程作业Programming Assignment不是「给你一个样例、跑通就收工」的题目——每一道都要提交到自动评测上既卡正确性又卡时间与空间有的作业甚至会因为多 new 了一个数组直接扣分。这套 Java 编程习题解答把课程十个作业完整走了一遍从并查集、随机队列到 Burrows-Wheeler 压缩每一份都按课程规定接口写好能直接编译跑分。适合两类人一类是正在选课、被作业卡住想找参考实现的同学另一类是准备算法面试、想把基础算法在真实约束下跑一遍的工程师。知道它是什么、能解决什么之后接下来先从作业体系说起。2. 作业体系与评判机制先搞清楚什么算「过」2.1 十个作业背后的算法地图Coursera 上这门课分两个部分。Part 1 的编程作业按顺序是Percolation渗透模型并查集、Deques and Randomized Queues双端队列与随机队列、Collinear Points共线点排序与比较器、8 Puzzle八数码A* 搜索、Kd-TreesKd 树空间索引。Part 2 则是 WordNet有向图与最短公共祖先、Seam Carving动态规划与图像缩放、Baseball Elimination最大流归约、BoggleTrie 与 DFS、Burrows-Wheeler字符串压缩变换。这套解答基本覆盖了全部题目并且遵循每个作业的接口约束。作业与作业之间不是孤立的。Percolation 训练并查集8 Puzzle 用上优先队列和曼哈顿距离Kd-Trees 又依赖 BST 的递归思维到了 Part 2 的 WordNet 还要把图算法和前面的知识结合。如果你只看单个作业答案容易漏掉课程本身的设计逻辑它是想让你在每个作业里反复练习「选数据结构」和「分析复杂度」这两件事。所以我建议拿到这套解答后不要只挑当前卡住的作业看而是先把每个作业的算法点扫一遍有了整体认知再深入。作业核心数据结构主要考察点PercolationWeightedQuickUnionUF并查集、backwashDeques and Randomized Queues动态数组均摊分析、扩容缩容Collinear Points排序数组比较器、去重8 Puzzle优先队列A* 搜索、曼哈顿距离Kd-TreesBST递归、空间剪枝WordNet有向图最短公共祖先、拓扑排序Seam Carving二维数组动态规划、能量计算Baseball Elimination最大流网络流归约BoggleTrieDFS 回溯、字符串匹配Burrows-Wheeler循环后缀数组压缩变换、基数排序2.2 本地跑分三件事编译、样例、自测脚本几乎所有作业都自带一个样例文件和一个可视化工具。常见做法是先把作业解压到一个独立目录然后依次做三件事编译、跑官方样例、跑性能自测。以 Percolation 为例命令行流程如下# 本地自测 Percolation 的典型流程 javac-algs4 Percolation.java PercolationStats.java java-algs4 PercolationStats 200 100 # 第一个参数 n 表示 200x200 网格第二个参数 trials 表示蒙特卡洛实验次数javac-algs4和java-algs4是这门课的官方命令等价于把 algs4.jar 加入 classpath 后再调用 javac/java。PercolationStats 200 100这一段的意思是在 200×200 的网格上做 100 次独立实验统计渗透阈值的均值、标准差和 95% 置信区间。跑完以后输出里会出现 mean、stddev、confidence interval 三个值。判断标准很明确均值要落在 0.592 附近这是物理学家已经算出来的渗透阈值如果偏离太远说明 open 或并查集逻辑有系统性问题。我会额外强调堆内存参数。课程评测的内存上限通常比本地 JVM 默认值小比如 Kd-Trees 作业会限制节点存储方式本地堆开得太大反而测不出真实占用。我一般会在自测时主动加java -Xmx256m再跑一遍提前暴露内存问题。另外命令参数要学会先用小规模验证第一次可以跑20 50几秒出结果确认无误后再放大到200 100不要一上来就用最大规模干等。2.3 评分维度正确性、性能、风格三项都要拿课程作业的分数不是只靠几个测试用例。评分至少三层正确性测试占大头性能测试专门卡时间和空间还有 checkstyle 风格分。很多人正确性全过、性能也过却在风格分上被扣掉一两分最后的等级从 100 掉到 98挺可惜的。评分项大致占比考察方式正确性约 60%几十个单元测试边界输入性能约 30%时间上限与内存上限风格约 10%checkstyle 零警告checkstyle 的规则非常具体每行不超过 100 字符、禁止用比较 String、局部变量名必须小写驼峰、不允许裸魔数、单个方法不能太长。这套解答之所以值得参考一部分原因就是它代码风格是按 checkstyle 零警告的标准整理的可以直接提交。如果拿这套代码作参考提交前自己也跑一次检查checkstyle-algs4 Percolation.java PercolationStats.java逻辑说明checkstyle-algs4是课程脚本调用课程指定的规则集。输出里只要出现 WARNING就代表有风格问题。规则集对行尾空格、import 顺序、javadoc 缺失都很敏感不是可选项而是评分项。提示课程评测用的 checkstyle 规则和社区通用版不同务必用checkstyle-algs4不要用本地 IDE 自带的那套。3. Percolation 实战从暴力枚举到并查集的标准改造3.1 问题定义与接口约束Percolation 是 Part 1 的第一个作业也是最能说明「暴力解法为什么在这里行不通」的例子。问题描述是有一个 n×n 的网格每个格子要么 open开放要么 blocked阻塞。一个格子 open 后它和上下左右四个方向相邻的 open 格子就连通了。当顶部任意 open 格子和底部任意 open 格子存在一条连通路径时整个系统处于渗透状态。作业要求实现Percolation和PercolationStats两个类。前者维护网格状态必须提供open(int row, int col)、isOpen、isFull、percolates、numberOfOpenSites方法后者做蒙特卡洛实验计算渗透阈值均值与置信区间。这里有两个隐藏约束行和列的编号从 1 开始而不是 0方法签名不能改动否则评测端反射调用会失败。有些同学在 open 内部把 row-1、col-1 换算成数组下标时弄反导致第一行永远无法连上顶部虚拟节点最后渗透阈值偏大。3.2 暴力做法的失败与并查集引入如果只求正确最直接的做法是每次判断渗透时都对网格做一次 DFS从顶部所有 open 格子出发看能不能到底部。单次遍历是 O(n²)在 n200 的网格上勉强能跑但统计实验要做 T 次每次实验内又要反复 open总复杂度会到 O(T × n² × n²) 这个量级性能测试直接超时。即使把 DFS 改成 BFS 并用 visited 数组也无法改变「每次查询都扫描全图」的根源问题。标准做法是用并查集维护连通性。每个格子在 open 的同时和已经 open 的上下左右邻居做 union「是否渗透」变成「顶部虚拟节点和底部虚拟节点是否连通」。并查集的 find 和 union 几乎是常数时间带路径压缩和按秩合并整个模拟的复杂度降到 O(n² α(n))。这里有个官方没明说但必须知道的点并查集不支持撤销操作恰好 Percolation 的 open 是单向的、只增不减两者天然匹配。反过来如果题目要求支持关闭格子并查集就不好用了需要换思路。3.3 接口实现双并查集消除 backwash下面是一份能过评测的Percolation核心实现使用了两个并查集uf连接顶部和底部虚拟节点用来判断percolatesufNoBottom只连顶部用来判断isFull。public class Percolation { private final int n; private final WeightedQuickUnionUF uf; private final WeightedQuickUnionUF ufNoBottom; private final boolean[] open; private final int top; private final int bottom; private int openCount; public Percolation(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); this.n n; int size n * n 2; uf new WeightedQuickUnionUF(size); ufNoBottom new WeightedQuickUnionUF(size); top 0; bottom n * n 1; open new boolean[size]; } private int index(int row, int col) { return (row - 1) * n col; } public void open(int row, int col) { validate(row, col); int idx index(row, col); if (open[idx]) return; open[idx] true; openCount; if (row 1) { uf.union(idx, top); ufNoBottom.union(idx, top); } if (row n) { uf.union(idx, bottom); } unionIfOpen(idx, row - 1, col); unionIfOpen(idx, row 1, col); unionIfOpen(idx, row, col - 1); unionIfOpen(idx, row, col 1); } private void unionIfOpen(int idx, int row, int col) { if (row 1 || row n || col 1 || col n) return; if (open[index(row, col)]) { uf.union(idx, index(row, col)); ufNoBottom.union(idx, index(row, col)); } } public boolean isFull(int row, int col) { validate(row, col); if (!open[index(row, col)]) return false; return ufNoBottom.find(index(row, col)) ufNoBottom.find(top); } public boolean percolates() { return uf.find(top) uf.find(bottom); } }逻辑说明每个新打开的格子会尝试与四个方向的 open 邻居合并。首行格子额外连接 top 虚拟节点末行格子额外连接 bottom 虚拟节点。isFull走ufNoBottompercolates走uf。为什么isFull不能也走uf因为系统渗透后top 和 bottom 已经连通任何和 bottom 连通的格子也会被归到 top 的连通分量里于是「从底部连上来、但并没有真正连到顶部」的格子会被误判为 full。这就是 backwash 问题课程讨论区每个学期都会有人问。参数说明网格边长 n 必须大于 0数组大小是 n×n2多出的两个下标分别给 top 和 bottom。index(row, col)的换算公式(row - 1) * n col把二维坐标压成 1 到 n² 的一维下标。unionIfOpen里每次都重新计算邻居下标会有少量重复开销但并查集操作很轻课程性能限制完全覆盖得住。两个并查集让内存翻倍但 Percolation 的测试对时间更敏感这个取舍是值得的。3.4 PercolationStats蒙特卡洛实验与置信区间PercolationStats的作用是重复实验每次新建一个干净网格随机选格子打开直到系统渗透记录打开的格子数占比。实验结束后用标准公式计算均值、标准差和置信区间。public class PercolationStats { private final double mean; private final double stddev; private final double confidenceLo; private final double confidenceHi; public PercolationStats(int n, int trials) { if (n 0 || trials 0) throw new IllegalArgumentException(); double[] thresholds new double[trials]; for (int t 0; t trials; t) { Percolation p new Percolation(n); while (!p.percolates()) { int row StdRandom.uniformInt(1, n 1); int col StdRandom.uniformInt(1, n 1); p.open(row, col); } thresholds[t] (double) p.numberOfOpenSites() / (n * n); } mean StdStats.mean(thresholds); stddev StdStats.stddev(thresholds); confidenceLo mean - 1.96 * stddev / Math.sqrt(trials); confidenceHi mean 1.96 * stddev / Math.sqrt(trials); } }逻辑说明while 循环里不断随机 open直到渗透。重复选到同一个格子没关系因为open是幂等的不会重复计数。StdRandom.uniformInt(1, n 1)生成 [1, n] 的整数左闭右开所以上限必须写 n1。标准差的公式直接调StdStats.stddev省去手写。参数说明n 通常取 20 到 200trials 官方建议至少 100。置信区间的宽度和sqrt(trials)成反比trials 越大越窄但运行时间线性增长。本地快速验证时可以先跑n20, trials50确认均值落在 0.59 到 0.60 之间再放大参数。测试里如果StdRandom.setSeed被删掉每次实验的随机序列不同出问题时无法复现这点我在避坑章节会再强调。4. 把 80 分的实现拉满细节优化与边界参数4.1 Deques and Randomized Queues均摊 O(1) 的数组策略第二个作业RandomizedQueue的难度不大但评测卡得细dequeue、enqueue 必须均摊 O(1)而且不能使用java.util集合类必须自己用数组实现。常见做法是动态数组加「末尾补位」删除法——dequeue 时随机选一个位置把数组最后一个元素搬到这个位置再把最后一个位置置 null。这样数组永远紧凑不需要搬移大量元素。public Item dequeue() { if (isEmpty()) throw new NoSuchElementException(); int idx StdRandom.uniformInt(size); Item item items[idx]; items[idx] items[size - 1]; items[size - 1] null; size--; if (size 0 size items.length / 4) resize(items.length / 2); return item; }逻辑说明随机下标出来后把尾部元素覆盖到被删位置再置 null。置 null 是关键Java 数组持有引用会让 GC 没法回收逻辑删除的对象内存占用会缓慢上涨评测的内存统计会发现这个问题。参数说明缩容阈值取items.length / 4而不是1 / 2是为了避免扩容后立刻缩容的抖动。假如缩容阈值是 1/2那么当队列在容量一半附近波动时会反复触发扩容和缩容均摊复杂度恶化。扩容倍数选 2 最简单也能保证均摊 O(1)选 1.5 能省一点内存但代码里要浮点乘除边界检查容易看错我一般保留 2。这个作业还有个常见陷阱iterator 返回的迭代器之间必须互不影响正确做法是让迭代器持有数组快照和独立游标不要直接引用队列内部数组做原地修改。4.2 Kd-Trees递归深度与退化数据Kd-Trees 是 Part 1 的压轴题需要实现KdTree的 insert、contains 和 nearest。核心是「2-d tree」的递归插入奇数层按 x 坐标比较偶数层按 y 坐标比较从 x 开始还是从 y 开始取决于约定课程默认第一层按 x。每个节点还隐含了一条切分线nearest 查询靠它来剪枝。private Node insert(Node node, Point2D p, boolean vertical) { if (node null) return new Node(p, vertical); int cmp compare(p, node.p, vertical); if (cmp 0) node.left insert(node.left, p, !vertical); else if (cmp 0) node.right insert(node.right, p, !vertical); else node.p p; return node; } private int compare(Point2D a, Point2D b, boolean vertical) { if (vertical) return Double.compare(a.x(), b.x()); return Double.compare(a.y(), b.y()); }逻辑说明vertical表示当前层用哪个坐标比较每递归一层就取反实现在两个维度间交替切分。compare必须用Double.compare不能写成a.x() - b.x()浮点减法在值接近时精度不稳NaN 的行为也不可控。参数说明nearest 查询的剪枝条件是性能关键。只有当查询点到当前节点切分线的垂直距离小于当前已知最近距离时才进入另一侧子树否则整棵子树都可以剪掉。很多实现在这里把「到切分线的距离」和「到点的距离」混在一起导致剪枝失效复杂度退化到 O(N)。另一个边界是重复点如果插入的点已经存在contains 必须返回 trueinsert 对相同坐标应该覆盖而不是新建节点否则树里有重复点nearest 结果可能不稳定。树在输入点按坐标升序排列时会退化接近链表递归深度 O(N)这是 2-d tree 的固有问题课程测试数据会专门构造这种情况只能说尽量避免而不是完全消除。4.3 Collinear Points比较器与去重的正确姿势第三个作业Collinear Points要求找出所有包含至少 4 个点的直线段。暴力解法枚举任意两点确定直线再查其他点是否共线更快的有FastCollinearPoints按斜率排序扫描。最常翻车的点是重复输出线段同一条线段从不同端点出发会被多次发现。常见做法是对每个点 P 作为原点把其余点按到 P 的斜率排序扫描连续相同斜率的点段。只有当 P 是该线段自然顺序上的最小端点比如按 x 优先、y 其次的比较器时才把这条线段写入结果。private boolean isMinEndpoint(Point p, Point q, Point r) { return p.compareTo(q) 0 || (p.compareTo(q) 0 p.compareTo(r) 0); }逻辑说明Point.compareTo按 x 升序、x 相等时按 y 升序。扫描到一条候选线段的点段后先比原点 P 和段内所有点只有 P 最小才记录。这样每条线段只会从它的最小端点被输出一次。参数说明斜率如果用 double 存整数坐标场景没问题但如果你扩展成浮点坐标double 精度会导致「斜率相等」误判该合并的线段被拆开。我一般建议用有理数形式存斜率比如把分子分母约分后拼成字符串或者自己写一个 Slope 类。这个作业的时间限制较宽内存限制反而严格暴力解法在几千点规模下可能内存超限写之前先算一下要存储的斜率数量再定方案。5. 避坑与常见问题五个把 100 分改没的细节5.1 编译失败本地正常提交报错现象本地 IDE 编译通过提交到评测端却报编译错误分数直接 0。原因本地 IDE 自动补了import java.util.*或者代码里用了课程禁用的标准库类比如 ArrayList、HashMap。评测环境用官方脚本编译禁用类清单在每个作业的 checklist 里写得很清楚用错一个就直接编译失败。解决提交前在作业目录跑一次javac-algs4 *.java并核对 import。如果确实需要动态数组自己用普通数组扩容实现不要依赖标准库。这套解答里所有涉及数组的作业都是手写扩容数组就是为规避这条规则。5.2 isFull 结果诡异backwash 在作祟现象Percolation 样例全过但提交后 isFull 的专项测试失败本地肉眼检查看不出问题。原因单一并查集同时连了 top 和 bottom系统渗透后底部虚拟节点把「从底部连上来、但没连到顶部」的格子也归并进 top 的连通分量isFull 返回 true 的集合过大。解决维护两个并查集一个连 top/bottom 负责 percolates一个只连 top 负责 isFull。第 3 章的代码就是这么写的这也是课程讨论区公认的标准解法但每年都有人因为只用一个 UF 翻车。5.3 性能测试超时正确但不够快现象所有功能测试都过性能测试显示超时扣分严重。原因最常见的是 isOpen 或 numberOfOpenSites 内部写了遍历或者并查集用了 QuickFindUF 导致 union 是 O(n)以及随机队列缩容阈值设成 1/2 造成反复 resize。更隐蔽的是 Kd-Tree 的 nearest 没有做切分线剪枝。解决查询类方法改成数组直接访问并查集统一用 WeightedQuickUnionUF随机队列缩容阈值保持 1/4。Kd-Tree 的 nearest 一定先判断查询点到切分线的垂直距离再决定是否进入另一侧子树。本地用java -Xmx256m加时间统计提前感知性能问题。5.4 随机测试偶发失败种子不可控现象同一份代码本地连续跑五次三次过两次挂提交后分数还和本地不一样。原因随机算法没有固定种子每次实验的打开顺序不同某些 bug 只在特定随机序列下触发。比如随机队列里resize 倍数和下标计算的边界错误概率可能低于 1%平时跑不出来。解决自测脚本里第一行写StdRandom.setSeed(2024)保证失败可复现再写循环跑 100 次同一种子观察有没有偶发失败。触发失败的种子和参数要记录成回归用例以后每次改动后重跑一遍。5.5 风格分被扣checkstyle 零容忍现象功能分满分风格分被扣 1~2 分等级没有拿到最高档。原因行尾空格、不用的 import、裸数字常量、方法长度超过限制都是 checkstyle 的默认告警项。课程风格检查是零容忍的一个警告都可能进入扣分。解决提交前跑checkstyle-algs4 *.java看到 WARNING 就改不要留到提交后。行尾空格交给 IDE 保存时自动清理魔数改成private static final int常量这两招能消掉大部分告警。代码里全程用课程提供的 In/Out 类避免 System.out 混用也能减少风格问题。6. 把解答变成自己的算法模板库复用与验证技巧作业代码的类名、方法签名都被课程接口绑定想复用里面的核心逻辑直接复制类名很别扭。我的一般做法是把每个作业核心的数据结构抽出来改成通用类名去掉 validate 等作业特有的约束放进自己的模板目录。比如 Percolation 的双并查集思路抽成连通性管理类Kd-Tree 的 insert/nearest 抽成通用的二维索引类。抽离的时候保留参数注释比如缩容阈值为什么是 1/4、为什么用两个并查集否则几个月后再看又变成黑匣子。验证是这类资源最容易被忽略的一环。常见做法是写一个批量脚本遍历所有作业目录编译、跑样例、跑边界用例任何一步失败就退出并打印目录名。#!/usr/bin/env bash set -euo pipefail for d in Percolation Deques Collinear KdTree; do echo $d (cd $d javac-algs4 *.java java-algs4 $d sample.txt) done逻辑说明set -euo pipefail让脚本在编译失败、管道中断时立即退出不会带错继续跑。每个目录放一份稳定的 sample.txt保证输入不变。脚本只适合确定性样例随机算法需要固定种子否则两次结果不同没法判断是代码坏了还是随机波动。脚本里可以再加一行java-algs4 PercolationStats 20 50做小规模统计验证确认均值落在 0.59 到 0.60 之间再提交。课程评测是打分标准但直接拿它当调试器效率太低每次提交有冷却限制反馈通常也只有错误摘要。我的顺序是本地自测全部跑绿再对照 checklist 检查禁用类和接口签名最后提交。这一套流程走下来作业基本都能一次过。尤其是固定种子、跑回归、过 checkstyle 的顺序从一开始的手忙脚乱到接近零失误完全是靠踩坑换来的。从那以后我每次做这类课程作业都会强制把这三步走一遍再按下提交键。如果你正在做 algs4 的作业直接把这份解答拉下来对照着跑会比自己从头踩坑快很多。希望帮到你。本文还有配套的精品资源点击获取