华为 OD 训练营 · 题解精讲
LC207. 课程表
LC207. 课程表
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则 必须 先学习课程 b(i)。 例如，先修课程对 [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 。这是不可能的。
题目解析
解题思路
本题是经典的拓扑排序问题，将课程依赖关系建模为有向图：每门课程是一个节点，先修关系 [a, b] 表示从 b 指向 a 的边。若图中存在环，则无法完成所有课程。使用 BFS 拓扑排序（Kahn 算法）检测环。
核心数据结构：
- 邻接表
h：存储每个节点的后继节点列表 - 入度数组
inDegreeList：记录每门课程的先修课程数量
算法流程：将所有入度为 0 的节点（无先修要求的课程）入队，依次弹出并减少其后继节点的入度，若后继节点入度变为 0 则入队。最终若所有节点入度均为 0，说明无环。
关键步骤
1. 建图：遍历 prerequisites，对每个 [a, b]：
- 在
h[b]中添加a（b → a） inDegreeList[a]加 1
2. 初始化队列：将所有入度为 0 的课程入队：
初始入度: [0, 2, 1, 0] → 队列: [0, 3]3. BFS 拓扑排序：
- 弹出
cur，遍历其后继nxt inDegreeList[nxt] -= 1- 若
inDegreeList[nxt] == 0，入队
4. 结果判定：检查 inDegreeList 是否全为 0
复杂度分析
- 时间复杂度：O(V + E)，V = numCourses，E = len(prerequisites)。建图 O(E)，BFS 遍历每个节点和边各一次。
- 空间复杂度：O(V + E)，邻接表存储所有边，入度数组 O(V)，队列 O(V)。
参考代码
# 题目：LC207. 课程表
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS/拓扑排序
# 代码看不懂的地方，请直接在群上提问
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 将所给的数据用邻接表的形式存储
# 列表/哈希表均可
h = collections.defaultdict(list)
# 构建入度列表，长度为课程数量numCourses
inDegreeList = [0] * numCourses
# 构建邻接表
for a, b in prerequisites:
# 邻接表延长
h[b].append(a)
# a的入度+1
inDegreeList[a] += 1
# 构建队列，用于维护BFS搜索，其中列表长度为0
q = collections.deque( [i for i in range(numCourses) if inDegreeList[i] == 0] )
# 进行BFS搜索
while len(q) > 0:
# 弹出队头元素，当前在学习的课程
cur = q.popleft()
# 遍历cur的所有下一门课
for nxt in h[cur]:
# nxt的入度-1
inDegreeList[nxt] -= 1
# 如果nxt入度为0，则加入队列，进一步地做BFS搜索
if inDegreeList[nxt] == 0:
q.append(nxt)
# 判断入度列表是否均为0，均为0返回True，否则返回False
for i in inDegreeList:
if i != 0:
return False
return True