企业官网建设流程全解析

简介：这是Coursera平台上普林斯顿大学《算法》课程编程作业的Java解答合集，面向系统学习算法理论并希望完成配套编程实践的学习者，能帮助读者对照经典题目梳理解题思路、验证实现细节。压缩包共20个文件，以18个Java源文件为主体，另含1个Markdown说明文档和1个License文件，总容量仅28KB；Java文件对应各作业核心实现，Markdown用于说明作业任务与运行方式。解答覆盖渗滤、WordNet、KdTree、双端队列与随机队列、接缝裁剪、共线点、8拼图等题目，从基础数据结构到图与动态规划逐步递进，涉及排序、搜索、图处理、最优化等经典算法主题，也展示了面向对象封装、泛型与集合框架的实际运用。读者可对照代码排查自己提交中的逻辑漏洞，学习如何将复杂问题拆分为可管理模块、设计接口并选择合适的数据结构，从而提升算法分析能力与Java编程水平。目前已有243人学习下载，适合算法课程自学者和需要编程实践参考的开发者。

1. algs4-Programming-Assignment：这份作业合集到底该不该刷

A同学问过我一个很实在的问题：网上流传的 algs4-Programming-Assignment 习题解答，到底值不值得照着敲一遍？我的回答是：值得，但得把它当“评测标准”而不是“答案”。这是某高校那门经典算法公开课配套的编程作业合集，覆盖并查集、排序、图算法、字符串处理等算法课核心知识点。真正让这套作业含金量高的，是它背后的自动评分机制——不只查输出对不对，还查性能、内存、代码风格和 API 合规。直接抄一遍答案，只会得到一份虚假的掌握感；自己实现、反复跑测试、再对照合集里的思路，才是这套作业的正确打开方式。这篇笔记就把这条路从头拆到尾。

2. algs4 作业全貌：10 道题的知识点分布与难度评级

2.1 作业清单与难度：先把对手看清楚

algs4 公开课一共拆成两段，第一段偏基础数据结构，第二段偏进阶算法，前后各五个编程作业。下面这份清单是我自己按“实现阻力”拍的难度，不是课程官方排序，你可以把它当作投入时间的参考。

Part I 的前三个作业其实是在热身，难度不高，但要求你适应“按接口写类”的模式：哪些方法必须是 public，哪些辅助逻辑必须藏起来，这些习惯会直接影响后面所有作业。从 8 Puzzle 开始，评分器会统计你创建的对象数量，算法复杂度对但对象太多照样扣分。Part II 里的 Baseball Elimination 和 Burrows-Wheeler 是最劝退的两道，前者要把比赛排名问题改造成网络流，后者要把循环后缀数组的逆向变换搞清楚，任何一个环节卡住都容易让人想放弃。

2.2 评分机制拆解：别以为输出对了就拿满分

很多合集里的代码在本地能跑出正确答案，交上去分数却很难看，原因是没吃透官方评分器的五个维度。

• 正确性：大量单元测试，除了固定用例还有随机生成用例。随机种子固定，结果可复现，意味着你不能靠运气过关。
• 性能：每个测试有超时限制，复杂度不对、对象创建过多都会让这个维度崩掉。
• 内存：评分器会统计你创建了多少对象，每个作业有配额，超了直接扣分。这是 algs4 作业和普通 OJ 最大的区别，普通在线评测只关心时间和答案，这里连内存足迹都要算。
• 代码风格：走 Checkstyle，缩进、空格、Javadoc、命名、行长度都会被查。风格分占比不大，却是最好拿的，丢了最冤。
• API 合规：作业规定类的公开接口，你多写一个 public 方法，评测器可能直接编译失败，这是硬线。

所以我的习惯是：把习题解答当“对照答案”，不看它的输出，只看它怎么建模，然后自己实现。每道题先自己写一版，卡住了再去翻合集的思路提示，而不是复制代码。后面每一章的代码都是教学节选，不是交作业用的完整答案，用意也在这里。

2.3 刷题顺序与时间预算：不是所有题目都要平均用力

推荐顺序是：Percolation → Deques 和 Randomized Queues → Collinear Points → 8 Puzzle → Kd-Trees → WordNet → Seam Carving → Boggle → Baseball Elimination → Burrows-Wheeler。理由是前五道能帮你建立起“对象数量敏感度”，后面图算法和网络流先易后难，心理压力会小很多。

时间预算按三档来：Part I 前三题是热身，一题 1～2 天；Part I 后两题加 Part II 前三题是核心区，一题 2～3 天；Baseball Elimination 和 Burrows-Wheeler 是硬骨头，给自己 4～5 天，因为建模失败重来的概率很高。总时间大约六到八周，和公开课的节奏基本吻合。如果手头只有两周，我的取舍是：把前五道吃透，Part II 只做 WordNet 和 Seam Carving，另外三道看思路但不深抠。先把一整套评分机制跑熟，比做完十道题但每道都没打磨到满分更有价值。

3. 搭建本地评测环境：从 JDK 到评分脚本的一站式配置

3.1 版本选型：老课程别追太新的 JDK

这套作业是用 Java 写的，官方评测器大概率跑在 JDK 8 或 11 上。我本地装的是 OpenJDK 17，但写代码时只用 Java 8 就有的语法，var、switch 表达式、记录类型这些新特性一概不碰。原因很简单：你在本地用新特性编译通过，评测器用旧编译器一编就挂，这种翻车没有任何技术含量，纯粹是版本自找的。

不要因为教程里写了某个 JDK 版本就去网上找“最新版”，也别迷信新版本能自动优化性能。评分器对旧代码的兼容性远比本地开发体验重要。装好后先确认版本一致：

java -version javac -version

两个命令输出的版本号必须一致，否则编译和运行用的不是同一套工具链。最常见的坑是系统里同时装了多个 JDK，java指向了 17，javac却指向了 8，这类玄学问题我在很多同学的机器上见过。

3.2 环境变量与类路径：可以直接执行的配置片段

我习惯把课程配套的库统一放到~/lib目录下，然后在每个作业目录里用 export 临时设置，不写进全局配置，避免不同作业互相干扰。

export JAVA_HOME=/usr/lib/jvm/java-17-openjdk-amd64 export PATH=$JAVA_HOME/bin:$PATH export ALGS4_LIB="$HOME/lib/algs4.jar" export CLASSPATH=".:$ALGS4_LIB" java -version javac -version

逐行说明一下：JAVA_HOME指向 JDK 安装根目录；PATH把 JDK 的 bin 目录放到最前面，确保命令行用的是它；ALGS4_LIB指向 algs4.jar，这个 jar 里装好了 WeightedQuickUnionUF、StdRandom、StdIn 等课程配套类，作业里可以直接 import；CLASSPATH里最前面的点是当前目录，表示编译时先找当前目录下的源码和字节码。

参数注意：如果你在 Windows 上，类路径分隔符是分号而不是冒号，路径里也别带空格。macOS 上不要硬编码 JAVA_HOME 路径，用/usr/libexec/java_home动态获取，我通常会在~/.zshrc里写一行别名，而不是把路径写死。

3.3 最小命令跑通第一个作业：编译、运行与自测

环境配好后，用第一个作业 Percolation 验证整套链路：

cd ~/workspace/01-percolation javac -encoding UTF-8 Percolation.java PercolationStats.java java PercolationStats 200 100

第一行命令把两个类一起编译，第二行运行蒙特卡洛模拟。PercolationStats的两个参数分别是网格边长 N 和实验次数 T，输出应该是平均值、标准差和 95% 置信区间。如果你看到数值在 0.59 附近抖动，说明基础功能正常，因为渗漏阈值的理论值大约是 0.5927。如果输出是 1.0 或者 0.0，说明并查集的合并逻辑有方向性问题，后面第四章会详细讲。

注意：这个命令只验证正确性的一部分，不能替代官方评分器。边界输入测试，比如 n=1、行列越界、重复 open，必须自己补，评分器一定会覆盖这些用例。

3.4 把评分器和 Checkstyle 接到本地

常见做法是：从课程页面下载测试器 zip 和 Checkstyle 配置，解压到作业根目录，目录结构大致如下。

01-percolation/ Percolation.java PercolationStats.java lib/ algs4.jar checkstyle/ checkstyle.jar algs4.xml tester/

Checkstyle 的调用方式一般是：

java -jar checkstyle/checkstyle.jar -c checkstyle/algs4.xml *.java

这条命令把当前目录下所有 Java 源码按课程规则检查一遍，规则文件不变，本地结果基本等同评测器结果。测试器的情况则因作业而异，入口可能是一个 jar 包也可能是一组 JUnit 类，以课程当季页面给的说明为准，但运行原理都一样：先编译，再跑正确性用例，最后跑性能测试。这里有个很容易踩的坑：类路径忘记加lib/algs4.jar，测试器 一启动就报 ClassNotFoundException，别慌，回到 3.2 的 export 重跑一遍，把依赖加载顺序理清就好。

4. 以 Percolation 为样板：建模、backwash 与可对照的关键代码

4.1 先把题目翻译成数据结构

Percolation 问的是：N×N 个格子，每个格子可能开放或封闭，从最上面一行灌水，水能不能顺着相邻开放格子流到最下面一行。暴力做法是每次查询都重新做一次 DFS，太慢；正确姿势是并查集：把连通的开放格子合并成一个集合，再判断顶和底是否连通。

但直接合并所有开放格子，isFull会出错。原因在于并查集只回答“连通吗”，不回答“这个格子是因为直接和顶部连通才算 full，还是因为从底部回流上来的也算 full”。这就是 backwash 问题。所以在建模前就要决定：percolates 和 isFull 是不是用同一套并查集。在我做过和看过的方案里，最常见的做法是维护两个并查集，一个管 percolates，一个管 full，代价是内存多一份父数组，但逻辑清楚，值得。

4.2 虚拟节点与 backwash：决定 isFull 正确性的两个参数

这道题里有几个参数是必须想清楚的：

• 虚拟顶节点：给并查集多开一个索引 0，把第一行所有 open 的格子 union 到 0，percolates就可以直接回答“虚拟底节点和 0 是否连通”，时间复杂度 O(1)。
• 虚拟底节点：索引 N*N+1，把最后一行所有 open 的格子 union 到它。注意，如果只用这一个并查集判断 full，底部连通的格子上方所有开放格都会被误判为 full，因为路径可以经底部绕回顶部。
• isFull 的判定：要用不含虚拟底节点的那个并查集，只判断“是否和虚拟顶节点连通”。

4.3 关键代码节选：open() 的合并与 isFull() 的两种写法

下面这段是核心骨架，节选自常见正确做法，不能直接提交，但可以对照自己的实现。

public class Percolation { private final boolean[] open; private final int n; private final WeightedQuickUnionUF uf; // 管 percolates，含虚拟底 private final WeightedQuickUnionUF ufFull; // 管 isFull，不含虚拟底 private int openCount; public Percolation(int n) { if (n <= 0) throw new IllegalArgumentException("n must be positive"); this.n = n; open = new boolean[n * n + 2]; uf = new WeightedQuickUnionUF(n * n + 2); ufFull = new WeightedQuickUnionUF(n * n + 2); } private int indexOf(int row, int col) { return (row - 1) * n + col; } public void open(int row, int col) { validate(row, col); if (isOpen(row, col)) return; int id = indexOf(row, col); open[id] = true; openCount++; if (row == 1) { uf.union(id, 0); ufFull.union(id, 0); } if (row == n) { uf.union(id, n * n + 1); } // 只和已经开放的邻居合并 unionNeighbor(row, col, row - 1, col); unionNeighbor(row, col, row + 1, col); unionNeighbor(row, col, row, col - 1); unionNeighbor(row, col, row, col + 1); } public boolean isFull(int row, int col) { validate(row, col); int id = indexOf(row, col); return open[id] && ufFull.find(id) == ufFull.find(0); } }

逻辑说明很关键：open()里先把 open 数组标记为 true，再决定要不要连虚拟节点，最后只和上下左右已经开放的格子合并。顺序不能反，否则isOpen会漏掉当前格子的状态。isFull用的是ufFull，它没有连虚拟底，所以从底部绕上来的格子不会在这里被判为 full，backwash 被绕开了。

参数说明：WeightedQuickUnionUF是官方库提供的并查集，find(id)返回集合根节点；ufFull.find(id) == ufFull.find(0)表示当前格子与虚拟顶属于同一集合。两个并查集都初始化为 N*N+2 长度，多出来的两个位置就是虚拟顶和虚拟底。如果你直接照抄这段去提交，会挂在 validate 和 unionNeighbor 这两个私有方法上——它们必须自己补全，包括行列越界检查。

4.4 用官方测试之外的“土办法”验证正确性

官方评分器要等提交后才出结果，太慢。我一般在本地跑一组不同规模的蒙特卡洛模拟：

for n in 100 200 500; do java PercolationStats $n 100 done

N 从 100 到 500，实验次数固定为 100，观察均值是否稳定在 0.5927 附近。如果输出稳定在 0.59 到 0.60 之间，说明渗漏模型的并查集逻辑基本正确；如果明显偏离，先检查open()里有没有漏掉邻居合并，再看虚拟顶底节点的索引有没有算错。这个办法能提前拦下一大批低级错误，尤其是把行列坐标转索引时从 0 开始还是从 1 开始的问题。

5. algs4 作业避坑指南：五个最容易丢分的细节

5.1 Checkstyle 风格分丢光：因为你没在本地先跑一遍规则

现象：功能全对，评分器上的风格分却是 0。原因：Checkstyle 检查缩进、空格、Javadoc、行宽、空行，本地 IDE 看着正常，评测器一跑就全亮红。我见过的典型问题包括方法之间没有空行、行尾多了空格、缺少类级 Javadoc、命名用了缩写。解决：把课程提供的 checkstyle 配置放到本地，提交前先跑一次，把警告当错误处理。命令在 3.4 里给过，规则文件不变，本地结果基本等同评测器结果。风格分虽然占比不大，但它是所有维度里唯一零成本能拿满的，丢了就是白丢。

5.2 API 违规：多一个 public 方法直接编译失败

现象：本地能编译，传到评测器上报错，说找不到方法或方法签名冲突。原因：作业规定了类必须有哪些 public 方法，同时要求“不允许额外的 public 方法”。为了调试方便加一个 public 辅助类，比如public void printGrid()，评测器一编译就挂。解决：所有辅助函数一律 private；内部辅助类改成 package-private 或普通内部类，不能进公开接口。这是我见过最多的低级翻车，而且一旦发生，整个作业的分数都受影响，不是只扣一点点。

5.3 性能超时：对象数量是隐藏的定时炸弹

现象：小规模用例全过，大规模用例 Time Limit Exceeded。原因：算法复杂度没问题，但对象创建太多。典型场景是每次比较都 new 一个包装类型来存斜率，或者用 ArrayList 存大量临时结构，导致垃圾回收拖慢整体速度。解决：作业要求“限制创建的对象数量”，通用做法是尽量用基本类型、复用数组、避免自动装箱。用内存分析工具统计对象数量，和评分器同口径比较。性能测试的输入规模一般设计成是你复杂度能过的上限，一旦超时，先不要优化算法，先数一数对象创建。

5.4 随机性测试翻车：不要自己造随机

现象：Deques 和 Randomized Queues 的随机性测试偶尔失败，本地还复现不出来。原因：自己用Math.random()凑均匀分布，没有严格遵守“dequeue 时每个元素等概率”的要求。比如实现随机队列时用了链表，删除时没有把随机选择落实到每一步，导致分布偏差。解决：要么用官方库提供的 StdRandom，要么把随机队列实现成可扩容数组，每次 dequeue 时随机选一个索引，把最后一个元素搬过来填坑，保证 O(1) 且等概率。评测器的随机种子是固定的，它测的是统计属性，你本地跑一百次看着没问题，不代表种子一变还能过。

5.5 内存超限：隐藏引用比大数组更危险

现象：正确性和性能都过了，内存分被扣。原因：你以为只开了一个 NN 的数组，但并查集初始化了 NN+2 个节点，又额外存了一份 open 数组，加上保存棋盘状态的字段没有释放，内存配额就超了。解决：提交前数一遍每个对象：数组、并查集父数组、辅助状态数组。凡是可以在局部变量里创建的就不要塞进字段；凡是能通过索引计算得到的就不要额外存一份。官方库的 WeightedQuickUnionUF 内部有一个长度为 N*N+2 的 int 数组，这是必须的，但不要再重复维护一份邻接表或布尔矩阵。内存维度最麻烦的地方在于它不报错，只在分数单上扣你几分，所以提交前多花十分钟数对象，回报很高。

6. 交作业前最后 10 分钟：三个给分数兜底的验证习惯

6.1 一条命令自查 80% 的坑

我每次提交前都会跑一条三连命令，把编译、风格、基础功能串在一起：

javac -encoding UTF-8 -Xlint:all *.java \ && java -jar checkstyle/checkstyle.jar -c checkstyle/algs4.xml *.java \ && java PercolationStats 200 100

第一段打开全部编译警告，任何 unchecked 或 deprecation 都值得看一眼，不要放过；第二段是风格硬门槛，过了才继续；第三段是典型的随机模拟，验证核心功能没有在修改中被破坏。三关都过，剩下的是边界行为，靠 6.2 的表单去对照。

6.2 把成绩单回读成代码动作

拿到评分结果后，第一反应别是看总分，而是看哪个维度掉了，然后按表定位：

这张表是我从好几次“为什么功能对却只有 70 分”的疑问里整理出来的。照着表回读，五分钟内基本能定位丢分点。

6.3 提交前留好第一版：给评测器一次反悔的机会

最后一个习惯是版本管理。我一般每个作业建一个 Git 仓库，第一版能通过基础测试就提交一次，再开分支做优化：

git init git add . git commit -m "v1: first correct version" git checkout -b refactor vi Percolation.java # 做性能或内存优化 git add Percolation.java && git commit -m "v2: optimize memory" git checkout master

master 分支永远保留第一版，refactor 分支放心折腾。如果优化把正确性改挂了，切回 master 重新提交，比在考场里一行行找回改前的代码要省太多时间。这个后悔药我吃过几次甜头，现在已经是习惯动作。

我现在拿到任何一份习题解答，第一件事不是看代码，而是先把整套测试命令跑通，再逐题写自己的版本。解答合集的真正价值是告诉你哪些坑可以不用踩，但动手过的那道坎，只能自己走过去。希望帮到你。

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