Course Schedule Series

发表于

Course Schedule

Question

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, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Analysis

先将题给的先修课程转化为图结构，利用队列不断寻找入度为0的节点，最后判断所有入度为0的节点个数是否等于numcourses

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int len=numCourses;
        int[][] graph=new int[len][len];
        int[] degree=new int[len];
        
        for(int i=0;i<prerequisites.length;i++){
            int prenode=prerequisites[i][1];
            int tonode=prerequisites[i][0];
            if(graph[prenode][tonode]==0)
                degree[tonode]++;
            graph[prenode][tonode]=1;
        }
        
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<len;i++){
            if(degree[i]==0)
                queue.offer(i);
        }
        
        int count=0;
        while(!queue.isEmpty()){
            int tmp=queue.poll();
            count++;
            for(int i=0;i<len;i++){
                if(graph[tmp][i]!=0){
                    if(--degree[i]==0){
                        queue.offer(i);
                    }
                }
            }
        }
        
        return count==len;
    }
}

Course Description II

Question

同上，输出拓扑排序结果

Analysis

注意：

  • 在构建图的时候可能会存在重复的先修关系，所以需要判断该点在图中是否已为1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int len=prerequisites.length;
        int n=numCourses;
        int[] res=new int[n];
        int[][] graph=new int[n][n];
        int[] degree=new int[n];
        
        for(int i=0;i<len;i++){
            int from=prerequisites[i][1];
            int to=prerequisites[i][0];
            if(graph[from][to]==0)
                degree[to]++;
            graph[from][to]=1;
        }
        
        Queue<Integer> queue=new LinkedList<>();
        
        for(int i=0;i<n;i++){
            if(degree[i]==0)
                queue.offer(i);
        }
        
        int cnt=0;
    
        while(!queue.isEmpty()){
            int tmp=queue.poll();
            res[cnt++]=tmp;
            for(int j=0;j<n;j++){
                if(graph[tmp][j]!=0){
                    if(--degree[j]==0){
                        queue.offer(j);
                    }
                }
            }
        }
        
        if(cnt==n)
            return res;
        else
            return new int[0];
    }
}