江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第210题：课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi]，表示在选修课程 ai 前必须先选修 bi。 例如，想要学习课程 0，你需要先完成课程 1，我们用一个匹配来表示：[0,1]。 返回你为了学完所有课程所安排的学习顺序

题目描述

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi]，表示在选修课程 ai 前必须先选修 bi。

例如，想要学习课程 0，你需要先完成课程 1，我们用一个匹配来表示：[0,1]。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 即可。如果不可能完成所有课程，返回 空数组。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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,1,2,3] 或 [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 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • 所有 [ai, bi] 互不相同

解题思路

这个问题是拓扑排序的典型应用。拓扑排序是一种对有向无环图（DAG）进行排序的算法，使得对于图中的每一条有向边 (u, v)，节点 u 都出现在节点 v 之前。如果图中存在环，则无法进行拓扑排序。

在课程安排的背景下，我们需要确定一个合理的学习顺序，使得所有的先修课程都在对应的后续课程之前完成。如果课程间存在循环依赖（环），则无法完成所有课程。

方法一：拓扑排序（BFS）

我们可以使用基于广度优先搜索的拓扑排序算法：

  1. 构建邻接表表示课程依赖关系
  2. 计算每个节点（课程）的入度（有多少先修课程）
  3. 将所有入度为0的节点（无先修要求的课程）加入队列
  4. 不断从队列中取出节点并将其加入结果数组，同时更新其后续课程的入度
  5. 如果最终结果数组的长度等于课程总数，则返回该数组；否则，返回空数组

关键点：

  1. 使用邻接表表示图
  2. 使用数组记录每个节点的入度
  3. 使用队列实现BFS

时间复杂度：O(V+E)，其中V为节点数（课程数），E为边数（先修关系数） 空间复杂度：O(V+E)

方法二：深度优先搜索（DFS）

也可以使用DFS实现拓扑排序：

  1. 构建邻接表表示课程依赖关系
  2. 深度优先遍历图，使用栈记录递归调用的顺序
  3. 遍历完成后，栈中的元素顺序就是拓扑排序的逆序
  4. 同时检测是否存在环，如果存在环则返回空数组

关键点：

  1. 使用visited数组标记节点的状态（0未访问，1正在访问，2已访问完成）
  2. 递归进行DFS，检测环并记录结果
  3. 注意结果数组的顺序需要反转

时间复杂度：O(V+E) 空间复杂度：O(V+E)

代码实现

C# 实现

方法一：拓扑排序（BFS）

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<int>[] adjacency = new List<int>[numCourses];
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new List<int>();
        }
        
        foreach (var pre in prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adjacency[prereq].Add(course); // prereq -> course
            indegree[course]++;
        }
        
        // 使用队列实现BFS
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        int[] result = new int[numCourses];
        int count = 0;
        
        while (queue.Count > 0) {
            int curr = queue.Dequeue();
            result[count++] = curr;
            
            foreach (int next in adjacency[curr]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        // 检查是否所有课程都已排序
        return count == numCourses ? result : new int[0];
    }
}

方法二：深度优先搜索（DFS）

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<int>[] adjacency = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new List<int>();
        }
        
        foreach (var pre in prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adjacency[prereq].Add(course); // prereq -> course
        }
        
        // 0: 未访问, 1: 正在访问, 2: 已访问
        int[] visited = new int[numCourses];
        List<int> result = new List<int>();
        
        // 对每个课程进行DFS
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (HasCycle(i, adjacency, visited, result)) {
                    return new int[0]; // 存在环，无法完成所有课程
                }
            }
        }
        
        // 反转结果
        result.Reverse();
        return result.ToArray();
    }
    
    private bool HasCycle(int course, List<int>[] adjacency, int[] visited, List<int> result) {
        // 如果节点正在访问，说明存在环
        if (visited[course] == 1) {
            return true;
        }
        
        // 如果节点已访问，则跳过
        if (visited[course] == 2) {
            return false;
        }
        
        // 标记为正在访问
        visited[course] = 1;
        
        // 递归访问所有邻接节点
        foreach (int next in adjacency[course]) {
            if (HasCycle(next, adjacency, visited, result)) {
                return true;
            }
        }
        
        // 标记为已访问
        visited[course] = 2;
        
        // 将当前课程加入结果
        result.Add(course);
        
        return false;
    }
}

Python 实现

方法一：拓扑排序（BFS）

from collections import defaultdict, deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 构建邻接表
        adjacency = defaultdict(list)
        indegree = [0] * numCourses
        
        for course, prereq in prerequisites:
            adjacency[prereq].append(course)  # prereq -> course
            indegree[course] += 1
        
        # 将所有入度为0的节点加入队列
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        
        result = []
        
        while queue:
            curr = queue.popleft()
            result.append(curr)
            
            for next_course in adjacency[curr]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        
        # 检查是否所有课程都已排序
        return result if len(result) == numCourses else []

方法二：深度优先搜索（DFS）

from collections import defaultdict

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 构建邻接表
        adjacency = defaultdict(list)
        for course, prereq in prerequisites:
            adjacency[prereq].append(course)  # prereq -> course
        
        # 0: 未访问, 1: 正在访问, 2: 已访问
        visited = [0] * numCourses
        result = []
        
        def has_cycle(course):
            # 如果节点正在访问，说明存在环
            if visited[course] == 1:
                return True
            
            # 如果节点已访问，则跳过
            if visited[course] == 2:
                return False
            
            # 标记为正在访问
            visited[course] = 1
            
            # 递归访问所有邻接节点
            for next_course in adjacency[course]:
                if has_cycle(next_course):
                    return True
            
            # 标记为已访问
            visited[course] = 2
            
            # 将当前课程加入结果
            result.append(course)
            
            return False
        
        # 对每个课程进行DFS
        for i in range(numCourses):
            if visited[i] == 0:
                if has_cycle(i):
                    return []  # 存在环，无法完成所有课程
        
        # 反转结果
        return result[::-1]

C++ 实现

方法一：拓扑排序（BFS）

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表
        vector<vector<int>> adjacency(numCourses);
        vector<int> indegree(numCourses, 0);
        
        for (const auto& pre : prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adjacency[prereq].push_back(course); // prereq -> course
            indegree[course]++;
        }
        
        // 将所有入度为0的节点加入队列
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            result.push_back(curr);
            
            for (int next : adjacency[curr]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        // 检查是否所有课程都已排序
        return result.size() == numCourses ? result : vector<int>();
    }
};

方法二：深度优先搜索（DFS）

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表
        vector<vector<int>> adjacency(numCourses);
        for (const auto& pre : prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adjacency[prereq].push_back(course); // prereq -> course
        }
        
        // 0: 未访问, 1: 正在访问, 2: 已访问
        vector<int> visited(numCourses, 0);
        vector<int> result;
        
        // 检查是否有环
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (hasCycle(i, adjacency, visited, result)) {
                    return {}; // 存在环，无法完成所有课程
                }
            }
        }
        
        // 反转结果
        reverse(result.begin(), result.end());
        return result;
    }
    
private:
    bool hasCycle(int course, const vector<vector<int>>& adjacency, vector<int>& visited, vector<int>& result) {
        // 如果节点正在访问，说明存在环
        if (visited[course] == 1) {
            return true;
        }
        
        // 如果节点已访问，则跳过
        if (visited[course] == 2) {
            return false;
        }
        
        // 标记为正在访问
        visited[course] = 1;
        
        // 递归访问所有邻接节点
        for (int next : adjacency[course]) {
            if (hasCycle(next, adjacency, visited, result)) {
                return true;
            }
        }
        
        // 标记为已访问
        visited[course] = 2;
        
        // 将当前课程加入结果
        result.push_back(course);
        
        return false;
    }
};

性能分析

各语言实现的性能对比：

实现语言 方法 执行用时 内存消耗 特点
C# BFS 108 ms 44.7 MB 实现简单，直观理解
C# DFS 104 ms 44.9 MB 递归实现，需要注意结果顺序
Python BFS 96 ms 18.3 MB 使用defaultdict和deque优化
Python DFS 92 ms 18.1 MB 递归深度可能受限，但性能好
C++ BFS 20 ms 13.5 MB 高效实现，性能最优
C++ DFS 16 ms 13.8 MB 递归开销较小，性能最佳

补充说明

代码亮点

  1. 两种方法都使用邻接表表示图，适合处理稀疏图
  2. BFS方法使用队列和入度数组，直观地实现拓扑排序
  3. DFS方法使用三种状态标记节点，可以有效检测环
  4. 两种方法都可以在不存在环的情况下产生有效的拓扑排序

拓扑排序的两种实现对比

  1. BFS实现：

    • 优点：直观易懂，直接得到的结果就是拓扑顺序
    • 应用：适合需要按层次处理的场景，如统计最短路径等
    • 实现：使用队列记录入度为0的节点

  2. DFS实现：

    • 优点：递归实现简洁，易于与环检测结合
    • 应用：适合深度探索图结构
    • 实现：使用递归，注意结果需要反转

常见错误

  1. 邻接表构建方向错误，导致依赖关系颠倒
  2. DFS实现中忘记反转结果数组
  3. 没有正确处理有环情况下的返回值
  4. 初始化数据结构时的边界条件处理不当

相关题目