简介这份资源是普林斯顿大学算法课程Coursera编程作业的Java解答合集面向正在学习算法、需要对照参考或自测练习的学习者覆盖排序、图算法、动态规划等经典主题及配套数据结构实现。压缩包共20个文件以18个Java源码为主体涵盖Percolation、KdTree、WordNet、SeamCarver、8puzzle等作业模块另附1个README说明与1个LICENSE授权文件整体约28KB体量轻便、便于按模块查阅。已有243人学习下载说明其在算法自学者中有一定参考价值。读者可从中获得各次作业的完整实现思路包括并查集、优先队列、图搜索与最短路径等算法的落地写法以及面向对象设计、异常处理和复杂度分析的实践范例适合作为课程作业的对照参考与调试排错素材帮助构建扎实的算法基础。1. 从一份“刷完就能跑”的算法习题解答说起很多人学算法课视频看得懂一到编程作业就卡壳题目读了三遍不知道从哪下手写完提交又卡在隐藏用例上最后连自己错在哪都说不清。这份 algs4 编程习题解答就是冲着这个痛点来的——它把普林斯顿算法课程那套 Java 编程作业逐题做了一遍每道题都有可编译、可运行的完整实现从并查集、排序、优先队列到图搜索、最短路径、字符串匹配覆盖了课程主线上的全部编程任务。适合两类人一类是正在跟这门课、想对照参考实现把作业啃下来的学习者另一类是已经写过 Java、想拿这些经典算法当练手素材、顺便看看别人怎么组织代码的开发者。它不是一份只贴答案的题解而是一套能直接javac编译、用课程自带测试脚本跑起来的工程代码。2. 项目结构与技术选型为什么是纯 Java 标准输入输出2.1 目录组织按作业周次切分一题一包这类课程作业解答的常见组织方式是按作业单元分目录每个目录对应一次编程任务目录内放该题的全部源码和测试数据。我拆过的版本大致是这个结构algs4-programming-assignment/ ├── build.xml # Ant 构建脚本统一编译与测试入口 ├── lib/ │ ├── algs4.jar # 课程官方算法库StdIn/StdOut/StdDraw 等 │ └── junit-4.13.2.jar # 单元测试依赖 ├── src/ │ ├── percolation/ # 渗流问题并查集 蒙特卡洛 │ │ ├── Percolation.java │ │ ├── PercolationStats.java │ │ └── PercolationVisualizer.java │ ├── collinear/ # 共线点排序 斜率比较 │ │ ├── Point.java │ │ ├── BruteCollinearPoints.java │ │ └── FastCollinearPoints.java │ ├── queues/ # 双端队列与随机队列 │ │ ├── Deque.java │ │ ├── RandomizedQueue.java │ │ └── Permutation.java │ ├── kdtree/ # 二维范围搜索 │ │ ├── PointSET.java │ │ └── KdTree.java │ ├── wordnet/ # 词网有向图 最短公共祖先 │ │ ├── WordNet.java │ │ ├── SAP.java │ │ └── Outcast.java │ └── seam/ # 接缝裁剪最短路径 │ ├── SeamCarver.java │ └── ... └── test/ # 各题的本地测试用例这个结构的好处是每道题自成一个包互不干扰编译时按包名隔离测试时也能单独跑某一题。lib/algs4.jar是课程官方提供的算法库里面封装了标准输入输出、绘图和若干基础数据结构作业代码大量依赖它所以这个 jar 必须放在类路径里否则一编译就是package edu.princeton.cs.algs4 does not exist。2.2 技术选型为什么不用 Maven而用 Ant课程作业的提交环境对构建工具没有硬性要求但官方推荐的测试脚本是基于 Ant 的build.xml。选 Ant 而不是 Maven 的原因很实际作业规模小依赖就两个 jar不需要依赖传递和仓库管理Ant 的 target 写起来直观ant compile、ant test一眼能看懂在干什么更重要的是课程提供的checkstyle和测试脚本本身就是 Ant 任务跟着官方走能少踩很多环境坑。!-- build.xml 关键片段编译与测试两个 target -- project namealgs4-assignment defaultcompile basedir. property namesrc.dir valuesrc/ property namebuild.dir valuebuild/ property namelib.dir valuelib/ !-- 类路径官方算法库 JUnit -- path idclasspath fileset dir${lib.dir} includes**/*.jar/ /path target namecompile mkdir dir${build.dir}/ javac srcdir${src.dir} destdir${build.dir} classpathrefclasspath includeantruntimefalse encodingUTF-8 debugtrue/ /target target nametest dependscompile junit printsummarytrue haltonfailuretrue classpath pathelement location${build.dir}/ path refidclasspath/ /classpath formatter typeplain/ batchtest forktrue todir${build.dir} fileset dir${build.dir} includes**/*Test.class/ /batchtest /junit /target /project这段脚本里几个参数值得说清楚srcdir指向源码根目录destdir是编译产物目录classpathref把lib下所有 jar 一次性挂上省得逐个写。includeantruntimefalse是消除 Ant 自带运行时库混入类路径的警告encodingUTF-8防止源码里有中文注释时编译报编码错误。testtarget 依赖compile用batchtest自动扫描所有以Test结尾的类并执行haltonfailuretrue表示一旦有测试失败就中断适合本地快速验证。2.3 依赖清单与版本约束依赖作用放置位置注意点algs4.jar标准输入输出、绘图、基础容器lib/必须与课程版本一致否则 API 可能对不上junit 4.x本地单元测试lib/用 JUnit 4 而非 5因为官方测试脚本按 4 的注解写JDK 8编译运行系统环境课程代码大量用泛型与自动装箱JDK 8 起步依赖少是这类项目的优势但也意味着所有基础能力都得自己写或从algs4.jar里拿。比如Deque和RandomizedQueue这两题题目明确要求不能用java.util里的现成容器必须自己用数组或链表实现这正是练手价值所在。3. 核心模块拆解从并查集到最短路径的代码实现3.1 Percolation加权并查集 虚拟顶点渗流问题是整门课第一个编程作业也是最能体现“算法选对了代码就短”的一题。题目给一个 N×N 的格子每个格子要么开放要么阻塞判断是否存在一条从顶到底的开放路径。暴力搜索会超时正确解法是并查集把每个开放格子与上下左右相邻的开放格子合并再引入两个虚拟顶点分别代表“顶部”和“底部”只要这两个虚拟顶点连通就说明存在贯通路径。public class Percolation { private final int n; private final int[] parent; // 并查集父指针 private final int[] size; // 每棵树的大小用于加权合并 private final boolean[] open; // 格子是否开放 private int openCount; private final int virtualTop; // 虚拟顶部顶点 private final int virtualBottom; // 虚拟底部顶点 public Percolation(int n) { if (n 0) throw new IllegalArgumentException(n must be positive); this.n n; int total n * n 2; // 多出两个虚拟顶点 parent new int[total]; size new int[total]; open new boolean[n * n]; for (int i 0; i total; i) { parent[i] i; size[i] 1; } virtualTop n * n; virtualBottom n * n 1; } // 二维坐标映射到一维索引注意题目行列从 1 开始 private int index(int row, int col) { return (row - 1) * n (col - 1); } private int find(int p) { while (p ! parent[p]) { parent[p] parent[parent[p]]; // 路径压缩 p parent[p]; } return p; } private void union(int p, int q) { int rootP find(p), rootQ find(q); if (rootP rootQ) return; // 加权合并小树挂到大树下面保证树高对数级 if (size[rootP] size[rootQ]) { parent[rootP] rootQ; size[rootQ] size[rootP]; } else { parent[rootQ] rootP; size[rootP] size[rootQ]; } } 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) union(idx, virtualTop); if (row n) union(idx, virtualBottom); if (row 1 isOpen(row - 1, col)) union(idx, index(row - 1, col)); if (row n isOpen(row 1, col)) union(idx, index(row 1, col)); if (col 1 isOpen(row, col - 1)) union(idx, index(row, col - 1)); if (col n isOpen(row, col 1)) union(idx, index(row, col 1)); } public boolean percolates() { return find(virtualTop) find(virtualBottom); } }这段代码的关键点有三个。第一是索引映射题目行列从 1 开始而数组从 0 开始index方法统一做转换避免到处写-1出错。第二是加权合并加路径压缩size数组记录每棵树节点数合并时小树挂大树find里顺手做路径压缩两者结合后单次操作接近常数时间N 取到几千也不会超时。第三是虚拟顶点顶部行和底部行在open时直接与虚拟顶点合并percolates只需比较两个虚拟顶点的根是否相同逻辑干净且 O(1)。PercolationStats则是在Percolation之上做蒙特卡洛模拟重复 T 次实验每次随机开放格子直到贯通记录开放比例最后算均值和置信区间。这里常见的坑是随机数生成器要复用同一个实例每次实验重新new Random()会导致结果不可复现。3.2 Deque 与 RandomizedQueue数组实现的双端队列与随机队列这两题考的是基础数据结构的手写能力题目禁止使用java.util容器。Deque要求支持两端增删和迭代RandomizedQueue要求dequeue随机返回一个元素且各元素等概率。用数组实现是常见做法核心是环形缓冲区和迭代器的正确性。public class DequeItem implements IterableItem { private Item[] items; private int head; // 队头下标 private int tail; // 队尾下标指向下一个空位 private int count; SuppressWarnings(unchecked) public Deque() { items (Item[]) new Object[8]; head 0; tail 0; count 0; } public boolean isEmpty() { return count 0; } public int size() { return count; } private void resize(int capacity) { Item[] copy (Item[]) new Object[capacity]; for (int i 0; i count; i) { copy[i] items[(head i) % items.length]; // 按逻辑顺序搬移 } items copy; head 0; tail count; } public void addFirst(Item item) { if (item null) throw new IllegalArgumentException(); if (count items.length) resize(2 * items.length); head (head - 1 items.length) % items.length; // 环形回退 items[head] item; count; } public void addLast(Item item) { if (item null) throw new IllegalArgumentException(); if (count items.length) resize(2 * items.length); items[tail] item; tail (tail 1) % items.length; count; } public Item removeFirst() { if (isEmpty()) throw new java.util.NoSuchElementException(); Item item items[head]; items[head] null; // 避免对象游离 head (head 1) % items.length; count--; if (count 0 count items.length / 4) resize(items.length / 2); return item; } Override public java.util.IteratorItem iterator() { return new java.util.IteratorItem() { private int i 0; public boolean hasNext() { return i count; } public Item next() { if (!hasNext()) throw new java.util.NoSuchElementException(); Item item items[(head i) % items.length]; i; return item; } public void remove() { throw new UnsupportedOperationException(); } }; } }环形数组的难点全在取模运算上addFirst时head往前退一格退到 0 之前要绕回数组末尾所以写(head - 1 items.length) % items.length加items.length是为了避免负数取模。resize时不能简单复制因为逻辑顺序可能跨过数组边界必须从head开始按逻辑顺序逐个搬移。removeFirst里把槽位置null是防止对象游离否则被删元素仍被数组引用垃圾回收器收不走。缩容阈值取length / 4而不是/ 2是为了避免在临界点反复扩容缩容的抖动。RandomizedQueue的随机性来自dequeue时随机选一个下标把该位置元素与末尾交换后弹出这样每个元素被选中的概率都是 1/n且不需要额外打乱整个数组。3.3 KdTree二维范围搜索与最近邻KdTree 这题要求实现二维平面上的范围搜索和最近邻查询并且要和暴力版PointSET做性能对比。核心是交替按 x、y 坐标切分的二叉搜索树插入时按层级决定比较哪个维度。public class KdTree { private Node root; private int size; private static class Node { private final Point2D p; private final boolean vertical; // 该节点按 x 还是 y 切分 private Node left, right; Node(Point2D p, boolean vertical) { this.p p; this.vertical vertical; } } public void insert(Point2D p) { if (p null) throw new IllegalArgumentException(); root insert(root, p, true); } private Node insert(Node node, Point2D p, boolean vertical) { if (node null) { size; return new Node(p, vertical); } int cmp vertical ? Double.compare(p.x(), node.p.x()) // 竖线切分比 x : Double.compare(p.y(), node.p.y()); // 横线切分比 y if (cmp 0) node.left insert(node.left, p, !vertical); else if (cmp 0) node.right insert(node.right, p, !vertical); // cmp 0 视为重复点直接忽略 return node; } public IterablePoint2D range(RectHV rect) { java.util.ListPoint2D result new java.util.ArrayList(); range(root, rect, result); return result; } private void range(Node node, RectHV rect, java.util.ListPoint2D out) { if (node null) return; if (rect.contains(node.p)) out.add(node.p); // 剪枝只有子树可能落在矩形内才继续递归 if (node.vertical) { if (rect.xmin() node.p.x()) range(node.left, rect, out); if (rect.xmax() node.p.x()) range(node.right, rect, out); } else { if (rect.ymin() node.p.y()) range(node.left, rect, out); if (rect.ymax() node.p.y()) range(node.right, rect, out); } } }insert的递归里vertical标志决定当前层比较 x 还是 y插入后子节点翻转该标志这就是 kd 树交替切分的本质。range的剪枝是性能关键如果查询矩形的 x 范围完全在当前节点左侧右子树根本不用进反之亦然。没有剪枝的话范围搜索退化成遍历整棵树和暴力版没区别性能对比那一栏会很难看。最近邻查询nearest用优先队列或递归加距离剪枝都能做递归版更直观维护当前最近距离递归时先走可能更近的一侧再判断另一侧到切分线的距离是否小于当前最近距离小于才继续搜。3.4 WordNet 与 SAP有向图上的最短公共祖先词网这题把同义词集建成有向无环图要求计算两个词之间的最短公共祖先路径长度。SAP类负责在图上做广度优先搜索求最短路径WordNet负责加载数据并校验图是 DAG。public class SAP { private final Digraph graph; public SAP(Digraph g) { if (g null) throw new IllegalArgumentException(); this.graph new Digraph(g); // 防御性拷贝避免外部修改 } // 返回 {祖先, 路径长度}无公共祖先返回 {-1, -1} public int[] length(int v, int w) { validate(v); validate(w); int[] distV bfs(v); int[] distW bfs(w); int bestAncestor -1, bestLength Integer.MAX_VALUE; for (int i 0; i graph.V(); i) { if (distV[i] 0 distW[i] 0) { int len distV[i] distW[i]; if (len bestLength) { bestLength len; bestAncestor i; } } } return bestAncestor -1 ? new int[]{-1, -1} : new int[]{bestAncestor, bestLength}; } private int[] bfs(int source) { int[] dist new int[graph.V()]; java.util.Arrays.fill(dist, -1); java.util.QueueInteger queue new java.util.ArrayDeque(); dist[source] 0; queue.offer(source); while (!queue.isEmpty()) { int v queue.poll(); for (int w : graph.adj(v)) { if (dist[w] 0) { dist[w] dist[v] 1; queue.offer(w); } } } return dist; } }length的思路是分别从两个词出发做 BFS得到各自到所有可达节点的距离然后遍历所有节点找两边都可达且距离和最小的那个就是最短公共祖先。bfs里用ArrayDeque当队列dist数组初始化为 -1 表示不可达入队时更新距离保证每个节点只入队一次。构造器里对传入的图做防御性拷贝是血泪经验——如果直接持有外部引用调用方后续修改图会悄悄改变 SAP 的行为排查起来非常费劲。WordNet加载数据时要校验三件事每个同义词集 id 在范围内、图无环、每个词至少属于一个同义词集。无环校验用拓扑排序或 DFS 染色都行漏掉这一步后面 SAP 在环上跑 BFS 虽然不会死循环但语义已经错了。4. 跑起来环境准备、编译与测试的完整步骤4.1 环境准备与依赖放置先把 JDK 装好java -version确认是 8 或以上。然后从课程页面下载algs4.jar和测试数据放进lib/目录。JUnit 用 4.13.2 版本同样放lib/。目录结构按第 2 章那份来src/下每个作业一个包包名与目录名一致否则javac找不到类。# 确认环境 java -version javac -version # 目录准备 mkdir -p lib src build # 把 algs4.jar、junit-4.13.2.jar、hamcrest-core-1.3.jar 放进 lib/ ls lib/hamcrest-core是 JUnit 4 的传递依赖少了它跑测试会报NoClassDefFoundError这是新手最常翻车的地方之一。4.2 用 Ant 一键编译与测试项目根目录有build.xml的话直接两条命令ant compile # 编译 src 下所有源码到 build/ ant test # 编译并运行所有 *Test 类ant compile成功后build/下会出现与包结构对应的.class文件。如果报package edu.princeton.cs.algs4 does not exist说明algs4.jar没在类路径上检查build.xml里classpath的fileset路径是否指向lib。没有 Ant 也能手动编译适合只想跑单题的场景# 编译单个作业包输出到 build javac -cp lib/algs4.jar:lib/junit-4.13.2.jar -d build src/percolation/*.java # 运行交互式测试课程自带测试客户端 java -cp build:lib/algs4.jar edu.princeton.cs.algs4.PercolationVisualizer test/percolation/input10.txtWindows 下类路径分隔符是分号把:换成;即可。-d build让编译产物按包名落到build下对应子目录运行时类路径指向build就能找到。4.3 用课程测试脚本做正确性验证每道题官方都提供了测试客户端比如渗流题的PercolationVisualizer会弹窗画出格子状态PercolationStats直接输出均值、标准差和置信区间。跑之前先确认测试数据路径正确# 渗流统计N200T100 次实验 java -cp build:lib/algs4.jar PercolationStats 200 100 # 期望输出类似 # mean 0.592... # stddev 0.009... # 95% confidence interval [0.590, 0.594]均值落在 0.592 附近说明实现正确偏离太多通常是并查集合并方向或虚拟顶点接错了。队列题用Permutation客户端从标准输入读整数再随机输出可以这样喂数据echo 3 1 2 3 4 5 | java -cp build:lib/algs4.jar Permutation 3第一个数字是每次输出的个数 k后面是待处理序列。多跑几次看输出是否随机且不重复能快速验证RandomizedQueue的均匀性。5. 避坑与排查提交前最容易翻车的五个点5.1 现象本地跑通提交后隐藏用例全挂原因多半是边界条件没处理。渗流题里 N1 时虚拟顶部和底部会合并到同一个格子如果open里先接顶部再接底部逻辑上没问题但percolates的判断依赖两个虚拟顶点确实被 union 过。队列题里对空队列removeFirst必须抛NoSuchElementException抛别的异常或返回 null 都算错。解决方式是照着题目 API 文档逐条对异常类型别凭感觉写。5.2 现象Timing测试超时算法明明是对的原因通常是数据结构选错或没做剪枝。KdTree 的range如果忘了按切分线剪枝复杂度退化成 O(N)几千个点就超时。并查集如果只做路径压缩不做加权合并极端情况下树高仍是 O(log N) 但常数偏大。解决方式是先用小数据验证正确性再用大数据跑计时超时就回头检查递归里有没有该剪的分支。5.3 现象Checkstyle报一堆格式错误原因是对课程代码规范不熟。常见的有类成员顺序不对静态变量、实例变量、构造器、方法、行尾有多余空格、if后面没加大括号、方法超过规定行数。解决方式是本地先跑一遍 checkstyle按报错逐条改别等提交后看反馈。习惯上我会在build.xml里加一个checkstyletarget编译前先过一遍。5.4 现象测试数据读进来全是 null 或数组越界原因是标准输入读取方式不对。课程库的StdIn和Scanner行为不同StdIn.readAllStrings()会把整个输入读成字符串数组适合小数据大数据要用In类按行读。另外测试文件路径是相对当前工作目录的在 IDE 里跑和在命令行跑工作目录不同路径会失效。解决方式是统一用绝对路径或把数据放类路径下用getResourceAsStream读。5.5 现象RandomizedQueue的迭代器抛ConcurrentModificationException原因是迭代过程中修改了队列。题目要求迭代器在队列被修改后行为未定义但很多实现会在next里检查count变化并抛异常。如果你的实现没抛测试可能不报错但语义上不严谨。解决方式是在迭代器里记录创建时的countnext时比对不一致就抛ConcurrentModificationException和java.util的约定保持一致。6. 二次开发把习题代码改成可复用的算法工具库这套代码直接拿来当工具库用有个障碍每个类都绑定了课程库的StdIn/StdOut输入输出和算法逻辑混在一起。改造的第一步是把 I/O 从核心类里剥出去。以Percolation为例构造器只接收 Nopen/isOpen/percolates保持纯逻辑统计和绘图放到独立的客户端类里。这样Percolation就能被其他项目直接new出来用不依赖algs4.jar的 I/O 部分。第二步是给关键类补泛型和接口。Deque和RandomizedQueue已经是泛型但KdTree写死了Point2D如果要做三维或更高维的范围搜索得把维度抽成参数。常见做法是定义一个Point接口暴露dimension()和coordinate(int i)KdTree内部按dimension交替切分这样二维、三维共用一套逻辑。第三步是加基准测试。习题代码只保证正确性不保证性能可观测。我一般会写一个简单的 JMH 或手写计时循环对Percolation的open、KdTree的range、SAP的length分别跑不同规模的数据记录耗时曲线。下面是个手写计时的例子// 简易基准测 KdTree 范围搜索在不同点数下的耗时 public static void benchmarkRange(int n, int queries) { KdTree tree new KdTree(); java.util.Random rnd new java.util.Random(42); for (int i 0; i n; i) { tree.insert(new Point2D(rnd.nextDouble(), rnd.nextDouble())); } long start System.nanoTime(); for (int i 0; i queries; i) { double x rnd.nextDouble(), y rnd.nextDouble(); tree.range(new RectHV(x, y, Math.min(1, x 0.05), Math.min(1, y 0.05))); } long elapsed System.nanoTime() - start; System.out.printf(n%d queries%d avg%.3f ms%n, n, queries, elapsed / 1e6 / queries); }固定随机种子42是为了结果可复现queries控制查询次数avg是单次查询平均耗时。跑几组不同 n 值就能看出范围搜索是否接近 O(log N k)。改造后的验证方法是先用课程测试数据确认正确性没退化再跑基准确认性能符合预期最后把改造后的类打成 jar在其他项目里引用。从那以后我每次改这类算法代码都强制先跑一遍原始测试用例再动性能优化因为优化最容易在边界条件上翻车而边界条件恰恰是测试用例覆盖最全的地方。希望帮到你。本文还有配套的精品资源点击获取