企业官网建设流程全解析

简介：普林斯顿大学《算法》课程编程作业的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 II：WordNet 用有向图做最短的祖先路径，本质是 DAG 上 BFS；Seam 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 放 jar，src 放作业代码，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 Deque<Item> implements Iterable<Item> { 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 Iterator<Item> iterator() { return new Iterator<Item>() { 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 节所示，单独维护一个只连接虚拟顶节点的并查集ufTop，isFull 只用这个并查集判断。从那以后我对所有“是否与某端连通”的判断题，都会刻意追问一句：这个连通性判断会不会受另一端节点的影响。

现象二：Deque 的迭代器在部分样例上抛ConcurrentModificationException，但本机测试没复现。本机遍历时没有混入结构性修改操作，提交后评测系统模拟了“迭代过程中 addFirst”的场景，直接返回运行时异常。

原因：迭代器没有记录modCount，或者记录了但hasNext()没有做并发修改检查。课程要求迭代器在检测到结构修改时必须快速失败，这是 Java 集合框架的标准约定。解决：在每个 add/remove 方法里递增modCount，在迭代器的next()和hasNext()中比较expectedModCount与modCount，不一致就抛异常。这个坑在 RandomizedQueue 中同样存在，而且由于随机队列内部用数组实现，迭代器更容易遗漏写检查。

5.2 性能与内存：超时与超限的排查顺序

现象三：Percolation 的蒙特卡洛模拟在 n=200 时运行 5 秒以上，提交直接超时。本机跑小规模样例（n=20）很快，但当采样次数达到 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 清零、小规模正确性验证、大规模性能压测”这三步，这套习惯帮我躲过了绝大多数评测系统的红叉。希望帮到你。

本文还有配套的精品资源，点击获取