长大后想做什么？做回小孩！

0%

LeetCode——课程表I&II

发表于 分类于 Valine：
本文字数： 486

NO.207 课程表 中等 、NO.210 课程表 II 中等

非常经典的拓扑排序问题

NO.207 课程表 中等

Ygz9p9.png

YgzSfJ.png

思路一：拓扑排序 拓扑排序的总体思路选择 广度优先遍历+贪心 。

通常拓扑排序有两个主要功能：

  1. 得到一条拓扑序列，拓扑序列不唯一。
  2. 判断一个有向图是否有环。

实现上，用两个集合，分别保存每个节点入度的数量、每个节点的下一个后继节点。还需要一个队列，进行广度优先遍历。

将没有前驱的节点(入度为 0 )入队，广搜每出队一个节点，就将该节点的所有后继邻接节点的入度 -1 ，如果入度减为 0(没有前驱节点) 则节点入队。

广搜过程中记录出队节点的数量 count，如果图中有环，则 count<numCourses 。

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (prerequisites.length == 0) return true;
    //保存每个节点的入度
    int[] inDegree = new int[numCourses];
    //保存每个节点的下一个后继邻接节点
    HashSet<Integer>[] nextAdjacency = new HashSet[numCourses];
    for (int i = 0; i < numCourses; i++) nextAdjacency[i] = new HashSet<>();
    //预处理
    for (int[] temp : prerequisites) {
        inDegree[temp[0]]++;
        nextAdjacency[temp[1]].add(temp[0]);
    }
    //广搜队列
    Queue<Integer> queue = new LinkedList<>();
    //入度为 0 的节点入队
    for (int i = 0; i < inDegree.length; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    //开始广搜,记录出过队的节点数量
    int count = 0;
    while (!queue.isEmpty()) {
        Integer poll = queue.poll();
        count++;
        //遍历出队节点的所有后继邻接节点
        for (int next : nextAdjacency[poll]) {
            //减少后继节点的一条入度
            inDegree[next]--;
            //如果后继节点的入度为 0 则入队
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    //如果存在环,则 count<numCourses
    return count == numCourses;
}

时间复杂度：O(E+V) 边的数量 E ，节点数量 V。两次遍历邻接表

空间复杂度：O(E+V)

NO.210 课程表 II 中等

YgzZkD.png

YgzETO.png

相较于前一题，本题需要返回一条拓扑排序的路径。

思路一：拓扑排序 和上一题的思路一样，区别在于本题需要记录出队的节点序列，而不仅仅是数量。

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
public int[] findOrder(int numCourses, int[][] prerequisites) {
    //保存每个节点的入度
    int[] inDegree = new int[numCourses];
    //保存每个节点的后继邻接节点
    List<Integer>[] nextAdjacency = new List[numCourses];
    //预处理
    for (int i = 0; i < numCourses; i++) nextAdjacency[i] = new LinkedList<>();
    for (int[] temp : prerequisites) {
        inDegree[temp[0]]++;
        nextAdjacency[temp[1]].add(temp[0]);
    }
    //广搜队列
    Queue<Integer> queue = new LinkedList<>();
    //入度为 0 的节点入队
    for (int i = 0; i < inDegree.length; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    //保存出队节点序列 和 数量
    int[] res = new int[numCourses];
    int count = 0;
    //广搜
    while (!queue.isEmpty()) {
        int poll = queue.poll();
        res[count++] = poll;
        //遍历出队节点的所有后继邻接节点
        for (int next : nextAdjacency[poll]) {
            //后继邻接节点入度-1
            inDegree[next]--;
            //后继邻接节点入度为 0 则入队
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    //是否有环
    return count == numCourses ? res : new int[0];
}

时间复杂度：O(E+V) 边的数量 E ，节点数量 V。两次遍历邻接表

空间复杂度：O(E+V)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github