【LeetCode】课程表 Java 题解

作者：Albert

2022 年 8 月 18 日
北京
本文字数：1757 字
阅读完需：约 6 分钟

题目描述

现在你总共有 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]
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/course-schedule-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是课程表题目，根据题目描述，课程学习有依赖关系。解决这类题目，我们先构建一个图，初始化顶点和边的关系。题目求"返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。", 分析这里，说明题目图可能有环。当有环的时候，会有循坏依赖，无解,返回空数组。
我们如何判断这个图是否有环？我们一般使用拓扑排序方式的判断。任何有向无环图至少有一个拓扑排序，如果不存在拓扑排序，则说明有环。在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 u 到 v 的有向边(u, v) , 都可以有 u 在 v 的前面。
常见的拓扑排序实现有 Kahn 算法和 DFS 算法。在 Kahn 算法中，我们核心是维护一个入度为 0 的集合。初始状态下，集合 S 装着所有入度为 0 的点，是一个空列表。每次从 S 中取出一个点（可以随便取）放入 L , 然后将 u 的所有边 (u, v1), (u, v2) 等删除。对于边 (u, v)，若将该边删除后点 v 的入度变为 0, 则将 v 放入 S 中。不断重复以上过程，直到集合 S 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 L ，L 中顶点的顺序就是拓扑排序的结果。
具体实现代码如下，供参考。

通过代码

class Solution {    public int[] findOrder(int numCourses, int[][] prerequisites) {        if (numCourses <= 0) {            return new int[0];        }        HashSet<Integer>[] graph = new HashSet[numCourses];        for (int i = 0; i < numCourses; i++) {            graph[i] = new HashSet<>();        }        int[] inDegree = new int[numCourses];        for (int[] p : prerequisites) {            graph[p[1]].add(p[0]);            inDegree[p[0]]++;        }
        Queue<Integer> queue = new LinkedList<>();        for (int i = 0; i < numCourses; i++) {            if (inDegree[i] == 0) {                queue.offer(i);            }        }
        int[] ans = new int[numCourses];        int count = 0;
        while (!queue.isEmpty()) {            Integer head = queue.poll();            ans[count] = head;            count++;
            Set<Integer> successors = graph[head];            for (Integer nextCourse : successors) {                inDegree[nextCourse]--;                if (inDegree[nextCourse] == 0) {                    queue.offer(nextCourse);                }            }        }
        if (count == numCourses) {            return ans;        }                return new int[0];
    }}