Leetcode刷题

Problem 210

Posted by Ruizhi Ma on October 29, 2020

Solution URL

https://leetcode.com/submissions/detail/414627437/

代码

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //https://www.youtube.com/watch?v=qunhYX91VLU
        int[] indegree = new int[numCourses];
        int[] res = new int[numCourses];
        int k = 0;

        //统计入度
        for(int[] pairs: prerequisites){
            indegree[pairs[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        //入度为0，入队（即不需要前置课）,当前课程进res
        for(int i = 0; i < numCourses ; i++){
            if(indegree[i] == 0){
                queue.offer(i);
                res[k++] = i;
            }
        }

        //比较课程号和入度的关系，更新入度的值
        while(!queue.isEmpty()){
            //入度为0的课程号,可以为做先修课
            int pre = queue.poll();

            for(int[] pairs: prerequisites){

                //入度为0的课程号，刚好是当前课程的先修课，则入度-1
                if(pre == pairs[1]){
                    indegree[pairs[0]]--;

                    //若入度已经为0，则已经可以修了。入队，入结果集
                    if(indegree[pairs[0]] == 0){
                        queue.offer(pairs[0]);
                        res[k++] = pairs[0];
                    }
                }
            }
        }

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