HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 210. 课程表 II

学习
46
0
0
2022-04-13
LeetCode 210. 课程表 II

LeetCode 210. 课程表 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]

提示：

  • 1 <= numCourses <= 2000

  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)

  • prerequisites[i].length == 2

  • 0 <= ai, bi < numCourses

  • ai != bi

  • 所有 [ai, bi] 互不相同

思路

方法一：拓扑排序_BFS

本题与LeetCode 207. 课程表类似，只不过本题需要返回你为了学完所有课程所安排的学习顺序。

代码实现（Java）

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 通过题目信息创建有向图，使用邻接表存储
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // 计算图中每个节点的入度，inDegree[i] = j 表示节点 i 的入度为 j
        int[] inDegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            // 修完课程 from 才能修课程 to，即在图中节点 from 指向节点 to
            int to = edge[0];
            inDegree[to]++;
        }
        // 将入度为 0 的节点加入到队列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 记录拓扑排序的结果(即课程安排的学习顺序)
        int[] res = new int[numCourses];
        // 记录遍历节点的顺序
        int cnt = 0;
        // 通过 BFS 算法完成拓扑排序
        while (!queue.isEmpty()) {
            // 取出队首节点
            int cur = queue.poll();
            // 取出的节点顺序即为拓扑排序的结果
            res[cnt++] = cur;
            // 遍历当前节点所指向的所有节点
            for (int next : graph[cur]) {
                // 去掉 cur 指向 next 的边，故 next 的入度减 1
                inDegree[next]--;
                // 将入度为 0 的节点再次加入到队列中
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return cnt == numCourses ? res : new int[]{};
    }

    /*
        利用题目所给信息构建有向图，通过邻接表存储
        其中 numCourses 表示节点个数，prerequisites 存储节点之间的关系 
    */
    public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // 图中共有 numCourses 个节点
        List<Integer>[] graph = new ArrayList[numCourses];
        // 创建 numCourses 个节点
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        // 创建节点之间的关系(即有向边)
        for (int[] edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            // 修完课程 from 才能修课程 to，即在图中添加一条从 from 指向 to 的有向边
            graph[from].add(to);
        }
        return graph;
    }
}

总结

本题的解法涉及了图的拓扑排序，使用队列和邻接表来实现。希望这个解题思路对你有所帮助。

#LeetCode 9