简介这是Coursera平台上普林斯顿大学《算法》课程编程作业的Java解答合集面向系统学习算法理论并希望完成配套编程实践的学习者能帮助读者对照经典题目梳理解题思路、验证实现细节。压缩包共20个文件以18个Java源文件为主体另含1个Markdown说明文档和1个License文件总容量仅28KBJava文件对应各作业核心实现Markdown用于说明作业任务与运行方式。解答覆盖渗滤、WordNet、KdTree、双端队列与随机队列、接缝裁剪、共线点、8拼图等题目从基础数据结构到图与动态规划逐步递进涉及排序、搜索、图处理、最优化等经典算法主题也展示了面向对象封装、泛型与集合框架的实际运用。读者可对照代码排查自己提交中的逻辑漏洞学习如何将复杂问题拆分为可管理模块、设计接口并选择合适的数据结构从而提升算法分析能力与Java编程水平。目前已有243人学习下载适合算法课程自学者和需要编程实践参考的开发者。1. algs4-Programming-Assignment这份作业合集到底该不该刷A同学问过我一个很实在的问题网上流传的 algs4-Programming-Assignment 习题解答到底值不值得照着敲一遍我的回答是值得但得把它当“评测标准”而不是“答案”。这是某高校那门经典算法公开课配套的编程作业合集覆盖并查集、排序、图算法、字符串处理等算法课核心知识点。真正让这套作业含金量高的是它背后的自动评分机制——不只查输出对不对还查性能、内存、代码风格和 API 合规。直接抄一遍答案只会得到一份虚假的掌握感自己实现、反复跑测试、再对照合集里的思路才是这套作业的正确打开方式。这篇笔记就把这条路从头拆到尾。2. algs4 作业全貌10 道题的知识点分布与难度评级2.1 作业清单与难度先把对手看清楚algs4 公开课一共拆成两段第一段偏基础数据结构第二段偏进阶算法前后各五个编程作业。下面这份清单是我自己按“实现阻力”拍的难度不是课程官方排序你可以把它当作投入时间的参考。阶段作业核心算法我心中的难度最容易翻车的地方Part IPercolation并查集★★☆isFull 的 backwash 误判Part IDeques and Randomized Queues双向队列、随机队列★★☆随机性不满足均匀分布Part ICollinear Points排序、斜率比较★★★共线点去重与浮点误差Part I8 PuzzleA* 搜索、优先队列★★★棋盘状态的不可变性Part IKd-Trees二维 KD 树★★★★分割平面的边界条件Part IIWordNet有向图、最近公共祖先★★★★多继承路径长度定义Part IISeam Carving动态规划、能量图★★★★能量图更新与最小路径Part IIBaseball Elimination最大流、最小割★★★★★网络流建模Part IIBoggleTrie 树、DFS★★★★去重与回溯恢复状态Part IIBurrows-Wheeler循环后缀、Huffman★★★★★next 数组逆向还原Part I 的前三个作业其实是在热身难度不高但要求你适应“按接口写类”的模式哪些方法必须是 public哪些辅助逻辑必须藏起来这些习惯会直接影响后面所有作业。从 8 Puzzle 开始评分器会统计你创建的对象数量算法复杂度对但对象太多照样扣分。Part II 里的 Baseball Elimination 和 Burrows-Wheeler 是最劝退的两道前者要把比赛排名问题改造成网络流后者要把循环后缀数组的逆向变换搞清楚任何一个环节卡住都容易让人想放弃。2.2 评分机制拆解别以为输出对了就拿满分很多合集里的代码在本地能跑出正确答案交上去分数却很难看原因是没吃透官方评分器的五个维度。正确性大量单元测试除了固定用例还有随机生成用例。随机种子固定结果可复现意味着你不能靠运气过关。性能每个测试有超时限制复杂度不对、对象创建过多都会让这个维度崩掉。内存评分器会统计你创建了多少对象每个作业有配额超了直接扣分。这是 algs4 作业和普通 OJ 最大的区别普通在线评测只关心时间和答案这里连内存足迹都要算。代码风格走 Checkstyle缩进、空格、Javadoc、命名、行长度都会被查。风格分占比不大却是最好拿的丢了最冤。API 合规作业规定类的公开接口你多写一个 public 方法评测器可能直接编译失败这是硬线。所以我的习惯是把习题解答当“对照答案”不看它的输出只看它怎么建模然后自己实现。每道题先自己写一版卡住了再去翻合集的思路提示而不是复制代码。后面每一章的代码都是教学节选不是交作业用的完整答案用意也在这里。2.3 刷题顺序与时间预算不是所有题目都要平均用力推荐顺序是Percolation → Deques 和 Randomized Queues → Collinear Points → 8 Puzzle → Kd-Trees → WordNet → Seam Carving → Boggle → Baseball Elimination → Burrows-Wheeler。理由是前五道能帮你建立起“对象数量敏感度”后面图算法和网络流先易后难心理压力会小很多。时间预算按三档来Part I 前三题是热身一题 12 天Part I 后两题加 Part II 前三题是核心区一题 23 天Baseball Elimination 和 Burrows-Wheeler 是硬骨头给自己 45 天因为建模失败重来的概率很高。总时间大约六到八周和公开课的节奏基本吻合。如果手头只有两周我的取舍是把前五道吃透Part II 只做 WordNet 和 Seam Carving另外三道看思路但不深抠。先把一整套评分机制跑熟比做完十道题但每道都没打磨到满分更有价值。3. 搭建本地评测环境从 JDK 到评分脚本的一站式配置3.1 版本选型老课程别追太新的 JDK这套作业是用 Java 写的官方评测器大概率跑在 JDK 8 或 11 上。我本地装的是 OpenJDK 17但写代码时只用 Java 8 就有的语法var、switch 表达式、记录类型这些新特性一概不碰。原因很简单你在本地用新特性编译通过评测器用旧编译器一编就挂这种翻车没有任何技术含量纯粹是版本自找的。不要因为教程里写了某个 JDK 版本就去网上找“最新版”也别迷信新版本能自动优化性能。评分器对旧代码的兼容性远比本地开发体验重要。装好后先确认版本一致java -version javac -version两个命令输出的版本号必须一致否则编译和运行用的不是同一套工具链。最常见的坑是系统里同时装了多个 JDKjava指向了 17javac却指向了 8这类玄学问题我在很多同学的机器上见过。3.2 环境变量与类路径可以直接执行的配置片段我习惯把课程配套的库统一放到~/lib目录下然后在每个作业目录里用 export 临时设置不写进全局配置避免不同作业互相干扰。export JAVA_HOME/usr/lib/jvm/java-17-openjdk-amd64 export PATH$JAVA_HOME/bin:$PATH export ALGS4_LIB$HOME/lib/algs4.jar export CLASSPATH.:$ALGS4_LIB java -version javac -version逐行说明一下JAVA_HOME指向 JDK 安装根目录PATH把 JDK 的 bin 目录放到最前面确保命令行用的是它ALGS4_LIB指向 algs4.jar这个 jar 里装好了 WeightedQuickUnionUF、StdRandom、StdIn 等课程配套类作业里可以直接 importCLASSPATH里最前面的点是当前目录表示编译时先找当前目录下的源码和字节码。参数注意如果你在 Windows 上类路径分隔符是分号而不是冒号路径里也别带空格。macOS 上不要硬编码 JAVA_HOME 路径用/usr/libexec/java_home动态获取我通常会在~/.zshrc里写一行别名而不是把路径写死。3.3 最小命令跑通第一个作业编译、运行与自测环境配好后用第一个作业 Percolation 验证整套链路cd ~/workspace/01-percolation javac -encoding UTF-8 Percolation.java PercolationStats.java java PercolationStats 200 100第一行命令把两个类一起编译第二行运行蒙特卡洛模拟。PercolationStats的两个参数分别是网格边长 N 和实验次数 T输出应该是平均值、标准差和 95% 置信区间。如果你看到数值在 0.59 附近抖动说明基础功能正常因为渗漏阈值的理论值大约是 0.5927。如果输出是 1.0 或者 0.0说明并查集的合并逻辑有方向性问题后面第四章会详细讲。注意这个命令只验证正确性的一部分不能替代官方评分器。边界输入测试比如 n1、行列越界、重复 open必须自己补评分器一定会覆盖这些用例。3.4 把评分器和 Checkstyle 接到本地常见做法是从课程页面下载测试器 zip 和 Checkstyle 配置解压到作业根目录目录结构大致如下。01-percolation/ Percolation.java PercolationStats.java lib/ algs4.jar checkstyle/ checkstyle.jar algs4.xml tester/Checkstyle 的调用方式一般是java -jar checkstyle/checkstyle.jar -c checkstyle/algs4.xml *.java这条命令把当前目录下所有 Java 源码按课程规则检查一遍规则文件不变本地结果基本等同评测器结果。测试器的情况则因作业而异入口可能是一个 jar 包也可能是一组 JUnit 类以课程当季页面给的说明为准但运行原理都一样先编译再跑正确性用例最后跑性能测试。这里有个很容易踩的坑类路径忘记加lib/algs4.jar测试器 一启动就报 ClassNotFoundException别慌回到 3.2 的 export 重跑一遍把依赖加载顺序理清就好。4. 以 Percolation 为样板建模、backwash 与可对照的关键代码4.1 先把题目翻译成数据结构Percolation 问的是N×N 个格子每个格子可能开放或封闭从最上面一行灌水水能不能顺着相邻开放格子流到最下面一行。暴力做法是每次查询都重新做一次 DFS太慢正确姿势是并查集把连通的开放格子合并成一个集合再判断顶和底是否连通。但直接合并所有开放格子isFull会出错。原因在于并查集只回答“连通吗”不回答“这个格子是因为直接和顶部连通才算 full还是因为从底部回流上来的也算 full”。这就是 backwash 问题。所以在建模前就要决定percolates 和 isFull 是不是用同一套并查集。在我做过和看过的方案里最常见的做法是维护两个并查集一个管 percolates一个管 full代价是内存多一份父数组但逻辑清楚值得。4.2 虚拟节点与 backwash决定 isFull 正确性的两个参数这道题里有几个参数是必须想清楚的虚拟顶节点给并查集多开一个索引 0把第一行所有 open 的格子 union 到 0percolates就可以直接回答“虚拟底节点和 0 是否连通”时间复杂度 O(1)。虚拟底节点索引 N*N1把最后一行所有 open 的格子 union 到它。注意如果只用这一个并查集判断 full底部连通的格子上方所有开放格都会被误判为 full因为路径可以经底部绕回顶部。isFull 的判定要用不含虚拟底节点的那个并查集只判断“是否和虚拟顶节点连通”。参数取值作用N网格边长决定数组长度 N*N2虚拟顶索引0连接第一行用于 percolates 和 isFull虚拟底索引N*N1连接最后一行只用于 percolatesufN*N2 长度的并查集连虚拟底负责 percolatesufFullN*N2 长度的并查集不连虚拟底负责 isFull4.3 关键代码节选open() 的合并与 isFull() 的两种写法下面这段是核心骨架节选自常见正确做法不能直接提交但可以对照自己的实现。public class Percolation { private final boolean[] open; private final int n; private final WeightedQuickUnionUF uf; // 管 percolates含虚拟底 private final WeightedQuickUnionUF ufFull; // 管 isFull不含虚拟底 private int openCount; public Percolation(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); this.n n; open new boolean[n * n 2]; uf new WeightedQuickUnionUF(n * n 2); ufFull new WeightedQuickUnionUF(n * n 2); } private int indexOf(int row, int col) { return (row - 1) * n col; } public void open(int row, int col) { validate(row, col); if (isOpen(row, col)) return; int id indexOf(row, col); open[id] true; openCount; if (row 1) { uf.union(id, 0); ufFull.union(id, 0); } if (row n) { uf.union(id, n * n 1); } // 只和已经开放的邻居合并 unionNeighbor(row, col, row - 1, col); unionNeighbor(row, col, row 1, col); unionNeighbor(row, col, row, col - 1); unionNeighbor(row, col, row, col 1); } public boolean isFull(int row, int col) { validate(row, col); int id indexOf(row, col); return open[id] ufFull.find(id) ufFull.find(0); } }逻辑说明很关键open()里先把 open 数组标记为 true再决定要不要连虚拟节点最后只和上下左右已经开放的格子合并。顺序不能反否则isOpen会漏掉当前格子的状态。isFull用的是ufFull它没有连虚拟底所以从底部绕上来的格子不会在这里被判为 fullbackwash 被绕开了。参数说明WeightedQuickUnionUF是官方库提供的并查集find(id)返回集合根节点ufFull.find(id) ufFull.find(0)表示当前格子与虚拟顶属于同一集合。两个并查集都初始化为 N*N2 长度多出来的两个位置就是虚拟顶和虚拟底。如果你直接照抄这段去提交会挂在 validate 和 unionNeighbor 这两个私有方法上——它们必须自己补全包括行列越界检查。4.4 用官方测试之外的“土办法”验证正确性官方评分器要等提交后才出结果太慢。我一般在本地跑一组不同规模的蒙特卡洛模拟for n in 100 200 500; do java PercolationStats $n 100 doneN 从 100 到 500实验次数固定为 100观察均值是否稳定在 0.5927 附近。如果输出稳定在 0.59 到 0.60 之间说明渗漏模型的并查集逻辑基本正确如果明显偏离先检查open()里有没有漏掉邻居合并再看虚拟顶底节点的索引有没有算错。这个办法能提前拦下一大批低级错误尤其是把行列坐标转索引时从 0 开始还是从 1 开始的问题。5. algs4 作业避坑指南五个最容易丢分的细节5.1 Checkstyle 风格分丢光因为你没在本地先跑一遍规则现象功能全对评分器上的风格分却是 0。原因Checkstyle 检查缩进、空格、Javadoc、行宽、空行本地 IDE 看着正常评测器一跑就全亮红。我见过的典型问题包括方法之间没有空行、行尾多了空格、缺少类级 Javadoc、命名用了缩写。解决把课程提供的 checkstyle 配置放到本地提交前先跑一次把警告当错误处理。命令在 3.4 里给过规则文件不变本地结果基本等同评测器结果。风格分虽然占比不大但它是所有维度里唯一零成本能拿满的丢了就是白丢。5.2 API 违规多一个 public 方法直接编译失败现象本地能编译传到评测器上报错说找不到方法或方法签名冲突。原因作业规定了类必须有哪些 public 方法同时要求“不允许额外的 public 方法”。为了调试方便加一个 public 辅助类比如public void printGrid()评测器一编译就挂。解决所有辅助函数一律 private内部辅助类改成 package-private 或普通内部类不能进公开接口。这是我见过最多的低级翻车而且一旦发生整个作业的分数都受影响不是只扣一点点。5.3 性能超时对象数量是隐藏的定时炸弹现象小规模用例全过大规模用例 Time Limit Exceeded。原因算法复杂度没问题但对象创建太多。典型场景是每次比较都 new 一个包装类型来存斜率或者用 ArrayList 存大量临时结构导致垃圾回收拖慢整体速度。解决作业要求“限制创建的对象数量”通用做法是尽量用基本类型、复用数组、避免自动装箱。用内存分析工具统计对象数量和评分器同口径比较。性能测试的输入规模一般设计成是你复杂度能过的上限一旦超时先不要优化算法先数一数对象创建。5.4 随机性测试翻车不要自己造随机现象Deques 和 Randomized Queues 的随机性测试偶尔失败本地还复现不出来。原因自己用Math.random()凑均匀分布没有严格遵守“dequeue 时每个元素等概率”的要求。比如实现随机队列时用了链表删除时没有把随机选择落实到每一步导致分布偏差。解决要么用官方库提供的 StdRandom要么把随机队列实现成可扩容数组每次 dequeue 时随机选一个索引把最后一个元素搬过来填坑保证 O(1) 且等概率。评测器的随机种子是固定的它测的是统计属性你本地跑一百次看着没问题不代表种子一变还能过。5.5 内存超限隐藏引用比大数组更危险现象正确性和性能都过了内存分被扣。原因你以为只开了一个 NN 的数组但并查集初始化了 NN2 个节点又额外存了一份 open 数组加上保存棋盘状态的字段没有释放内存配额就超了。解决提交前数一遍每个对象数组、并查集父数组、辅助状态数组。凡是可以在局部变量里创建的就不要塞进字段凡是能通过索引计算得到的就不要额外存一份。官方库的 WeightedQuickUnionUF 内部有一个长度为 N*N2 的 int 数组这是必须的但不要再重复维护一份邻接表或布尔矩阵。内存维度最麻烦的地方在于它不报错只在分数单上扣你几分所以提交前多花十分钟数对象回报很高。6. 交作业前最后 10 分钟三个给分数兜底的验证习惯6.1 一条命令自查 80% 的坑我每次提交前都会跑一条三连命令把编译、风格、基础功能串在一起javac -encoding UTF-8 -Xlint:all *.java \ java -jar checkstyle/checkstyle.jar -c checkstyle/algs4.xml *.java \ java PercolationStats 200 100第一段打开全部编译警告任何 unchecked 或 deprecation 都值得看一眼不要放过第二段是风格硬门槛过了才继续第三段是典型的随机模拟验证核心功能没有在修改中被破坏。三关都过剩下的是边界行为靠 6.2 的表单去对照。6.2 把成绩单回读成代码动作拿到评分结果后第一反应别是看总分而是看哪个维度掉了然后按表定位成绩单项含义回读后的动作Correctness功能正确性补边界输入、空输入、非法参数Timing性能检查循环里有没有对象创建能不能用基本类型Memory内存配额数一遍字段数组删冗余引用Checkstyle风格按配置逐条过本地重跑一遍API Compile接口合规把所有多余 public 改成 private这张表是我从好几次“为什么功能对却只有 70 分”的疑问里整理出来的。照着表回读五分钟内基本能定位丢分点。6.3 提交前留好第一版给评测器一次反悔的机会最后一个习惯是版本管理。我一般每个作业建一个 Git 仓库第一版能通过基础测试就提交一次再开分支做优化git init git add . git commit -m v1: first correct version git checkout -b refactor vi Percolation.java # 做性能或内存优化 git add Percolation.java git commit -m v2: optimize memory git checkout mastermaster 分支永远保留第一版refactor 分支放心折腾。如果优化把正确性改挂了切回 master 重新提交比在考场里一行行找回改前的代码要省太多时间。这个后悔药我吃过几次甜头现在已经是习惯动作。我现在拿到任何一份习题解答第一件事不是看代码而是先把整套测试命令跑通再逐题写自己的版本。解答合集的真正价值是告诉你哪些坑可以不用踩但动手过的那道坎只能自己走过去。希望帮到你。本文还有配套的精品资源点击获取