普林斯顿算法编程作业通关指南：API契约、复杂度与边界用例

简介：这份资源是普林斯顿大学算法课程（Coursera）编程作业的Java解答合集，面向正在学习算法、需要对照参考实现的自学者与在校学生，帮助解决作业卡壳、理解经典算法落地细节的问题。压缩包共20个文件，以18个Java源码为主体，覆盖排序、图算法、动态规划等算法基础，以及并查集、KD树、WordNet、Seam Carving、8-Puzzle等课程典型作业模块，另附1个README说明与1份LICENSE授权文件，整体约28KB，体量轻便、便于按模块查阅。已有243人学习下载，可作为自测与查漏补缺的参照。读者能从中获得各次作业的完整实现思路、数据结构选型与复杂度分析参考，并借助README快速定位目录结构，适合在独立完成作业后对照复盘，逐步夯实算法设计与Java编码能力。

1. 从一道“看起来会、写起来挂”的题说起

普林斯顿算法课的编程作业，很多人第一次交上去就翻车：本地跑通、样例全过，提交后评分脚本一跑，内存超了、时间爆了、边界用例挂了。这场考核考的不是你背没背过快排，而是能不能把算法真正落到 Java 代码里，扛住评分器的压力测试。它适合已经学过数据结构、想用一份可对照的解答把“会写”变成“写对”的人。拿分的关键不在读懂题面，而在三件事：API 契约不能改、复杂度必须达标、边界输入不能崩。这份习题解答的价值，就是把这些隐性要求摊开给你看——每一题的正确写法长什么样、评分器到底在卡什么、哪些地方是血泪经验堆出来的坑。下面按考点分布、高频题型、易错点、答题套路一路讲透，你可以直接拿去对照练。

2. 考点分布：评分器到底在卡哪几类指标

2.1 正确性只是入场券，复杂度和内存才是分水岭

很多人以为编程作业是“对就行”，实际评分器分几档：正确性、运行时间、内存占用、代码规范。正确性不过直接零分，但正确性过了之后，真正拉开差距的是后三项。以排序类作业为例，题面往往要求某个操作在常数或对数时间内完成，如果你图省事每次遍历一遍，样例能过，压力测试直接超时。这类考核的典型套路是：给你一个看似宽松的 API，实际每个方法都有隐含的复杂度上限，评分器用大规模随机输入去撞你的实现。

答题时先做一件事：把题面里每个 public 方法的复杂度要求单独抄出来，标在方法签名旁边。比如“插入应为对数级”“查询应为常数级”，写代码前先想清楚用哪种数据结构能同时满足所有方法，而不是写完再优化。面试官最想听的是你先说清每个操作的复杂度预算，再谈实现选型，这个顺序反了，后面全是返工。

2.2 API 契约：签名、异常、返回值一个都不能自作主张

评分器是拿固定接口去调你的类的，方法名、参数类型、返回类型、抛不抛异常，全部写死。常见翻车是：觉得某个参数没用就删了，或者把返回值从Iterable改成List，本地编译过，提交后评分器直接找不到方法。还有一类是空输入、单元素输入时返回值不符合约定，比如该返回空迭代器却返回了null。

这类题的答法是：动手前先把题面给的 API 骨架原样抄进文件，一个字符都不改，然后只填方法体。遇到“这个方法什么时候返回 null、什么时候抛异常”的模糊地带，按题面示例反推，示例没覆盖的，按“空输入返回空结构、非法参数抛IllegalArgumentException”这条通用约定处理。面试里被问到接口设计，先复述契约再谈实现，是稳拿分的起手式。

2.3 内存与对象创建：看不见的评分项

有些作业会限制内存，或者间接通过运行时间卡你——大量创建临时对象会拖慢 GC。典型场景是循环里反复new数组或包装类，逻辑没错，但规模一大就慢。还有用递归实现本该迭代的算法，栈深度爆掉。

答题思路是先判断哪些对象可以复用、哪些循环可以合并。比如归并排序的辅助数组应该在构造时分配一次，而不是每次归并都新建。面试官问“你这个实现有什么性能隐患”，能主动指出临时对象和递归深度，比背复杂度公式更能体现你真跑过。

3. 高频题型：五类必练的编程作业与答题模板

3.1 排序与查找类：复杂度预算先于代码

这类题的高频要求是“某个操作均摊常数或对数”。典型考法是实现一个支持插入、删除、查找的结构，题面不直说用哪种结构，但复杂度要求已经把答案框死了。答题模板分三步：第一步列出每个操作的复杂度上限；第二步选能同时满足的数据结构，常见是平衡树或哈希加辅助结构；第三步写完后逐个方法核对预算，超了就换结构而不是硬优化。

// 以“支持对数级插入与查找”为例，核心是保持结构有序 public class SortedCollection<Key extends Comparable<Key>> { private Key[] keys; // 有序数组，插入时保持有序 private int n; public void insert(Key key) { int i = rank(key); // 二分定位，O(log n) // 后移腾位，最坏 O(n)，若题面要求严格对数需换平衡树 for (int j = n; j > i; j--) keys[j] = keys[j - 1]; keys[i] = key; n++; } private int rank(Key key) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int cmp = key.compareTo(keys[mid]); if (cmp < 0) hi = mid - 1; else if (cmp > 0) lo = mid + 1; else return mid; } return lo; } }

这段代码的关键注释点明了取舍：二分查找是对数级，但数组插入是线性级。如果题面只要求查找快、插入不设限，这样写够用；如果插入也要求对数级，就必须换成平衡树。参数上Key必须实现Comparable，这是排序类作业的通用前提。答题时把这段取舍讲出来，比闷头写完更有说服力。

3.2 图与路径类：先想清楚状态怎么表示

图论作业的高频考法是“给定图，求某条路径或连通性”，难点不在算法本身，而在输入规模大、需要高效的数据表示。常见翻车是用邻接矩阵存稀疏图，内存直接爆。答题模板：先判断图是稠密还是稀疏，稀疏用邻接表，稠密才考虑矩阵；再确认是否需要多次查询，需要就预处理，不需要就别过度设计。

// 稀疏图用邻接表，避免矩阵的内存浪费 public class Graph { private final int V; private final List<List<Integer>> adj; public Graph(int V) { this.V = V; adj = new ArrayList<>(V); for (int i = 0; i < V; i++) adj.add(new ArrayList<>()); } public void addEdge(int v, int w) { adj.get(v).add(w); // 无向图需反向再加一次 adj.get(w).add(v); } public Iterable<Integer> adj(int v) { return adj.get(v); } }

V是顶点数，adj每个元素是该顶点的邻居列表。无向图要双向添加，有向图只加一次，这个细节题面通常会说，但很多人漏看。面试里被问“为什么不用矩阵”，答“稀疏图边数远小于顶点数平方，矩阵浪费空间且遍历慢”，一句话点到即可。

3.3 字符串处理类：边界和编码别想当然

字符串题的高频坑是空串、单字符、全相同字符、含特殊字符。评分器专门拿这些撞你。答题模板：先把所有边界情况列成清单，写完逐个跑；涉及排序或查找的，确认比较规则是字典序还是自定义，题面没说的按字典序。还有一类是要求原地处理或流式处理，别一上来就split建一堆中间字符串。

// 处理字符串时先挡掉边界，再走主逻辑 public static int countOccurrences(String text, String pattern) { if (text == null || pattern == null || pattern.isEmpty()) return 0; int count = 0, from = 0; while ((from = text.indexOf(pattern, from)) != -1) { count++; from += pattern.length(); // 不重叠计数；若允许重叠改为 from + 1 } return count; }

from += pattern.length()决定是否允许重叠匹配，这是题面常考但常被忽略的语义差异。空模式直接返回 0，避免死循环。这类题答题时主动说明“我按不重叠处理，如果题面要求重叠我改这一行”，面试官会觉得你读题细。

3.4 递归与分治类：栈深度和重复计算是两大雷

分治题看着优雅，实际两个坑：递归太深栈溢出，子问题重复计算导致指数级。答题模板：先估递归深度，超过几千层就考虑改迭代或显式栈；再检查有没有重叠子问题，有就加记忆化。面试里被问“这个递归有什么问题”，先答深度再答重复计算，顺序别乱。

3.5 数据结构设计类：所有操作一起看，别单点优化

这类题给一组操作，要求整体高效。翻车点是只优化了最显眼的那个操作，其他操作退化到线性。答题模板：把所有操作的复杂度要求列成表，找一个能同时满足的结构，找不到就组合两个结构并说明各自负责什么。答题时把这张表画出来讲，比空谈“我用哈希表”清楚得多。

4. 易错点：四类最常丢分的题与纠正答法

4.1 改了 API 签名还以为没事

错在哪：觉得参数多余就删、返回值类型顺手改。为什么错：评分器按固定签名反射调用，签名一变直接找不到方法，正确性零分。怎么答对：动手前原样抄骨架，只填方法体；确实需要辅助方法就加private，绝不动public签名。

4.2 样例过了就提交，边界用例没跑

错在哪：只跑题面给的示例。为什么错：示例通常是最常规输入，评分器的压力测试专挑空、单元素、全重复、极大规模。怎么答对：每道题固定手写四类用例——空、单元素、重复元素、最大规模，跑完再提交。这个习惯能挡掉大半翻车。

4.3 复杂度算错，把均摊当最坏

错在哪：把均摊对数说成最坏对数，或者忽略某次操作的线性开销。为什么错：评分器可能专门构造最坏序列。怎么答对：每个方法分别标最坏和均摊，题面要求哪个就按哪个验；拿不准就按最坏算，宁可保守。

4.4 内存没算，循环里建对象

错在哪：循环内反复new数组或包装类。为什么错：规模一大 GC 拖慢，甚至超内存限制。怎么答对：把可复用的缓冲提到循环外或构造时分配；包装类能换基本类型就换。面试里主动提这一点，是加分项。

5. 答题套路：一套能直接套用的四步法

拿到任何一道编程作业，我固定走四步，顺序不乱。第一步读契约：把题面给的 API 骨架原样抄下来，每个 public 方法的签名、返回值、异常约定单独标出来，这一步决定你会不会白写。第二步列预算：每个方法旁边写复杂度上限和内存约束，写不出预算说明题没读透，回去重读。第三步选结构：拿预算去反推数据结构，一个结构满足不了就组合，并在注释里写清各自负责什么。第四步跑边界：空、单元素、重复、最大规模四类用例固定跑一遍，跑完再提交。

这套流程看着笨，但它把“翻车”从随机事件变成了可检查的清单。我早期也是样例一过就交，连续几次挂在边界和内存上，后来强制自己每道题都走完这四步，提交前再对着预算表核一遍，才把返工率压下来。你要是也在准备这类考核，建议先把这份解答里的每道题按四步法重写一遍，再对照它的写法找差距，比单纯看答案有用得多。希望帮到你。

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