【Leetcode】207.课程表

207.课程表

题目

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

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

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

 

示例 1:
输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

分析

对于这种问题，我们都可以画一张有向图，其中节点对应课程，有向边表示优先级顺序。
那么在优先级限制下的调度问题就等价于拓扑排序问题。

**拓扑排序：给定一幅有向图，将所有的节点排序，使得所有有向边均从排在前面的节点指向排在后面的节点。

而一旦一个优先级问题的有向图中存在环，则不可能找出一个正确的拓扑排序。因此，本题目实则是判断这个有向图中是否存在环。我们有DFS和BFS两种方式。

方法一(DFS)

算法步骤：

  • 首先进行建图操作，即通过给定的prerequisites建立一张用邻接表表示的图。
  • status数组用于记录节点的访问状态，访问过了标记 -1，正在访问标记 1，还未访问标记 0
  • 从图中的每个节点开始进行深度优先搜索，一旦从该节点出发可以找到环，则返回false.如果从所有节点开始都找不到环，则返回true。
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
class Solution {
    List<List<Integer>> adj;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] status = new int[numCourses];
        for(int i = 0; i < numCourses; i++)
            status[i] = 0;
        //第一步：将给定的prerequisites转换为邻接表
        adj = new ArrayList<>();
        for(int i = 0; i < numCourses; i++)
            adj.add(new ArrayList<>());
        for(int[] item: prerequisites){
            adj.get(item[1]).add(item[0]);
        }
        //从图中的每一个节点开始进行DFS，如果以任意一个节点开始都不存在环，则返回true
        for(int i = 0; i < numCourses; i++){
            if(dfs(i, status))
                return false;
        }
        return true;
    }
    //判断从节点i出发，能否找到一个环。
    public boolean dfs(int i, int status[]){
        //若当前节点i在此轮dfs中的状态为正在访问，说明在本轮dfs中之前遍历到了i,现在又回到了i，则存在环
        if(status[i] == 1)
            return true;
        //如果当前节点i在之前某次dfs中已经访问完了，说明从i出发不会有环，返回false。
        if(status[i] == -1)
            return false;
        status[i] = 1;
        for(int neighbor : adj.get(i)){
            //如果从i的一个邻居neighbor出发可以找到一个环，因为i可以走到neighbor。所以从i出发也可以找到一个环，返回true
            if(dfs(neighbor, status))
                return true;
        }
        //此刻i已经访问完，标记其为已访问
        status[i] = -1;;
        return false;
    }
}
  • 时间复杂度：O(n + m) 对图进行深度优先搜索的时间复杂度
  • 空间复杂度：O(n + m) 邻接表需要O(n + m)的空间，DFS队列需要O(n)的栈空间，总空间复杂度为O(n + m)

方法二（BFS)

算法步骤：

  • 准备一个队列，先让入度为0的节点入队列。（入度为0代表此课无先修课程，可以选）
  • 接着进入BFS流程，每次让队首节点出列，并相应地更新相连节点的入度。（出列代表课被选，同时相邻节点的先修课程就少了一门）
  • 如果某个节点的入度更新后为0，则让它入队列。

我们用一个变量count记录遍历过的节点数。如果BFS流程走完时，count不等于prerequisites，则意味着无法选齐所有的课，返回false。否则返回true

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
class Solution {
    List<List<Integer>> adj;
    int[] indegree;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //根据给定的prerequisites构造邻接表和入度表
        adj = new ArrayList<>();
        indegree = new int[numCourses];
        for(int i = 0; i < numCourses; i++)
            adj.add(new ArrayList<>());
        for(int[] item: prerequisites){
            adj.get(item[1]).add(item[0]);
            indegree[item[0]]++;
        }
        //先让入度为0的节点入队列
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0)
                queue.offer(i);
        }
        //count用来记录遍历到的节点个数
        int count = 0;
        while(!queue.isEmpty()){
            int temp = queue.poll();
            count++;
            //每遍历到一个节点，便更新它相邻节点的入度。
            //如果相邻节点的入度更新后为0，则将其入队
            for(int neighbor: adj.get(temp)){
                indegree[neighbor]--;
                if(indegree[neighbor] == 0)
                    queue.offer(neighbor);
            }
        }
        return count == numCourses;
    }
}
  • 时间复杂度：O(n + m) 对图进行广度优先搜索的时间复杂度
  • 空间复杂度：O(n + m) 邻接表需要O(n + m)的空间，BFS队列需要O(n)的空间，总空间复杂度为O(n + m)

210.课程表 II

题目

现在你总共有 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] 。

方法一（DFS）

此题与第207题的唯一不同在于，207题只需要判断是否能找到一种可能的拓扑排序。这道题让我们求出具体的一种拓扑排序。

我们只需用一个栈纪录已访问的序列即可，在dfs函数中，一旦遍历完当前节点i的所有邻居，并且从所有邻居开始都不存在有向环，则将节点i入栈。（注意：若不存在有向环，当i入栈时，它的所有邻居均已入栈，于是i位于栈顶，同时i是拓扑排序的起点）。

在深度优先遍历后，我们将栈中的元素依次弹出，就可以得到正确的拓扑排序了。

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
44
class Solution {
    List<List<Integer>> adj;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses == 0)
            return new int[0];
        //status数组用于记录节点的访问状态，访问过了标记 -1，正在访问标记 1，还未访问标记 0。数组初始化为全0
        int[] status = new int[numCourses];
        for(int i = 0; i < numCourses; i++)
            status[i] = 0;
        //第一步：将给定的prerequisites转换为邻接表
        adj = new ArrayList<>();
        for(int i = 0; i < numCourses; i++)
            adj.add(new ArrayList<>());
        for(int[] item: prerequisites){
            adj.get(item[1]).add(item[0]);
        }
        //栈stack用于保存拓扑排序的序列
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < numCourses; i++){
            if(dfs(i, status, stack))
                return new int[0];
        }
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
    //判断从节点i出发，能否找到一个环。
    public boolean dfs(int i, int status[], Stack<Integer> stack){
        if(status[i] == 1)
            return true;
        if(status[i] == -1)
            return false;
        status[i] = 1;
        for(int neighbor : adj.get(i)){
            if(dfs(neighbor, status, stack))
                return true;
        }
        status[i] = -1;
        stack.push(i);
        return false;
    }
}

方法二（BFS)

和上一题的唯一不同在于，上一题只需要判断BFS结束后的count是否等于numCourses即可。这道题我们要用一个数组记录下BFS过程中所经过的节点。

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
class Solution {
    List<List<Integer>> adj;
    int[] indegree;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses == 0)
            return new int[0];
        int[] res = new int[numCourses];
        //根据给定的prerequisites构造邻接表和入度表
        adj = new ArrayList<>();
        indegree = new int[numCourses];
        for(int i = 0; i < numCourses; i++)
            adj.add(new ArrayList<>());
        for(int[] item: prerequisites){
            adj.get(item[1]).add(item[0]);
            indegree[item[0]]++;
        }
        //先让入度为0的节点入队列
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0)
                queue.offer(i);
        }
        //count用来记录遍历到的节点个数
        int count = 0;
        while(!queue.isEmpty()){
            int temp = queue.poll();
            res[count++] = temp;
            //每遍历到一个节点，便更新它相邻节点的入度。
            //如果相邻节点的入度更新后为0，则将其入队
            for(int neighbor: adj.get(temp)){
                indegree[neighbor]--;
                if(indegree[neighbor] == 0)
                    queue.offer(neighbor);
            }
        }
        if(count != numCourses)
            return new int[0];
        return res;
    }
}