Leetcode刷题

Problem 207

Posted by Ruizhi Ma on October 29, 2020

Solution URL

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

代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //ans: https://www.youtube.com/watch?v=oa6uR2yNG_s
        int[] indegree = new int[numCourses];

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

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

        //比较课程号和入度的关系，更新入度的值
        while(!queue.isEmpty()){
            //入度为0的课程号
            int cur = queue.poll();

            for(int[] pairs: prerequisites){
                //当前课程入度为0，跳过
                if(indegree[pairs[0]] == 0) continue;

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

                if(indegree[pairs[0]] == 0) queue.offer(pairs[0]);
            }
        }

        //仍然有入度不为0（有先修课没有修完）
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] != 0) return false;
        }

        return true;
    }
}