JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

Code

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 先看入度
        // 入度为0，加入到队列中
        int[] indegree = new int[numCourses];
        int[] res = new int[numCourses];
        int k = 0;

        for(int[] pair : prerequisites){
            // 对应这个课程的序号+1，表示入度
            // 比如[1,0]
            // 在indegree中
            // index 0，1，2，3，4...
            //          1
            // 表示如果要修1课程，需要先修0课程
            indegree[pair[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.offer(i);
                res[k++] = i;
            }
        }

        while(!queue.isEmpty()){
            // 已经能够修的课程
            int pre = queue.poll();
            for(int[] pair : prerequisites){
                // [1,0]
                // 课程0已经可以修了，那么课程1的前置课程就减少了一个，因此indegree[pair[0]]--
                if(pair[1] == pre){
                    indegree[pair[0]]--;
                    // 如果这么课程的入度已经变成0，那么就是说这么课程也可以修了
                    if(indegree[pair[0]] == 0){
                        // 把入度为0的课程加入
                        queue.offer(pair[0]);
                        res[k++] = pair[0];
                    }
                }
            }
        }

        return (k == numCourses) ? res : new int[0];
    }
}