LC210. 课程表II

题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a(i), b(i)] ，表示在选修课程 a(i) 前 必须 先选修 b(i) 。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1： 输入：numCourses = 2, prerequisites = [[1,0]] 输出：[0,1] 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。 示例 2： 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出：[0,2,1,3] 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 示例 3： 输入：numCourses = 1, prerequisites = [] 输出：[0]

题目解析

题目在说什么

想象一下，你是一个大学新生，要选一些课。有些课是“先修课”，比如你想学“机器学习”，必须先学“高等数学”和“线性代数”。题目给了你一个列表，告诉你每门课的前置要求。比如 [1,0] 表示：想学课程 1，必须先学课程 0。

现在，你要安排一个学习顺序，把所有的课都学完。注意，可能有好几种顺序都行，你只要随便给出一种就行。但如果这些课程之间有“死循环”，比如课程 A 要求先学 B，课程 B 又要求先学 A，那就永远学不完，这时候你要返回一个空数组 []。

思路是怎么来的

这个问题其实很像我们平时做事的“任务安排”。比如你要做一顿饭：先洗菜，再切菜，再炒菜。洗菜没有前置任务，所以可以先做。切菜需要先洗菜，所以切菜要等洗菜完成。炒菜需要先切菜，所以炒菜要等切菜完成。

这种“先做谁，后做谁”的问题，在计算机里有个专门的名字叫“拓扑排序”。你可以把每门课想象成一个“节点”，把先修关系想象成一条“箭头”，从先修课指向后修课。比如 [1,0] 就是 0 → 1（先学 0，再学 1）。

那怎么找出一个可行的顺序呢？一个很自然的想法是：先找那些没有前置要求的课（入度为 0 的课），把它们先学了。学完之后，那些依赖它们的课，前置条件就少了一个。如果某门课的所有前置课都学完了，它就可以开始学了。这样一层一层地学下去，直到所有课都学完。

如果最后还有课没学，说明存在“死循环”（比如 A 依赖 B，B 依赖 A），那就没法学完。

这个思路就是“广度优先搜索（BFS）”的拓扑排序，也叫 Kahn 算法。

代码逐步拆解

我们来看参考代码，一步一步拆解。

1. 准备数据结构

Map<Integer, List<Integer>> adjList = new HashMap<>();
int[] inDegree = new int[numCourses];

• adjList：邻接表。用来存“学完某门课后，可以学哪些课”。比如 adjList.get(0) 就是学完课程 0 后，可以学的课程列表。
• inDegree：入度数组。每门课都有一个“入度”，表示它有多少门先修课还没学。比如 inDegree[2] = 1 表示课程 2 有 1 门先修课没学。

2. 建图

for (int[] prerequisite : prerequisites) {
    int a = prerequisite[0];
    int b = prerequisite[1];
    adjList.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    inDegree[a]++;
}

• 遍历每一条先修关系 [a, b]，意思是：想学 a，必须先学 b。
• 我们在邻接表中，把 a 加到 b 的“后继列表”里，表示学完 b 后可以学 a。
• 同时，a 的入度加 1，表示 a 又多了一门先修课。

3. 找起点

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
    if (inDegree[i] == 0) {
        queue.offer(i);
    }
}

• 入度为 0 的课，就是没有先修课的课，可以最先学。
• 把这些课都放进一个队列里，准备开始学。

4. BFS 过程

List<Integer> ans = new ArrayList<>();
while (!queue.isEmpty()) {
    int cur = queue.poll();
    ans.add(cur);
    if (adjList.containsKey(cur)) {
        for (int nxt : adjList.get(cur)) {
            inDegree[nxt]--;
            if (inDegree[nxt] == 0) {
                queue.offer(nxt);
            }
        }
    }
}

• 从队列里取出一门课 cur，把它加入答案列表（表示我们学了它）。
• 然后看 cur 有哪些“后继课”（即依赖 cur 的课），把这些后继课的入度减 1，表示它们的一门先修课已经学完了。