LeetCode 210. Course Schedule II 题解

LeetCode 210. Course Schedule II 题解题目描述现在你总共有numCourses门课需要选记为0到numCourses - 1。给你一个数组prerequisites其中prerequisites[i] [ai, bi]表示在选修课程ai前必须先选修bi。例如想要学习课程 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]解题思路方法拓扑排序Kahn 算法思路构建邻接表和入度数组邻接表adj存储每个课程的后继课程入度数组indegree存储每个课程的入度即需要先修的课程数量使用队列进行拓扑排序首先将所有入度为 0 的课程加入队列然后依次取出队列中的课程将其加入结果列表并将其所有后继课程的入度减 1如果某个后继课程的入度变为 0将其加入队列最后检查是否所有课程都被处理过即结果列表的长度等于课程数量复杂度分析时间复杂度O(V E)其中 V 是课程的数量E 是先修课程对的数量。需要遍历所有课程和先修课程对。空间复杂度O(V E)需要存储邻接表、入度数组和结果列表。代码实现方法拓扑排序Kahn 算法class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) - List[int]: # 构建邻接表和入度数组 adj [[] for _ in range(numCourses)] indegree [0] * numCourses for course, pre in prerequisites: adj[pre].append(course) indegree[course] 1 # 使用队列进行拓扑排序 queue [] for i in range(numCourses): if indegree[i] 0: queue.append(i) result [] while queue: current queue.pop(0) result.append(current) # 处理当前课程的所有后继课程 for neighbor in adj[current]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) # 检查是否所有课程都被处理过 return result if len(result) numCourses else []测试用例测试用例 1输入numCourses 2, prerequisites [[1,0]]输出[0,1]测试用例 2输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]输出[0,2,1,3]测试用例 3输入numCourses 1, prerequisites []输出[0]测试用例 4输入numCourses 2, prerequisites [[1,0],[0,1]]输出[]总结本题是拓扑排序的经典问题是课程表问题的延伸主要考察对拓扑排序算法的理解和应用。通过构建邻接表和入度数组然后使用队列进行拓扑排序我们可以不仅判断是否可以完成所有课程的学习还可以返回具体的课程学习顺序。拓扑排序的核心思想是按照依赖关系的顺序依次处理入度为 0 的节点。如果最终所有节点都被处理说明不存在环返回处理顺序否则说明存在环返回空数组。这种方法不仅适用于课程表 II 问题还可以应用于许多其他需要处理依赖关系并返回处理顺序的场景例如任务调度、编译顺序等。掌握拓扑排序的思想对于解决这类问题非常重要。