简介普林斯顿大学《算法》课程编程作业的Java解答集面向正在学习算法与数据结构、渴望通过实际编码提升能力的开发者与自学者。这套解答完整覆盖课程中多道经典作业帮助读者深入理解算法设计思路、数据结构选型与代码实现细节。压缩包共20个文件其中18个Java源文件为核心实现涵盖单词网络、渗透模型、K-D树、随机队列、接缝裁剪、共线点检测及八数码问题等主题另有1个Markdown说明文档辅助梳理结构1个License文件声明许可整体仅28KB便携易用。目前已有243人学习下载对算法学习者具备参考价值。通过研读源码与说明读者可按作业主题逐项练习学习排序、搜索、图算法与动态规划在真实场景中的应用同时借鉴Java面向对象设计、异常处理及集合框架的实战技巧为后续软件开发或数据分析方向奠定扎实的算法基础。1. 把 algs4 编程作业从“看懂答案”变成“自己会写”这份资源到底解决了什么很多人第一次接触 algs4-Programming-Assignment 这套编程习题解答时都会误以为它只是“抄答案用的代码仓库”但真正被这套作业折磨过的人会告诉你一个反直觉的结论卡住你的从来不是算法本身而是那些隐藏在 API 约定、内存限制和边界条件里的细节。这套来自某常春藤名校算法课程的编程作业用 Java 实现了并查集、平衡树、最短路径、正则表达式、后缀数组等一系列经典结构而这份习题解答把每道题从问题建模、数据结构选型到易错点全部拆开适合正在跟课、准备面试刷题、或者想用 Java 系统补一遍数据结构的从业者。它不是一个“拿来跑通就完事”的答案包而是一份能让你照着复现、并真正理解作业评分逻辑的落地手册。2. 作业体系与环境搭建先把九个题目的考点和运行环境吃透这一章不急着贴代码先解决两个问题这套编程作业到底考什么以及本地环境要怎么配才能达到课程评测系统的要求。很多人栽在第一步不是因为算法不会而是因为环境里缺了 algs4.jar、不知道评分脚本怎么跑、更不知道 checkstyle 会被扣分从一开始就输了起跑线。2.1 九道作业到底在考什么从并查集到循环后缀数组先看 Part I 的五道题Percolation 用加权快速合并WeightedQuickUnionUF模拟渗流模型考的是并查集建模和虚拟节点技巧Deque 和 RandomizedQueue 要求实现双端队列和随机队列考泛型容器、迭代器 fail-fast 机制和数组扩容策略Collinear Points 考排序加斜率比较点共线的枚举顺序必须保证最坏情况复杂度8 Puzzle 用 A* 搜索和优先队列考启发式函数的设计与不可解判定Kd-Trees 考平衡树与空间划分用红黑树或 2d-tree 实现范围搜索和最近邻查找。到了 Part IIWordNet 用有向图做最短的祖先路径本质是 DAG 上 BFSSeam Carving 是图像接缝裁剪考动态规划和像素能量计算Baseball Elimination 用最大流模型判断棒球队是否被淘汰Boggle 用 Trie 加 DFS 做单词搜索考剪枝和字典结构Burrows-Wheeler 则是数据压缩三大组件考循环后缀数组和逆变换的 next 数组推导。整套作业覆盖了本科算法课最核心的十几个专题每一道题都有明确的时间和空间上限比如 Percolation 要求在 2 秒内完成 200×200 网格的蒙特卡洛模拟Deque 的每个操作必须是常数均摊时间。这套解答的价值恰恰在这里它不是把九道题的代码简单罗列而是对每一道题的“评分界限”做了说明。比如 Percolation 只要用两个 WeightedQuickUnionUF 实例就能避开回流backwash问题但这会让内存使用翻倍如何在 64 位 JVM 的对象头开销下不超限就是这道题真正考人的地方。2.2 环境准备algs4.jar、标准输入输出与本地调试这套作业强依赖课程自带的 algs4.jar里面有 StdIn、StdOut、StdDraw、StdRandom 这些工具类还有 WeightedQuickUnionUF、MinPQ、TrieSET 等数据结构实现。作业模板里一般不让你直接改这些类但可以用它们来写答案。拿到资源包后的第一步是把它整理成一个标准的 Java 项目结构。# 目录规划lib 放 jarsrc 放作业代码bin 放编译输出 mkdir -p ~/algs4-project/{lib,src,bin} # 把资源中的 algs4.jar 复制到 lib 目录 cp /path/to/download/algs4.jar ~/algs4-project/lib/ # 设置 CLASSPATH让 javac 和 java 都能找到依赖 export CLASSPATH$HOME/algs4-project/lib/algs4.jar:$HOME/algs4-project/bin:. # 编译作业入口 javac -cp $CLASSPATH -d $HOME/algs4-project/bin src/Percolation.java # 跑课程提供的可视化器 java -cp $CLASSPATH PercolationVisualizer input.txt代码说明javac 的-d指定编译输出目录-cp是 classpath把 algs4.jar 放进去后 javac 才能找到 StdIn 这些类运行可视化器不需要额外写 main因为 PercolationVisualizer 里已经定义了测试输入和绘图逻辑。参数说明-Xmx512m可以在java命令后加用来限制堆内存这个参数在排查内存超限时非常有用后面第 5 章会专门讲。如果你用集成开发环境核心操作是一样的新建项目后把 algs4.jar 作为外部库引入再把/src目录标记为源码根目录。唯一要留意的是不要把自己写的类放到默认包以外的地方去作业评测系统要求类必须处于默认包带包名会导致编译器在自动评测时找不到主类。2.3 让评分规则前置checkstyle 与内存 / 时间上限课程的自动评测系统会同时检查三件事正确性、复杂度和代码风格。正确性通过单元测试样例来判定复杂度用时间或内存上限来硬性限制风格则用 checkstyle 配置来约束。很多人前面两关过了最后因为 80 字符行宽、命名不规范这类问题被扣分非常不划算。# 安装课程提供的 checkstyle 配置后本地执行静态检查 java -jar checkstyle-8.12-all.jar -c checkstyle.xml src/Percolation.java # 检查结果 # 如果一切正常输出类似 # Starting audit... # Audit done.这里 checkstyle 的-c参数指定配置文件课程的标准配置会检查行宽、import 顺序、空行规则、方法长度等。初次跑大概率会有一堆警告最常见的是“Line is longer than 80 characters”。我的习惯是把 checkstyle 做成构建工具的一部分每次提交前在项目根目录跑一遍而不是等到评测系统返回扣分记录才回头改。这类风格问题看起来琐碎但在自动评分系统里它占至少 5% 的分值而且一旦积累到十几处你就很难分辨到底是功能错还是风格错了。环境搭好之后接下来以 Part I 的两道题为例看这份资源里的代码是怎么组织的。3. 把 Part I 的经典题目真正写对Percolation 与 Deque 的完整拆解Part I 的前两道题是很多人的第一个门槛。Percolation 考并查集的建模能力Deque 考容器实现的基本功这两道题如果只抄答案而不理解内部机制到 Kd-Trees 时一定会翻车因为前面的坑会在后面以更复杂的形式重复出现。3.1 Percolation并查集建模与回流的真相Percolation 的问题背景是一个 n×n 的网格每个格点随机开放或封闭当顶部和底部通过开放格点连通时系统渗流。最直接的并查集建模方式是引入一个虚拟顶部节点和一个虚拟底部节点所有顶部格点与虚拟顶节点合并所有底部格点与虚拟底节点合并判断是否渗流就等价于判断虚拟顶节点和虚拟底节点是否连通。public class Percolation { private final int n; private final boolean[] open; // 格点开放状态索引 row * n col private final WeightedQuickUnionUF uf; // 主并查集含虚拟顶和虚拟底 private final WeightedQuickUnionUF ufTop; // 只含虚拟顶的并查集 private final int top; // 虚拟顶索引 private final int bottom; // 虚拟底索引 public Percolation(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); this.n n; open new boolean[n * n 1]; uf new WeightedQuickUnionUF(n * n 2); ufTop new WeightedQuickUnionUF(n * n 1); top n * n; bottom n * n 1; } private int index(int row, int col) { return (row - 1) * n col; // 题目说的 row/col 从 1 开始这里改成 0 基 } public void open(int row, int col) { int idx index(row, col); if (open[idx]) return; open[idx] true; if (row 1) { uf.union(idx, top); ufTop.union(idx, top); } if (row n) uf.union(idx, bottom); int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int nr row d[0], nc col d[1]; if (nr 1 nr n nc 1 nc n open[index(nr, nc)]) { uf.union(idx, index(nr, nc)); ufTop.union(idx, index(nr, nc)); } } } public boolean isFull(int row, int col) { return open[index(row, col)] ufTop.connected(index(row, col), top); } public boolean percolates() { return uf.connected(top, bottom); } }这段代码最关键的是两个并查集的取舍uf负责判断系统是否渗流它同时连了虚拟顶和虚拟底ufTop只连虚拟顶用来判断某个格点是否被顶部“浸满”。如果不加ufTop直接用uf.connected(idx, top)判断 isFull就会出现回流问题底部与虚拟底连通后底部一大片区域会通过虚拟底反向上溯被错误地判定为“渗流路径上的节点”。这是 Percolation 作业里最著名的黑匣子历年不知道坑了多少人。迁移到其他场景时要注意如果你只是判断整体是否连通一个并查集就够一旦需要区分“与起点连通”和“与终点连通”就要考虑是否要拆成多个并查集或者引入额外的状态数组。这个取舍在 WordNet 那道题里还会出现一次到时候你会发现同样的思维模型换了一层包装。3.2 Deque 与 RandomizedQueue泛型容器的迭代器血泪Deque 要求实现双向队列所有操作均摊 O(1)RandomizedQueue 要求随机队列迭代器必须产生随机顺序且和队列操作互不影响。这两道题表面上看是链表基本功真正扣分的点全在迭代器上。import java.util.Iterator; import java.util.NoSuchElementException; public class DequeItem implements IterableItem { private Node first, last; private int n; private int modCount; // 结构修改计数 private class Node { Item item; Node prev; Node next; } public void addFirst(Item item) { if (item null) throw new IllegalArgumentException(); Node oldFirst first; first new Node(); first.item item; first.next oldFirst; first.prev null; if (oldFirst null) last first; else oldFirst.prev first; n; modCount; } public void addLast(Item item) { if (item null) throw new IllegalArgumentException(); Node oldLast last; last new Node(); last.item item; last.next null; last.prev oldLast; if (oldLast null) first last; else oldLast.next last; n; modCount; } public Item removeFirst() { if (n 0) throw new NoSuchElementException(); Item item first.item; first first.next; if (first null) last null; else first.prev null; n--; modCount; return item; } public IteratorItem iterator() { return new IteratorItem() { private Node cur first; private final int expectedModCount modCount; public boolean hasNext() { if (expectedModCount ! modCount) { throw new java.util.ConcurrentModificationException(); } return cur ! null; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item cur.item; cur cur.next; return item; } }; } }迭代器里的modCount和expectedModCount是这道题最容易忽略的细节。评测系统会创建一个迭代器在遍历过程中调用addFirst修改双端队列然后期望迭代器立刻抛出ConcurrentModificationException如果没抛这一项直接零分。我在第一次写的时候没加这个检查跑本地样例时因为遍历次数短侥幸通过提交后立刻被系统打回。另一个容易掉进去的坑是 Node 类的访问权限和 remove 方法的实现。这里没写 remove(Item)是因为课程要求的 API 里 Deque 只需要removeFirst/removeLast不要求按值删除但 RandomizedQueue 的sample()和dequeue()必须随机且均匀实现随机迭代器时最稳妥的做法是内部复制一份数组快照然后随机打乱顺序。不要试图在链表上直接做随机访问那样时间复杂度会超标。这类“看着能做实际会超时”的解决方案在 8 Puzzle 和 Kd-Trees 里还会反复遇到早点形成“先看复杂度上限再动手写”的习惯能省很多时间。4. Part II 实战Seam Carving 与 Burrows-Wheeler 的算法落地Part II 的作业难度比 Part I 高一个台阶尤其是 Seam Carving 和 Burrows-Wheeler。前者需要把图像处理问题抽象成动态规划后者需要你彻底理解后缀数组的循环展开。如果 Part I 是靠记忆代码混过去的到这两道题一定会漏馅反过来把这两道题啃下来再去做其他数据压缩或图像算法的题目会发现思路基本都是通的。4.1 Seam Carving能量图与动态规划找接缝Seam Carving 的目标是找到一条从图像顶部到底部的像素路径接缝移除这条路径后图像宽度减一同时尽量保留视觉重要区域。核心分三步计算每个像素的能量、用动态规划找最小能量路径、移除路径上的像素。public class SeamCarver { private int[][] color; // 存储 RGB 值color[x][y] 对应像素颜色 private int width; private int height; public double energy(int x, int y) { if (x 0 || x width || y 0 || y height) { throw new IllegalArgumentException(out of bounds); } if (x 0 || x width - 1 || y 0 || y height - 1) { return 1000.0; // 边界像素能量设为大值避免接缝从边缘走 } double rx gradient(color[x - 1][y], color[x 1][y], 0); double gx gradient(color[x - 1][y], color[x 1][y], 1); double bx gradient(color[x - 1][y], color[x 1][y], 2); double ry gradient(color[x][y - 1], color[x][y 1], 0); double gy gradient(color[x][y - 1], color[x][y 1], 1); double by gradient(color[x][y - 1], color[x][y 1], 2); return Math.sqrt(rx * rx gx * gx bx * bx ry * ry gy * gy by * by); } public int[] findVerticalSeam() { // distTo[y][x] 表示从顶部到 (x,y) 的最小累计能量 double[][] distTo new double[height][width]; int[][] edgeTo new int[height][width]; for (int x 0; x width; x) { distTo[0][x] energy(x, 0); edgeTo[0][x] -1; } for (int y 1; y height; y) { for (int x 0; x width; x) { double best Double.POSITIVE_INFINITY; int bestX -1; for (int dx -1; dx 1; dx) { int nx x dx; if (nx 0 || nx width) continue; if (distTo[y - 1][nx] best) { best distTo[y - 1][nx]; bestX nx; } } distTo[y][x] best energy(x, y); edgeTo[y][x] bestX; } } // 回溯找到最优路径起点 int bestX 0; for (int x 1; x width; x) { if (distTo[height - 1][x] distTo[height - 1][bestX]) bestX x; } int[] seam new int[height]; for (int y height - 1; y 0; y--) { seam[y] bestX; bestX edgeTo[y][bestX]; } return seam; } }动态规划的转移方程是到达当前像素的最小能量等于上一行相邻三个像素中的最小能量加上当前像素自身的能量。edgeTo用来记录路径来源回溯时从底部最小累计能量的像素开始逐行向上跟踪。这里最容易翻车的是边界处理如果直接把边界像素的能量设为 0动态规划会倾向于沿着图像边缘切一条线因为这看起来能量最低课程评测会故意用纯色图像来测一旦边界没设大值性能测试样例里就会出现明显错误。实际写的时候还要注意horizontal seam 和 vertical seam 是互逆操作如果你实现了findVerticalSeam再用转置图像的方式去复用代码可以少写一半逻辑但转置操作本身要同步更新width和height很多人漏了这一步导致图像移除接缝后尺寸错乱。这个问题属于“看起来是小 bug跑起来处处不对”的典型。4.2 Burrows-Wheeler循环后缀数组与 next 数组推导Burrows-Wheeler 这道题由三个组件构成BurrowsWheeler 变换、循环后缀数组、以及一个基于前缀表的重构方法。它的难点在于逆变换不是直观地从编码直接还原原文而是要用 next 数组一步步跳回去。public class BurrowsWheeler { public static void encode() { String s BinaryStdIn.readString(); int n s.length(); int[] suffix new int[n]; for (int i 0; i n; i) suffix[i] i; // 对循环后缀排序比较时用环形索引 Arrays.sort(suffix, (a, b) - { for (int k 0; k n; k) { char ca s.charAt((a k) % n); char cb s.charAt((b k) % n); if (ca ! cb) return ca - cb; } return 0; }); int first 0; for (int i 0; i n; i) { if (suffix[i] 0) { first i; break; } } BinaryStdOut.write(first); for (int i 0; i n; i) { int idx (suffix[i] n - 1) % n; BinaryStdOut.write(s.charAt(idx)); } BinaryStdOut.flush(); } }循环后缀数组的排序如果直接在比较器里做字符串截取复杂度会是 O(n^2 log n)必然超时常见做法是用 Java 的 Arrays.sort 配合自定义比较器通过取模访问原字符串避免复制或者用后缀数组的标准倍增算法。这套作业给出的是循环后缀的思路也就是把每个后缀当成环形字符串来处理这个技巧在数据压缩类问题里非常常见。逆变换的 next 数组推导是这道题最黑匣子的地方。原理是对最后一列做排序可以得到第一列然后根据相同字符在最后一列出现的位置与第一列出现位置的对应关系构造出 next 数组。写逆变换时最容易出错的是字符相同的情况比如字符串为 banana 时多个 a 的位置必须按稳定性规则一一对应顺序一乱整个还原结果就错。我的经验是先把课程给出的样例在纸上手工推导一遍再用代码去碰撞否则直接在代码层面调试稀疏的 next 数组会非常痛苦。5. 避坑手册五个让人翻车的经典问题与排查路径这套作业的评测系统只会返回一个红叉或绿勾不会告诉你具体哪条样例错了。所以本地复现评测逻辑、提前排查边界条件几乎是唯一可靠的调试手段。下面这五条是我在这套题目上反复见到的踩坑记录全部按现象到原因的路径来写。5.1 正确性玄学本机样例全过提交却 Red现象一Percolation 的 isFull 结果与预期不符但 percolates() 完全正确。本机用课程提供的可视化器跑 input10.txt 时渗流路径绘制基本正常可一旦开启“显示所有被浸满格点”的模式底部一大片封闭区域被错误标记为蓝色。原因典型的回流backwash问题。主并查集把虚拟底节点也连进去了当系统渗流后底部区域会通过虚拟底节点与顶部连通导致 isFull 在判断时把“和底部连通”误判为“和顶部连通”。解决如 3.1 节所示单独维护一个只连接虚拟顶节点的并查集ufTopisFull 只用这个并查集判断。从那以后我对所有“是否与某端连通”的判断题都会刻意追问一句这个连通性判断会不会受另一端节点的影响。现象二Deque 的迭代器在部分样例上抛ConcurrentModificationException但本机测试没复现。本机遍历时没有混入结构性修改操作提交后评测系统模拟了“迭代过程中 addFirst”的场景直接返回运行时异常。原因迭代器没有记录modCount或者记录了但hasNext()没有做并发修改检查。课程要求迭代器在检测到结构修改时必须快速失败这是 Java 集合框架的标准约定。解决在每个 add/remove 方法里递增modCount在迭代器的next()和hasNext()中比较expectedModCount与modCount不一致就抛异常。这个坑在 RandomizedQueue 中同样存在而且由于随机队列内部用数组实现迭代器更容易遗漏写检查。5.2 性能与内存超时与超限的排查顺序现象三Percolation 的蒙特卡洛模拟在 n200 时运行 5 秒以上提交直接超时。本机跑小规模样例n20很快但当采样次数达到 1000 次时总时间明显超出课程给的 2 秒上限。原因open()方法里每打开一个格点就新建一个 WeightedQuickUnionUF 实例或者每次都用find()去扫描整个网格判断连通性。并查集的合并操作本身是近 O(1) 的但反复重新初始化会把复杂度拉回 O(n^2)。解决把并查集实例作为 Percolation 类的成员变量整个蒙特卡洛模拟复用同一个实例另外open 操作中只对它实际影响的四个邻居做 union不要对整行整列做循环。排查性能问题时我一般先用-Xmx512m限制堆内存再看 GC 日志如果频繁 Full GC多半是数据结构重复创建。现象四提交后提示内存超限本机跑同样的代码却正常。本机用的是 64 位 JVM 默认配置堆内存充足评测环境对每个作业设置了硬性内存上限Deque 或 RandomizedQueue 的数组扩容策略太激进一上来就申请 10 万容量的数组。原因数组初始化容量过大或者扩容时翻倍策略不合理。RandomizedQueue 的数组必须采用“满则翻倍、低于四分之一则减半”的策略这能保证常数均摊时间同时不浪费内存如果只翻倍不缩容删除操作之后数组浪费的空间会被内存检查器抓个正着。解决严格按标准策略实现 resize并且数组初始容量设置为 1 或 2不要一次性申请大块内存。这类问题在本地几乎无法感知因为现代机器的内存足够大只有到了评测沙箱里才会暴露。现象五checkstyle 报错几十条但代码跑起来完全正常提交后被扣掉风格分。最常见的报错是“Line is longer than 80 characters”其次是 method 参数过多、缺少Override注解、if 语句没有花括号等。原因课程标准 checkstyle 配置和常规工程配置不同它更严格比如要求所有方法都用 Javadoc 注释import 必须按字母序排列。解决本地把课程提供的 checkstyle.xml 放进项目根目录每次提交前先跑java -jar checkstyle-8.12-all.jar -c checkstyle.xml src/*.java把警告清零再提交。如果你用的是集成开发环境直接把 checkstyle 插件挂上去保存即触发检查就不会积累到最后一堆红色波浪线。6. 把作业代码改造成通用工具一份可复用的算法落地实践这套作业的代码在通过评测之后如果直接删除就太可惜了。我一般会把其中几个核心类抽出来改造成通用的工具模块放入自己的代码工具箱。比如 Percolation 的并查集建模可以抽象成一个“网格连通性分析器”输入任意二维网格和开放条件输出连通分量和渗流路径Seam Carving 的能量图加动态规划可以改造成一个命令行图片缩放工具支持指定目标宽度并自动保留图像主体区域。这个改造过程比单纯刷题更有价值因为它强迫你重新审视类接口设计。以 Seam Carving 为例改造时我会去掉与课程评测相关的pic.txt输入格式改成直接读 PNG/JPG 图片输出缩放后的图片。具体做法是把能量计算函数从int[][] color改成接收BufferedImage把动态规划逻辑抽成独立的SeamFinder类让图像解码、接缝计算、像素移除三层互相解耦。实际改造中我发现最耗时间的不是算法本身而是像素移除时的坐标同步——每移除一条垂直接缝右边所有像素的 x 坐标都要减一这个更新如果放到像素级循环里性能会指数级恶化正确做法是先把整条接缝的坐标记录下来一次性重建目标图像。另外一个验证技巧本地建立一个简单的“评测模拟脚本”用随机输入跑完整流程然后和课程给出的参考输出做比对再把输入规模放大 10 倍看时间是否线性增长。从那以后我每次做完一道题都会强制走一遍“checkstyle 清零、小规模正确性验证、大规模性能压测”这三步这套习惯帮我躲过了绝大多数评测系统的红叉。希望帮到你。本文还有配套的精品资源点击获取