想要精通算法和SQL的成长之路 - 课程表IV

前言

想要精通算法和SQL的成长之路 - 系列导航

做这个题目之前可以回顾一下：课程表II

一. 课程表IV （拓扑排序）

原题链接

这道题目在课程表II的基础上做了什么升华呢？也就是课程之间的先决条件是可以继承的。 那么我们在原本的拓扑排序基础上可以做些什么操作？

• 我们需要记录这个先决关系，记录每一对课程之间是否存在直接或间接的先决条件。这里我们可以用一个二维数组matrix来存储。
• 最终的返回结果，根据queries数组的一二维坐标可以直接查询。

我们先看下拓扑排序中的几个重要步骤：

1.构建邻接图以及计算每个节点的入度数。

List[] adj = new List[numCourses];
// 初始化集合而已
for (int i = 0; i < numCourses; i++) {
    adj[i] = new ArrayList<Integer>();
}
int[] inDegree = new int[numCourses];
for (int[] prerequisite : prerequisites) {
	// [0,1] --> 0->1
    adj[prerequisite[0]].add(prerequisite[1]);
    // 后继节点的入度+1
    inDegree[prerequisite[1]]++;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.利用queue队列，将入度为0的先入队，并做后续的递归操作。入度为0，则说明没有先决课程，可以直接学习。

LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
    if (inDegree[i] == 0) {
        queue.offer(i);
    }
}
1
2
3
4
5
6

3.开始递归：

while (!queue.isEmpty()) {
    Integer pre = queue.poll();
    List<Integer> nextNode = adj[pre];
    for (Integer next : nextNode) {
    	// 入度-1
        inDegree[next]--;
        // 入度为0之后，立马加入队列，进入下一次递归
        if (inDegree[next] == 0) {
            queue.offer(next);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

那么本题目将在第三个步骤中增添核心逻辑：

1. 我们准备一个二维数组matrix。
2. 同时在递归过程中，将对应的指向关系设置为true，代表他们之间的有向性 pre --> next。如果说存在节点 i --> pre。那么一定有i --> next。

boolean[][] matrix = new boolean[numCourses][numCourses];
while (!queue.isEmpty()) {
    Integer pre = queue.poll();
    List<Integer> nextNode = adj[pre];
    for (Integer next : nextNode) {
    	// 当前的有向性
        matrix[pre][next] = true;
        // 同时遍历一次数组，在满足pre->next的前提下，如果有i->pre。必定有i->next (i->pre->next)
        // 注意，这里的遍历，我们的纵坐标是固定的，因为纵坐标是指向地（后继节点），而出发点我们应该遍历所有的情况
        for (int i = 0; i < numCourses; i++) {
            if (matrix[i][pre]) {
                matrix[i][next] = true;
            }
        }
        inDegree[next]--;
        if (inDegree[next] == 0) {
            queue.offer(next);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最后根据题目的入参queries，像查字典一样，从matrix字典中查出每组的答案：

ArrayList<Boolean> res = new ArrayList<>();
for (int[] query : queries) {
    res.add(matrix[query[0]][query[1]]);
}
return res;
1
2
3
4
5

最终完整代码如下：

public class Test1462 {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List[] adj = new List[numCourses];
        boolean[][] matrix = new boolean[numCourses][numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        int[] inDegree = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            adj[prerequisite[0]].add(prerequisite[1]);
            inDegree[prerequisite[1]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer pre = queue.poll();
            List<Integer> nextNode = adj[pre];
            for (Integer next : nextNode) {
                matrix[pre][next] = true;
                for (int i = 0; i < numCourses; i++) {
                    if (matrix[i][pre]) {
                        matrix[i][next] = true;
                    }
                }
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        ArrayList<Boolean> res = new ArrayList<>();
        for (int[] query : queries) {
            res.add(matrix[query[0]][query[1]]);
        }
        return res;
    }
}
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