本文最后更新于 390 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
你总共需要上 numCourses
门课,课程编号依次为 0
到 numCourses-1
。你会得到一个数组 prerequisite
,其中 prerequisites[i] = [ai, bi]
表示如果你想选 bi
课程,你 必须 先选 ai
课程。
- 有的课会有直接的先修课程,比如如果想上课程
1
,你必须先上课程0
,那么会以[0,1]
数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程 a
是课程 b
的先决条件,课程 b
是课程 c
的先决条件,那么课程 a
就是课程 c
的先决条件。
你也得到一个数组 queries
,其中 queries[j] = [uj, vj]
。对于第 j
个查询,您应该回答课程 uj
是否是课程 vj
的先决条件。
返回一个布尔数组 answer
,其中 answer[j]
是第 j
个查询的答案。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出:[false,true]
解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。
示例 2:
输入:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出:[false,false]
解释:没有先修课程对,所以每门课程之间是独立的。
示例 3:
输入:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出:[true,true]
提示:
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
- 每一对
[ai, bi]
都 不同 - 先修课程图中没有环。
1 <= queries.length <= 104
0 <= ui, vi <= n - 1
ui != vi
解法一:Flody 算法
算法思路:
Flody 算法:
Floyd 算法,也称为 Floyd-Warshall 算法,是一种用于求解所有节点对最短路径的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。
Floyd算法的基本思想是通过中转节点逐步更新节点对之间的最短路径。它维护一个二维数组dist
,其中dist[i][j]
表示节点i
到节点j
之间的最短路径长度。
算法的具体步骤如下:
- 初始化
dist
数组,将所有节点对之间的距离初始化为正无穷,但对角线上的元素(即dist[i][i]
)初始化为0。 - 遍历图中的每个节点
k
,作为中转节点。对于每对节点i
和j
,如果通过节点k
可以使路径长度更短,即dist[i][k] + dist[k][j] < dist[i][j]
,则更新dist[i][j] = dist[i][k] + dist[k][j]
。 - 重复步骤2,直到遍历完所有节点作为中转节点。最终,
dist
数组中存储的就是每对节点之间的最短路径长度。
Floyd算法的时间复杂度为 O(V ^ 3),其中 V 是图中节点的数量。它适用于解决任意两个节点之间的最短路径问题,包括负权边或负权环的情况。
对于本题:
- 我们创建一个二维数组 pre, 其中 pre[i] [j] 表示节点 i 到节点 j 是否可达。
- 对于数组 prerequisites 中的每一项[a, b], 我们都将 pre[a] [b] 设置为 true。
- 接下来使用 Floyd 算法计算出节点之间的可达性。
- 在计算完所有节点对之间的可达性后,对于每一个查询 [a, b],我们之间返回 pre[a] [b]即可。
代码实现:
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
boolean[][] pre = new boolean[numCourses][numCourses];
for(int[] p : prerequisites){
pre[p[0]][p[1]] = true;
}
for(int k = 0; k<numCourses;k++){
for(int i = 0;i<numCourses;i++){
for(int j = 0; j < numCourses; j++){
pre[i][j] |= pre[i][k] && pre[k][j];
}
}
}
List<Boolean> ans = new ArrayList<>();
for(int[] q : queries){
ans.add(pre[q[0]][q[1]]);
}
return ans;
}
}
复杂度分析:
时间复杂度: O(n ^ 3)
空间复杂度: O(n ^ 2)
解法二:拓扑排序 + BFS
算法思路:
本题与 207. 课程表 – 拓扑排序 210. 课程表 II – 拓扑排序 解法思路基本一致,不同之处在于:
- 创建一个二维数组 pre, 其中 pre[i] [j] 表示节点 i 到节点 j 是否可达。
- 在遍历邻接表的同时计算课程对之间的可达性。
代码实现:
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
int[] inDegree = new int[numCourses]; // 入度数组
HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表
boolean[][] pre = new boolean[numCourses][numCourses]; // 节点对可达性
// 构建入度数组和邻接表
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map.containsKey(prerequisites[i][1])) { // 当前课已经存在于邻接表
map.get(prerequisites[i][1]).add(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
List<Integer> list = new ArrayList<>();
list.add(prerequisites[i][0]);
map.put(prerequisites[i][1], list);
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int selected = queue.poll(); // 当前选的课,出列
List<Integer> toEnQueue = map.get(selected); // 获取这门课对应的后续课
if (toEnQueue != null && !toEnQueue.isEmpty()) { // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
int dependentCourse = toEnQueue.get(i);
// 记录课程之间的可达性
pre[selected][dependentCourse] = true;
for(int h = 0; h < numCourses; h++){
pre[h][dependentCourse] |= pre[h][selected];
}
inDegree[dependentCourse]--; // 依赖它的后续课的入度-1
if (inDegree[dependentCourse] == 0) { // 如果因此减为0,入列
queue.offer(dependentCourse);
}
}
}
}
List<Boolean> ans = new ArrayList<>();
for(int[] q : queries){
ans.add(pre[q[1]][q[0]]);
}
return ans;
}
}
复杂度分析:
时间复杂度: O(n ^ 2)
空间复杂度: O(n ^ 2)