LeetCode 210、课程表II

一、题目描述

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

例如，想要学习课程 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]

二、题目解析

三、参考代码

1、Java 代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 将所给的数据用邻接表的形式存储
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        // 构建入度数组，长度为课程数量numCourses
        int[] inDegree = new int[numCourses];
        // 构建邻接表
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0];
            int b = prerequisite[1];
            // 邻接表延长
            adjList.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            // a的入度+1
            inDegree[a]++;
        }

        // 构建队列，用于维护BFS搜索
        Queue<Integer> queue = new LinkedList<>();
        // 将入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 构建答案数组
        List<Integer> ans = new ArrayList<>();
        // 进行BFS搜索
        while (!queue.isEmpty()) {
            // 弹出队头元素，当前在学习的课程
            int cur = queue.poll();
            ans.add(cur);
            // 遍历当前课程cur的所有后续课程
            if (adjList.containsKey(cur)) {
                for (int nxt : adjList.get(cur)) {
                    // nxt的入度-1
                    inDegree[nxt]--;
                    // 如果nxt的入度为0，则加入队列，进一步做BFS搜索
                    if (inDegree[nxt] == 0) {
                        queue.offer(nxt);
                    }
                }
            }
        }

        // 判断入度数组是否均为0，若均为0返回true，否则返回false
        for (int degree : inDegree) {
            if (degree != 0) {
                return new int[0];
            }
        }

        // 将List<Integer>转换为int[]
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        return result;
    }
}

2、 C++ 代码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 将所给的数据用邻接表的形式存储
        unordered_map<int, vector<int>> adjList;
        // 构建入度数组，长度为课程数量numCourses
        vector<int> inDegree(numCourses, 0);
        // 构建邻接表
        for (auto& prerequisite : prerequisites) {
            int a = prerequisite[0];
            int b = prerequisite[1];
            // 邻接表延长
            adjList[b].push_back(a);
            // a的入度+1
            inDegree[a]++;
        }

        // 构建队列，用于维护BFS搜索
        queue<int> q;
        // 将入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        // 构建答案数组
        vector<int> ans;
        // 进行BFS搜索
        while (!q.empty()) {
            // 弹出队头元素，当前在学习的课程
            int cur = q.front();
            q.pop();
            ans.push_back(cur);
            // 遍历当前课程cur的所有后续课程
            if (adjList.count(cur) > 0) {
                for (int nxt : adjList[cur]) {
                    // nxt的入度-1
                    inDegree[nxt]--;
                    // 如果nxt的入度为0，则加入队列，进一步做BFS搜索
                    if (inDegree[nxt] == 0) {
                        q.push(nxt);
                    }
                }
            }
        }

        // 判断入度数组是否均为0，若均为0返回true，否则返回false
        for (int degree : inDegree) {
            if (degree != 0) {
                return vector<int>();
            }
        }
        return ans;
    }
};

3、Python 代码

# 题目：LC210. 课程表II
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS/拓扑排序
# 代码看不懂的地方，请直接在群上提问


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 将所给的数据用邻接表的形式存储
        # 列表/哈希表均可
        h = 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] )
        # 构建答案列表
        ans = [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)
                    ans.append(nxt)
        
        # 判断入度列表是否均为0，均为0返回True，否则返回False
        for i in inDegreeList:
            if i != 0:
                return []
        return ans