LeetCode 207. 课程表

字数 2583 2025-11-02 00:38:44

LeetCode 207. 课程表

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai ，则必须先学习课程 bi。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。

示例 1:
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。

示例 2:
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这形成了一个死循环，是不可能的。

解题过程

这个问题可以被建模为一个有向图。在这个图中：

每个节点代表一门课程。
一条有向边从课程 B 指向课程 A，表示 B 是 A 的先修课程（即 prerequisites[i] = [A, B] 对应边 B -> A）。

那么，问题“是否可能完成所有课程的学习”就等价于另一个图论问题：这个有向图中是否存在环？ 如果存在环（如示例2中的 0 -> 1 -> 0），则说明课程之间存在循环依赖，无法完成所有课程。如果不存在环（即这是一个有向无环图，DAG），则可以完成。

我们可以使用拓扑排序 来判断一个有向图是否有环。拓扑排序是针对有向无环图（DAG）的一种线性排序，使得对于任何有向边 u -> v，在排序中 u 都出现在 v 的前面。这个顺序正好对应了我们的选课顺序。

这里我们采用 Kahn算法（基于BFS的拓扑排序），其核心思想是不断选择入度为0的节点（即没有先修课程的课程）。

步骤详解：

构建图并计算入度：
- 我们需要一个数据结构（如邻接表）来表示图，记录每个节点的所有后继节点（即学完这门课后，可以解锁哪些新课）。
- 同时，我们需要一个数组 inDegree 来记录每个节点的入度（即这门课程有多少门先修课）。
- 具体操作：
  - 初始化一个邻接表 graph，大小为课程数量 numCourses，每个元素是一个空列表。
  - 初始化一个入度数组 inDegree，大小为 numCourses，所有元素初始化为0。
  - 遍历 prerequisites 数组中的每一个先修条件 [ai, bi]：
    - 在邻接表中，将 ai 加入到 graph[bi] 的末尾。这表示修完 bi 后，可以解锁 ai。
    - 将课程 ai 的入度 inDegree[ai] 加1。
初始化队列：
- 初始化一个队列（可以是普通的FIFO队列），用于存放当前所有入度为0的节点。
- 遍历所有课程 i（从0到numCourses-1），如果 inDegree[i] == 0，说明课程 i 没有先修要求，可以直接学习，将其加入队列。
进行BFS（广度优先搜索）：
- 初始化一个计数器 count 为0，用于记录我们已经成功“学完”（从图中移除）的课程数量。
- 当队列不为空时：
  - 从队列中取出一个节点（课程）course。这个节点是当前可以学习的课程。
  - 将计数器 count 加1，表示我们学完了一门课。
  - 遍历这门课程 course 的所有后继课程 nextCourse（即在邻接表 graph[course] 中）：
    - 将每个后继课程 nextCourse 的入度减1。因为这门前置课程 course 已经被“学完”了，相当于移除了它对后继课程的依赖。
    - 检查减1之后，nextCourse 的入度是否变为0。如果变为0，说明 nextCourse 所有的先修课程都已完成，现在它可以被学习了，将其加入队列。
判断结果：
- 当队列为空后，BFS过程结束。
- 此时，检查计数器 count 是否等于总课程数 numCourses。
  - 如果 count == numCourses：说明所有课程都成功被“学完”了，即图中不存在环，返回 true。
  - 如果 count < numCourses：说明有部分课程（数量为 numCourses - count）的入度始终无法变为0。这些课程之间存在循环依赖，导致无法开始学习，即图中存在环，返回 false。

为什么这样能找到环？

因为只有入度为0的节点才能被加入队列并处理。如果图中存在环，那么这个环上的所有节点都会互相依赖，它们的入度永远不可能被减到0（因为环内的节点彼此牵制，没有一个起点）。因此，这些节点永远不会被加入队列。最终，我们处理过的节点数 count 就会小于总节点数。

示例演练（以示例2为例）：
numCourses = 2, prerequisites = [[1,0],[0,1]]

建图与计算入度：
- 对于 [1,0]：graph[0] 增加 1；inDegree[1] 加1（变为1）。
- 对于 [0,1]：graph[1] 增加 0；inDegree[0] 加1（变为1）。
- graph[0] = [1], graph[1] = [0]
- inDegree = [1, 1]
初始化队列： 寻找入度为0的节点。inDegree[0] 和 inDegree[1] 都是1，没有入度为0的节点。队列初始为空。
BFS： 队列为空，直接结束。
判断结果： count 为0，不等于2。返回 false。正确判断出存在环。

这个算法的时间复杂度是 O(V+E)，其中 V 是课程数量（节点数），E 是先修条件数量（边数），非常高效。

LeetCode 207. 课程表题目描述你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai ，则必须先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。示例 1: 输入：numCourses = 2, prerequisites = [ [ 1,0] ] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。示例 2: 输入：numCourses = 2, prerequisites = [ [ 1,0],[ 0,1] ] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这形成了一个死循环，是不可能的。解题过程这个问题可以被建模为一个有向图。在这个图中：每个节点代表一门课程。一条有向边从课程 B 指向课程 A ，表示 B 是 A 的先修课程（即 prerequisites[i] = [A, B] 对应边 B -> A ）。那么，问题“是否可能完成所有课程的学习”就等价于另一个图论问题：这个有向图中是否存在环？如果存在环（如示例2中的 0 -> 1 -> 0 ），则说明课程之间存在循环依赖，无法完成所有课程。如果不存在环（即这是一个有向无环图，DAG ），则可以完成。我们可以使用拓扑排序来判断一个有向图是否有环。拓扑排序是针对有向无环图（DAG）的一种线性排序，使得对于任何有向边 u -> v ，在排序中 u 都出现在 v 的前面。这个顺序正好对应了我们的选课顺序。这里我们采用 Kahn算法（基于BFS的拓扑排序），其核心思想是不断选择入度为0 的节点（即没有先修课程的课程）。步骤详解：构建图并计算入度：我们需要一个数据结构（如邻接表）来表示图，记录每个节点的所有后继节点（即学完这门课后，可以解锁哪些新课）。同时，我们需要一个数组 inDegree 来记录每个节点的入度（即这门课程有多少门先修课）。具体操作：初始化一个邻接表 graph ，大小为课程数量 numCourses ，每个元素是一个空列表。初始化一个入度数组 inDegree ，大小为 numCourses ，所有元素初始化为0。遍历 prerequisites 数组中的每一个先修条件 [ai, bi] ：在邻接表中，将 ai 加入到 graph[bi] 的末尾。这表示修完 bi 后，可以解锁 ai 。将课程 ai 的入度 inDegree[ai] 加1。初始化队列：初始化一个队列（可以是普通的FIFO队列），用于存放当前所有入度为0的节点。遍历所有课程 i （从0到numCourses-1），如果 inDegree[i] == 0 ，说明课程 i 没有先修要求，可以直接学习，将其加入队列。进行BFS（广度优先搜索）：初始化一个计数器 count 为0，用于记录我们已经成功“学完”（从图中移除）的课程数量。当队列不为空时：从队列中取出一个节点（课程） course 。这个节点是当前可以学习的课程。将计数器 count 加1，表示我们学完了一门课。遍历这门课程 course 的所有后继课程 nextCourse （即在邻接表 graph[course] 中）：将每个后继课程 nextCourse 的入度减1。因为这门前置课程 course 已经被“学完”了，相当于移除了它对后继课程的依赖。检查减1之后， nextCourse 的入度是否变为0。如果变为0，说明 nextCourse 所有的先修课程都已完成，现在它可以被学习了，将其加入队列。判断结果：当队列为空后，BFS过程结束。此时，检查计数器 count 是否等于总课程数 numCourses 。如果 count == numCourses ：说明所有课程都成功被“学完”了，即图中不存在环，返回 true 。如果 count < numCourses ：说明有部分课程（数量为 numCourses - count ）的入度始终无法变为0。这些课程之间存在循环依赖，导致无法开始学习，即图中存在环，返回 false 。为什么这样能找到环？因为只有入度为0的节点才能被加入队列并处理。如果图中存在环，那么这个环上的所有节点都会互相依赖，它们的入度永远不可能被减到0（因为环内的节点彼此牵制，没有一个起点）。因此，这些节点永远不会被加入队列。最终，我们处理过的节点数 count 就会小于总节点数。示例演练（以示例2为例）： numCourses = 2 , prerequisites = [[1,0],[0,1]] 建图与计算入度：对于 [1,0] ： graph[0] 增加 1 ； inDegree[1] 加1（变为1）。对于 [0,1] ： graph[1] 增加 0 ； inDegree[0] 加1（变为1）。 graph[0] = [1] , graph[1] = [0] inDegree = [1, 1] 初始化队列：寻找入度为0的节点。 inDegree[0] 和 inDegree[1] 都是1，没有入度为0的节点。队列初始为空。 BFS：队列为空，直接结束。判断结果： count 为0，不等于2。返回 false 。正确判断出存在环。这个算法的时间复杂度是 O(V+E)，其中 V 是课程数量（节点数），E 是先修条件数量（边数），非常高效。