简介这是针对普林斯顿大学Coursera算法课程编程作业的Java解答项目适合正在修读该课或系统练习经典算法的开发者、学生使用。资源涵盖渗透、队列、共线点、8数码、Kd树、WordNet、接缝裁剪等多个作业模块每个模块均提供完整Java源码并配有README说明与LICENSE许可方便查阅和二次修改。压缩包共20个文件以Java源码为主18个另有1个Markdown说明文件和1个许可证文件整体大小仅28KB结构紧凑便于快速下载与对照调试。已有243人学习内容围绕算法与数据结构核心主题包括并查集、优先队列、红黑树、最短路径、动态规划等经典知识点。通过研读这些实现可以直观理解如何将课堂理论转化为可运行代码提升Java编程能力和算法分析水平尤其适合需要解决作业思路、学习代码组织方式或准备技术面试的学习者。1. 先说清楚这套编程作业到底是什么值不值得做如果你在 GitHub 上搜过 algs4大概率见过这样的仓库整齐列着8Puzzle.java、BoggleSolver.java、BurrowsWheeler.java命名规范到像印刷品评论区永远有人追问这是 Princeton 的作业吗代码能直接交吗。这是指 Coursera 上普林斯顿大学开设的 Algorithms, Part I Part II 课程通常简称 algs4配套的编程作业Programming Assignment是这门课的灵魂——不把作业写完就跟看完整套教学视频却没翻过一页课后题一样知识永远浮在表面。这门课的编程作业有一个非常鲜明的特点不考语法考工程判断。每个作业给你明确的数据结构与算法约束比如不得使用任何 Java 集合类、时间复杂度必须达到某个大 O 级别然后让代码跑过一堆隐藏测试用例。更关键的是作业自带官方评分器会检查你有没有用禁止的数据结构、有没有在构造器里不合理地分配内存、有没有在equals()里违反对称性。很多人第一版代码能跑但交上去只有 60 分原因不是算法错了而是没满足那些看不见的工程约束。这篇文章想做的不是给你一份可以原封不动粘贴的答案而是把每个高频作业题的解题路径、边界条件和容易翻车的细节拆开讲。适合三类人正在肝 Coursera 的读者、想用作业练手却卡在某一题的老手、以及把 algs4 当面试准备材料的人。你会看到每个题的核心难点、推荐的数据结构选型、以及我在本地环境反复排查过的坑。读完你应该能独立完成大部分作业而不是从仓库里复制一个自己看不懂的排序比较器。2. 建立一个能过评分器的最小思维模型分数构成与选型逻辑2.1 先搞清楚评分器在看什么三项分数与两类测试algs4 的官方评分器Checkstyle 加自定义单元测试对每个作业给出 100 分制评分拆成三块正确性Correctness、内存Memory、效率Timing。其中正确性又分公开可见的测试与隐藏测试。公开测试能让你大概摸清方向但真正决定你是否学会的是那些隐藏的大数据测试——比如8Puzzle里 4x4 甚至 5x5 的棋盘、BurrowsWheeler里几十 MB 的输入。我见过太多人盯着公开测试调代码交上去却只有 80 分然后一头雾水。这里有一条 80/20 法则80% 的分数靠主算法的正确性拿20% 的分数藏在边界条件与性能约束里。例如Percolation作业你只要把并查集模型建对公开测试全过就至少 80 分但如果你直接用二维数组boolean[][]记录每个格子是否打开评分器会在内存项扣分因为官方期望你用一维映射或者更省空间的建模。而那 20% 的隐藏分往往决定了你最后是 90 还是 100。另一个容易被忽略的得分点是代码风格。评分器会跑官方 Checkstyle 配置检查命名、缩进、空行、注释格式。很多人算法全对因为一个多余的空行或者不规范的 Javadoc 被扣 2 到 3 分。这不是玄学是评分器硬规则。我的建议是本地装好 Checkstyle 插件写完代码先跑一遍官方配置再提交。2.2 本地开发环境怎么搭官方 jar 包与最小编译命令你在本地写作业不需要把整套 Coursera 环境复制下来但需要一个基础骨架。每个作业都会提供algs4.jar包含标准库、测试框架和部分数据结构还有一个样例输入文件。最常见的做法是# 以 8Puzzle 作业为例下载 algs4.jar 和对应的测试数据 # 在一个空的 src 目录里写 Board.java, Solver.java mkdir -p 8puzzle-solution/src cd 8puzzle-solution javac -cp ../algs4.jar src/Board.java src/Solver.java逻辑说明这段命令把官方库algs4.jar加入 classpath然后编译你的两个核心类。Solver会引用Board如果两者不在同一包下需要确保类的package声明一致或全部采用默认包。编译成功后会生成.class文件这时再用 java 命令运行主类。参数说明-cp指定 classpath在 macOS 或 Linux 上分隔符是冒号Windows 上是分号../algs4.jar是相对路径如果你把 jar 放在项目根目录就直接写algs4.jar。这里有个常见坑在 IDE 里直接用 Run 按钮可能没有把 algs4.jar 加进 module 依赖导致StdOut.println编译不过。我一般建议先用命令行把编译跑通再回 IDE 写代码这样能隔离环境问题。除了编译你还需要一个能模拟评分器行为的本地验证脚本。我通常这样跑样例# 编译成功之后用官方提供的样例输入跑一遍 java -cp .:../algs4.jar Solver puzzle04.txt # 期望输出里包含 minimum number of moves 5 之类的行逻辑说明puzzle04.txt是 8Puzzle 作业附带的输入文件格式是3维度然后九宫格的数字。Solver的main()会读入棋盘并输出最少步数。这个样例值来自官方测试数据不是万能的但能快速确认主流程没跑偏。2.3 为什么同一份代码两次提交分数不同留出性能余量有一类问题是我什么都没改重新提交分数从 98 变成 92。这往往不是评分器抽风而是性能项与内存项在机器负载高的时段测出来的波动。algs4 作业通常对运行时间有隐性要求比如CollinearPoints的暴力解法在 5000 个点下必须跑进几秒如果评分服务器当时很卡原本擦边的运行时间就超了。我一般会给自己留一个安全余量把时间复杂度压到理论最优的一半以下。比如CollinearPoints用排序法时排序比较器的实现决定了整体性能如果比较器里每次都重新计算斜率等于把排序的O(n log n)放大成了O(n^2 log n)——这在 5000 点下就是明显的时间差。血泪经验是能在构造器里预计算的不要在比较器里现算。同理8Puzzle里把曼哈顿距离缓存到Board实例字段能省下大量重复计算。3. 四个高频作业的解法骨架从数据模型到边界处理3.1 Percolation并查集模型的两种建法与一个致命约定Percolation是 Part I 的第一份作业很多人在这里第一次接触虚拟节点这个概念。模型很简单一个 N×N 网格每个格子独立地以概率 p 打开判断整个系统是否从顶部渗漏到底部——即是否存在一条由打开的格子构成的上下连通路径。官方要求用并查集WeightedQuickUnionUF但禁止把每个格子映射成二维数组的索引再直接存储必须显式转换成一维编号。最常见的错误是只建一个虚拟顶部节点不建虚拟底部节点然后漏掉了从底部直接出界的路径。我见过 A 同学写的版本只检查每行最后一列是否连通到虚拟顶结果在一个 2×2 棋盘上右下角打开、右上角关闭、但右下角上方也打开的情况他的模型判断为渗漏而实际上根本没有连通到顶部。原因就是没有把底部所有格子统一接到一个虚拟底部节点。正确的建模方式如下// 一维索引 (row - 1) * N col范围 1..N*N // 虚拟顶 index N*N虚拟底 index N*N1 // open[row][col] 只用于标记格子是否打开不参与连通性判断 public class Percolation { private final int n; private final int virtualTop; private final int virtualBottom; private final WeightedQuickUnionUF uf; private final boolean[][] open; public Percolation(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); this.n n; this.virtualTop n * n; this.virtualBottom n * n 1; uf new WeightedQuickUnionUF(n * n 2); open new boolean[n 1][n 1]; // 1-based方便直接用行号列号 } public void open(int row, int col) { validate(row, col); open[row][col] true; int idx encode(row, col); if (row 1) uf.union(idx, virtualTop); if (row n) uf.union(idx, virtualBottom); // 与四个邻居合并注意边界 if (row 1 isOpen(row - 1, col)) uf.union(idx, encode(row - 1, col)); if (row n isOpen(row 1, col)) uf.union(idx, encode(row 1, col)); if (col 1 isOpen(row, col - 1)) uf.union(idx, encode(row, col - 1)); if (col n isOpen(row, col 1)) uf.union(idx, encode(row, col 1)); } }逻辑说明这段代码的核心在于open()先标记格子为打开再检查是否与顶部或底部虚拟节点相连最后向四个方向检查邻居。注意并查集合并的顺序无所谓但必须先标记 open 再合并邻居否则邻居调用isOpen()时当前格子还是关闭状态就会漏掉连通路径。参数说明uf的大小是n*n2多出的两个位置留给虚拟节点。我在open()里单独判断row1和rown而不是在初始化时就连接整行的格子因为那样做的话当某个顶部格子还没打开时你就提前建立了它和虚拟顶的连接后续所有连通性全乱了。这是典型的看不见的工程约束——算法本身不难难在别让虚拟节点和未打开格子提前连通。3.2 CollinearPoints排序法的三个细节与一个必踩的浮点坑CollinearPoints又称 Pattern Recognition要求找出平面上所有由 4 个或更多点组成的直线段。暴力枚举四重循环在点数超过 50 时就会卡死所以官方允许你使用排序法以每个点为原点对其余点按斜率排序斜率相同的相邻点就在同一条直线上。排序法的核心坑有三个。第一比较器必须稳定且自洽如果两个点与原点共线它们的斜率相等此时比较器要返回 0但如果直接返回 0Arrays.sort()会认为这两个点相等从而可能触发TimSort的稳定性逻辑当数组长度超过 32 时导致排序结果不符合预期。解决方案是像官方 hint 那样用自然顺序y 坐标优先x 坐标其次来打破平局。我给出的比较器骨架如下public class SlopeOrder implements ComparatorPoint { private final Point origin; public SlopeOrder(Point origin) { this.origin origin; } Override public int compare(Point p1, Point p2) { double slope1 origin.slopeTo(p1); double slope2 origin.slopeTo(p2); if (slope1 slope2) return -1; if (slope1 slope2) return 1; // 斜率相等时用 y 坐标打破平局确保与 equals 不冲突 int yCompare Integer.compare(p1.y, p2.y); if (yCompare ! 0) return yCompare; return Integer.compare(p1.x, p2.x); } }逻辑说明这里slopeTo()必须处理三个边界垂直线dx 0返回正无穷、水平线dy 0返回 0、同一点返回负无穷。在compare()里斜率相等时的平局打破不是可选项——它决定了排序结果是否稳定可复现。但要注意这个比较器与Point.equals()并不完全一致因为origin不同的比较器对同一对点的比较结果可能不同所以排序后你需要独立地用斜率分组而不是依赖相邻点比较。参数说明Point的x、y都是int用Integer.compare避免直接相减导致整型溢出。slopeTo返回double不要用比较浮点数——我建议在compare()里直接用和分治避免Double.compare对-0.0和0.0的特殊处理。第二坑如果输入点集中有两个完全相同的点评分器会期望你输出错误提示或者直接按缺失点处理但官方测试数据里不会有重复点你的代码却要在逻辑上容错。第三坑排序后找线段时要跳过那些起点不是当前原点的线段否则每条线段会被重复输出多次。3.3 8PuzzleA* 搜索的两个剪枝与一个必踩的缓存坑这道作业要求用 A* 算法求解 8-puzzle 或 15-puzzle 的最少步数核心是正确实现优先级队列的优先级函数。常见的有两个曼哈顿距离之和每个方块的当前位置到目标位置的横向纵向距离之和与 Hamming 距离位置不正确的方块数。曼哈顿距离更强计算量略大在滑动拼图上它是一致的可采纳且单调所以用它作为启发函数不会丢解。我在这里遇到的最大坑是没有缓存 Board 的曼哈顿距离或 Hamming 距离导致每次入队出队都重新计算。8Puzzle 的状态空间虽然不大但评分器测试的 4×4 棋盘会让搜索节点数上万若不缓存运行时间会变成指数级放大。public class Board { private final int[][] tiles; private final int n; private final int hamming; private final int manhattan; private int zeroRow, zeroCol; public Board(int[][] tiles) { this.n tiles.length; this.tiles tiles; this.hamming computeHamming(); this.manhattan computeManhattan(); for (int i 0; i n; i) for (int j 0; j n; j) if (tiles[i][j] 0) { zeroRow i; zeroCol j; } } public int hamming() { return hamming; } public int manhattan() { return manhattan; } private int computeManhattan() { int sum 0; for (int i 0; i n; i) for (int j 0; j n; j) { int val tiles[i][j]; if (val 0) continue; // 空位不参与距离计算 int targetRow (val - 1) / n; int targetCol (val - 1) % n; sum Math.abs(i - targetRow) Math.abs(j - targetCol); } return sum; } }逻辑说明注意曼哈顿距离里0不参与计算因为空位没有目标位置。targetRow (val - 1) / n和targetCol (val - 1) % n来源于目标状态要求第 i 行第 j 列的数字是i * n j 10 表示空位。如果你用 0-based 坐标这个公式要跟着调整否则隐藏测试全挂。参数说明tiles是二维数组我在构造函数里把hamming和manhattan的计算结果缓存到 final 字段。这里有一个空间权衡每个Board对象都持有一个二维数组如果搜索节点多内存会涨得很快评分器在内存项会检查你是否在Solver里保存了不必要的Board副本。常见做法是在Solver的搜索节点中只存Board引用不复制二维数组除非移动时需要产生一个新棋盘。此外zeroRow和zeroCol也应该缓存否则neighbors()每次都要扫描整个数组找空位。3.4 BoggleSolverTrie 的剪枝与 QU 整体处理Boggle 作业要求给定一个 4×4 的字母骰子棋盘和一本字典找出所有能由相邻字母组成的合法单词。官方给的BoggleBoard会对每一个位置随机分配字母其中有一个特殊处理骰子上可能出现Q但官方把它当作QU两个字母处理。这意味着你在构建字典时得把QU当作一个整体节点否则Q后面必须紧跟U的规则会写得很别扭。我采用的常见做法是把字典构建成一个字符级的 Trie前缀树以单词结尾标记来识别合法单词。DFS 搜索棋盘时如果当前 Trie 节点没有对应字母的子节点就剪枝。这个剪枝是性能关键Boggle 棋盘总字母数不多但暴力 DFS 会遍历所有可能的路径不剪枝的话一个 4×4 棋盘就能跑到秒级之外。public class BoggleSolver { private final TrieNode root; private static class TrieNode { private final TrieNode[] next new TrieNode[26]; private boolean isWord; } private void addWord(String word) { TrieNode node root; for (int i 0; i word.length(); i) { char c word.charAt(i); if (c Q) { // 处理 QU 整体插入 Q 节点后再强制插入 U 节点 i; // 跳过 U if (node.next[Q - A] null) node.next[Q - A] new TrieNode(); node node.next[Q - A]; if (node.next[U - A] null) node.next[U - A] new TrieNode(); node node.next[U - A]; } else { if (node.next[c - A] null) node.next[c - A] new TrieNode(); node node.next[c - A]; } } node.isWord true; } }逻辑说明这段addWord把QU当成了一个不可分割的序列所以在插入QUEEN时先走Q再走U字典树深度增加了两层。在 DFS 中你遇到棋盘上的Q时也必须接着检查下一个字符是不是U并在字典中走QU节点的路径否则像QUIZ这样的词会断在Q的下一层。参数说明next数组长度固定为 26存储空间较小但每次查询要按坐标计算Q - A这是很廉价的运算。有人在搜索时用 HashMap 存子节点理由是稀疏字典省内存但 Boggle 字典通常有几万个词Trie 结构下用数组不仅快而且评分器的内存项也更安全——数组的连续内存是已知量HashMap 的开销和散列冲突都不可控。还有一个隐藏规则单词长度必须至少为 3 才能算分。DFS 过程中如果当前路径长度小于 3即使 Trie 节点标记为isWord也不能加入结果集。这个过滤要在isWord判断里做否则你的答案数量会比官方多出一堆无意义的两字母词。4. 避坑指南我在作业里踩过的 5 个真实大坑4.1 现象equals()与compareTo()违反数理逻辑导致隐藏测试全红很多作业的测试框架会自动调用Board.equals()来比较搜索状态或者用Point.compareTo()来排序。如果你像 Java 默认那样只做引用相等或者用比较Double的斜率比如slope1 slope2就会出现两个明明不同的状态被判为相等或者斜率差 1e-15 的两条线被判为不同这类问题。原因equals()没有覆盖hashCode()或者比较器使用了不可传递的规则。比如CollinearPoints中如果直接用Double.compare(slope1, slope2)而斜率有无穷大和无穷小Double.compare会优先比较数值大小但如果你同时混入-0.0和0.0就会出现比较器返回非 0 但斜率实际相等的情况。解决一律用字段比较与Objects.equals模式对浮点斜率统一用和分治而不是。我在CollinearPoints里最终采用了Point.slopeTo()返回原始 double然后compare()里先比斜率再比 y后比 x成功规避了-0.0与0.0的歧义。Board.equals()里则逐元素比较二维数组不要用Arrays.equals(int[][], int[][])因为它只比较一维引用。4.2 现象8Puzzle内存不足Solver跑到一半 OOM评分器对8Puzzle有 256MB 左右的内存限制但 4×4 棋盘的最优解搜索可能生成几十万个节点。如果你每个搜索节点都保存一份Board的拷贝、一份previous引用、和额外的路径记录堆内存很快见顶。原因A* 的节点里Board持有二维数组移动一次就新建一个int[n][n]旧数组要等 GC但队列里存活节点太多GC 来不及回收。最关键的是没有缓存曼哈顿距离导致每次出队比较优先级时重新算一遍虽然不直接体现在内存却让节点存活时间变长。解决在搜索节点对象中只保存Board board、int moves、GameNode previous三个字段。移动产生新棋盘时只复制数组内容不复制多余元数据。同时把曼哈顿距离缓存到Board实例变量如 3.3 节代码所示。我最终把Solver的PriorityQueue初始容量设为 1024避免队列扩容抖动评分器内存项从 88 分提到 98 分。4.3 现象Percolation的 backwash 问题被测试点抓出来Percolation的isFull()方法要求判断某个格子是否与虚拟顶部连通同时不考虑虚拟底部。正确性测试里有一个隐藏用例专门验证系统已经渗漏但某些与底部连通的格子不应被视为 full。原因使用单一并查集实例同时连接虚拟顶和虚拟底导致只要系统渗漏底部格子也会通过虚拟底被连到虚拟顶于是所有与底部相连的格子全被isFull()判定为 true。解决使用两个并查集实例一个只连接虚拟顶与所有顶部格子用于isFull()另一个同时连接虚拟顶和虚拟底用于percolates()。代码量增加不到二十行但正确性从 87 分跳到 100 分。这个坑几乎每个做过这份作业的人都会踩属于必背套路。4.4 现象BoggleSolver的 QU 特殊字符让字典查询漏词Boggle 棋盘里有时一个骰子标记是Qu而不是Q官方说明把它当成两个字母处理但它们必须作为连续整体出现。我的第一个版本把Q当成普通字符导致QAT这种词永远不会被找到因为 Boggle 里不可能只用 Q 开头而后面没有 U。原因字典树里的Q节点和QU节点路径不一致搜索时没有为Q做特殊分支处理。解决按 3.4 节代码把QU插入为一个两级序列同时在 DFS 中遇到Q时自动把下一个位置视为U并检查 Trie 的QU子节点。注意棋盘上Q的每个邻居位置都可能作为U的候选因此遍历邻居的循环里要单独判断当前格子值是否为Q如果是则强制要求写入的下一个字符是U不能简单地先走一步再走一步那样会绕过QU的绑定关系。4.5 现象BurrowsWheeler的逆变换用索引表重建字符串时出错Burrows-Wheeler 逆变换依赖一个next[]数组它把变换后的字符串t[]中的每个字符映射到其在轮转有序矩阵中的下一行索引。最常见的问题是原始字符串包含大量重复字符比如 DNA 序列如果不用计数方式跳过已经匹配的相同字符next[]数组顺序就错乱导致重建的字符串不是原串。原因第一列中的重复字符出现的顺序必须与最后一列中相同字符的出现顺序一致。假如直接用charAt(i)对应的第一列字符第一次出现的位置构建next当有重复字符时就会按最后一个匹配位置赋值全串错位。解决用计数器维护每个字符在最后一列中出现的次数构建next[int]时按第 i 行字符 当前字符第 k 次出现的位置这个规则填充。这一步必须看纸面推演否则代码读一百遍都看不出错。我在本地用一个ABRACADABRA!的样例反复对照官方参考输出才定位到是计数器初始化为 0 还是 1 的问题。5. 用这些作业反哺面试与工程三条进阶玩法与最后的忠告当你把前面几章的作业都做完并且分数稳定在 90 以上你已经把这门课最有价值的部分消化了一大半。接下来我建议做三件事按性价比排序。第一给每个作业写一个自己版本的 README里面记录你的最初错误、评分器反馈和最终解法。这比任何笔记都有效因为评分器的隐藏测试本身就是最好的教学。我现在还会翻看自己的 8Puzzle 笔记每次都有新发现。第二把Percolation的双并查集技巧迁移到实际工程中——在做连通性分析、图像的 flood fill 或者合并区间时你会发现虚拟节点这个概念无处不在。第三在面试前用BoggleSolver的 Trie 剪枝来热身——很多面试官喜欢让你手写 Trie 或优化 DFS你不会想在那个场合第一次思考QU怎么处理。如果再往前一步我会推荐你自己实现一遍Solver的 A* 搜索但把启发式替换成曼哈顿距离加线性冲突Linear Conflict。线性冲突的思路是如果两个方块在同一行且它们的目标位置也在同一行但顺序相反那么它们至少需要额外一次移动来彼此绕过。把这个冲突次数乘以 2 加到曼哈顿距离上能明显减少搜索节点数。你会发现评分器里那些跑得飞快的参考实现其实都是用这类加强启发式在减少状态空间。甚至可以更进一步把Board的tiles数组改成紧凑的长整型编码用位运算来代替二维数组访问每个状态只需要一个long字段内存占用直接降一个量级。这是很多高性能算法竞赛选手的常规操作也是你理解数据布局对性能影响的最好练习。最后说一个我个人的教训。曾经为了赶截止日期我从某仓库里复制了一份CollinearPoints的完整实现直接提交结果拿了一个编译警告的扣分提示。后来真正自己动手写过一遍才发现那份代码里的比较器把Double.NEGATIVE_INFINITY当普通浮点数处理线上数据刚好有一组点是垂直线全部被判为平行。从那以后我再也不把别人的代码当作正确答案只看作待验证的假设。希望你也能在这套作业里体会到这种从找答案到验证答案的转变——这才是 algs4 真正想教会我们的东西。希望这些踩坑记录能让你少走一段我走过的弯路祝你在提交分数页面看到那个让你满意的百分数。本文还有配套的精品资源点击获取