企业官网建设流程全解析

简介：这是针对普林斯顿大学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*N+1 // 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*n+2，多出的两个位置留给虚拟节点。我在open()里单独判断row==1和row==n，而不是在初始化时就连接整行的格子，因为那样做的话，当某个顶部格子还没打开时你就提前建立了它和虚拟顶的连接，后续所有连通性全乱了。这是典型的"看不见的工程约束"——算法本身不难，难在别让虚拟节点和未打开格子提前连通。

3.2 CollinearPoints：排序法的三个细节与一个必踩的浮点坑

CollinearPoints（又称 Pattern Recognition）要求找出平面上所有由 4 个或更多点组成的直线段。暴力枚举四重循环在点数超过 50 时就会卡死，所以官方允许你使用排序法：以每个点为原点，对其余点按斜率排序；斜率相同的相邻点就在同一条直线上。

排序法的核心坑有三个。第一，比较器必须稳定且自洽：如果两个点与原点共线，它们的斜率相等，此时比较器要返回 0；但如果直接返回 0，Arrays.sort()会认为这两个点相等，从而可能触发TimSort的稳定性逻辑（当数组长度超过 32 时）导致排序结果不符合预期。解决方案是像官方 hint 那样，用自然顺序（y 坐标优先，x 坐标其次）来打破平局。

我给出的比较器骨架如下：

public class SlopeOrder implements Comparator<Point> { 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 8Puzzle：A* 搜索的两个剪枝与一个必踩的缓存坑

这道作业要求用 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 + 1（0 表示空位）。如果你用 0-based 坐标，这个公式要跟着调整，否则隐藏测试全挂。

参数说明：tiles是二维数组，我在构造函数里把hamming和manhattan的计算结果缓存到 final 字段。这里有一个空间权衡：每个Board对象都持有一个二维数组，如果搜索节点多，内存会涨得很快；评分器在内存项会检查你是否在Solver里保存了不必要的Board副本。常见做法是在Solver的搜索节点中只存Board引用，不复制二维数组，除非移动时需要产生一个新棋盘。此外，zeroRow和zeroCol也应该缓存，否则neighbors()每次都要扫描整个数组找空位。

3.4 BoggleSolver：Trie 的剪枝与 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 真正想教会我们的东西。希望这些踩坑记录能让你少走一段我走过的弯路，祝你在提交分数页面看到那个让你满意的百分数。

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