复盘 · LC 207 课程表

题目

题号：LeetCode 207
名称：课程表（Course Schedule）
难度：Medium
链接：leetcode.cn/problems/course-schedule
今日代码：207-课程表/index.js

题意

共有 numCourses 门课（编号 0 … numCourses-1），prerequisites[i] = [a, b] 表示学 a 之前必须先学 b。问能否修完所有课（即先修关系是否构成有向无环图）。

可能有环 → 无法完成，返回 false。
无先修时任意顺序均可。
边界：0 条边、自环、多条边指向同一课、只有一条长链。

涉及算法

标签	一句话
拓扑排序（Kahn）	入度为 0 入队，削边减入度，能弹出的点数 = 课数 ⇒ 无环
DFS 判环	三色标记：访问中再次碰到灰点 ⇒ 有环

教程对照：11 · 队列与层序思想（队列 BFS 骨架；拓扑排序是「按依赖层层弹出」的图版层序）。

评价我的解法

你的思路：邻接表 + 入度数组，Kahn 拓扑排序，统计弹出节点数是否等于 numCourses。方向完全正确，是本题标准解之一。

我的代码（摘自 207-课程表/index.js，不含本地测例）：

javascript

var canFinish = function (numCourses, prerequisites) {
  /* 定义邻接表 */
  const table = Array.from({ length: numCourses }, () => []);
  /* 记录每一个节点的入度 */
  const enterNumArr = new Array(numCourses).fill(0);

  for (let i = 0; i < prerequisites.length; i++) {
    const [a, b] = prerequisites[i];
    table[b].push(a);
    enterNumArr[a]++;
  }

  const startNodeArr = [];

  for (let i = 0; i < enterNumArr.length; i++) {
    const count = enterNumArr[i];
    if (count === 0) {
      startNodeArr.push(i);
    }
  }

  let count = 0;

  while (startNodeArr.length > 0) {
    const startNode = startNodeArr.shift();
    count++;
    for (const node of table[startNode]) {
      enterNumArr[node]--;
      if (enterNumArr[node] === 0) {
        startNodeArr.push(node);
      }
    }
  }
  return count === numCourses;
};

对在哪、糙在哪：

边方向对：[a, b] → b → a、a 入度 +1，和题意一致。
Kahn 骨架完整：建图 → 入度 0 入队 → 削边 → count === numCourses，能 AC。
Array.shift() 当队列：每次 O(n)，稠密图上会拖成近似 O(V²)；JS 更稳妥是用下标当队头（queue[head++]），或接受 shift 但面试要能说出这个坑。
本地测例有越界：numCourses = 3 却写了先修 [3, 1]（合法课号只有 0～2）。解法本身没错，但本地自测会踩到 table[b] / 入度越界，说明测例要跟着约束写。
命名略啰嗦（enterNumArr / startNodeArr）：不影响正确性；面试可改成 indegree / queue。

小结：拓扑排序会了，而且边方向没反——这是 207 最常见翻车点。下一步把「无 shift 的队列」和「DFS 三色判环」各默写一遍，当口述备选。

最佳题解

Kahn 拓扑 + 下标队列（避免 shift）：

javascript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    indegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  let learned = 0;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    learned++;
    for (const v of graph[u]) {
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return learned === numCourses;
};

时间 O(V + E)，空间 O(V + E)。
为何更优：语义与你的解相同，但队头用下标推进，避免 shift 的隐性二次代价；变量名更贴近口述。

DFS 三色判环也可作对照：0 未访 / 1 访问中 / 2 已完成；走到 1 即有环。

关联题目

题	为何相关
210. 课程表 II	同一拓扑，额外输出一门合法顺序
269. 火星词典	字符偏序 → 拓扑排序
802. 找到最终的安全状态	反向图 / 拓扑找无环可达点
785. 判断二分图	另一类「图上 BFS/染色」面试题

一句话带走

课程表：先修关系建有向图，Kahn 不断弹出入度 0；能弹出全部课 ⇒ 无环可修完。

复盘 · LC 207 课程表 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​