LeetCode_210:课程表

链接

LeetCode_210:课程表 

问题

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例

示例 1:

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

思路

拓扑排序

我的题解

题解1

思路:

1.  为每一个课程设置一个Set集合, 用于存储该课程依赖的其他课程, set集合的长度即为依赖课程的数量
2.  找出不依赖其他课程的课程信息(set集合为空), 加入到队列中
3.  将已结束的课程从依赖集合中移除, 然后判断课程在移除结束课程后, 是否不再依赖任何课程了, 如果是,则加入到队列中

public class LeeCode_210 {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses <= 0) return new int[0];

        //初始化存储每个课程的Set集合
        Set<Integer>[] courses = new Set[numCourses];
        for (int i = 0; i<numCourses; i++){
            courses[i] = new HashSet<>();
        }

        //将每个课程依赖的其他课程加入到该课程的Set集合中
        for (int i = 0; i < prerequisites.length; i++) {
            Set<Integer> courSet = courses[prerequisites[i][0]];
            courSet.add(prerequisites[i][1]);
        }

        //队列中存储没有依赖的课程
        Queue<Integer> queue = new ArrayDeque();
        Set<Integer> addedSet =  new HashSet<>();
        //找出第一个没有依赖的课程
        for (int i = 0; i < courses.length; i++) {
            if(courses[i].isEmpty()){
                queue.offer(i);
                addedSet.add(i);
            }
        }
        int count = 0; //已结束课程数量
        int[] result = new int[numCourses];  //存储已结束的课程

        //拓扑排序
        while(!queue.isEmpty()){
            //将队头的课程出队
            Integer coursing = queue.poll();
            //出队后, 加入结果列表中
            result[count++] = coursing;
            //遍历所有课程, 将已删除的课程从其他课程的依赖Set集合中移除
            for (int i = 0; i < courses.length; i++) {
                courses[i].remove(coursing);
                //当课程的依赖课程Set集合为空时, 将该课程加入到队列中
                if (courses[i].isEmpty() && !addedSet.contains(i)){
                    queue.offer(i);
                    addedSet.add(i);
                }
            }
        }
        //校验课程是否可以完成(是否存在环)
        if(count != numCourses){
            return new int[0];
        }else{
            return result;
        }
    }
}

题解2

思路:

1.  建立入度表，入度为 0 的节点先入队
2.  当队列不为空，节点出队，标记学完课程数量的变量加 1，并记录该课程
3.  将课程的邻居入度减 1
4.  若邻居课程入度为 0，加入队列
5.  用一个变量记录学完的课程数量，一个数组记录最终结果

public class LeeCode_210 {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses <= 0) return new int[0];
        int[] inDegrees = new int[numCourses];
        //设置一个数组, 用于存储每个课程所依赖其他课程的数量
        for (int[] prerequisite : prerequisites) {
            inDegrees[prerequisite[0]] ++;
        }
        //将无任何依赖的课程加入到队列中, 这些课程将先结束
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) queue.offer(i);
        }

        int count = 0;  //计算已经结束课程的数量
        int[] result = new int[numCourses]; //存储已结束的课程
        while(!queue.isEmpty()){
            Integer overCourse = queue.poll();
            result[count] = overCourse;
            count++;
            //遍历所有依赖信息, 将依赖结束课程的课程的依赖数量-1
            for (int[] prerequisite : prerequisites) {
                //prerequisite[0]: 当前课程
                //prerequisite[1]: 依赖的其他课程
                if(prerequisite[1] == overCourse){
                    if(--inDegrees[prerequisite[0]] == 0){
                        queue.offer(prerequisite[0]);
                    }
                }
            }
        }
        if(count!=numCourses){
            return new int[0];
        }else{
            return result;
        }
    }
}

其他题解:

DFS 的总体思路：

1. 建立邻接矩阵
2. DFS 访问每一个课程，若存在环直接返回
   status 保存课程的访问状态，同一个栈保存课程的访问序列

邻接矩阵(数组) + DFS

    // 邻接矩阵 + DFS   由于用的数组，每次都要遍历，效率比较低
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) return new int[0];
        // 建立邻接矩阵
        int[][] graph = new int[numCourses][numCourses];
        for (int[] p : prerequisites) {
            graph[p[1]][p[0]] = 1;
        }
        // 记录访问状态的数组，访问过了标记 -1，正在访问标记 1，还未访问标记 0
        int[] status = new int[numCourses];
        Stack<Integer> stack = new Stack<>();  // 用栈保存访问序列
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, status, i, stack)) return new int[0]; // 只要存在环就返回
        }
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    private boolean dfs(int[][] graph, int[] status, int i, Stack<Integer> stack) {
        if (status[i] == 1) return false; // 当前节点在此次 dfs 中正在访问，说明存在环
        if (status[i] == -1) return true;

        status[i] = 1;
        for (int j = 0; j < graph.length; j++) {
            // dfs 访问当前课程的后续课程，看是否存在环
            if (graph[i][j] == 1 && !dfs(graph, status, j, stack)) return false;
        }
        status[i] = -1;  // 标记为已访问
        stack.push(i);
        return true;
    }

升级版：用 HashSet 作为邻接矩阵

    // 方法 2 升级版：用 HashSet 作为邻接矩阵，加速查找速度
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) return new int[0];
        // HashSet 作为邻接矩阵
        HashSet<Integer>[] graph = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new HashSet<>();
        }
        for (int[] p : prerequisites) {
            graph[p[1]].add(p[0]);
        }
        int[] mark = new int[numCourses]; // 标记数组
        Stack<Integer> stack = new Stack<>(); // 结果栈
        for (int i = 0; i < numCourses; i++) {
            if(!isCycle(graph, mark, i, stack)) return new int[0];
        }
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    private boolean isCycle(HashSet<Integer>[] graph, int[] mark, int i, Stack<Integer> stack) {
        if (mark[i] == -1) return true;
        if (mark[i] == 1) return false;

        mark[i] = 1;
        for (int neighbor : graph[i]) {
            if (!isCycle(graph, mark, neighbor, stack)) return false;
        }
        mark[i] = -1;
        stack.push(i);
        return true;
    }