1462. 课程表 IV
难度: 中等
来源: 每日一题 2023.09.12
现你总共需要上 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 <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= n - 1ai != bi- 每一对 [ai, bi] 都 不同
- 先修课程图中没有环。
1 <= queries.length <= 1040 <= ui, vi <= n - 1ui != vi
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
}
}
分析与题解
-
深度优先遍历 + 邻接表 + 暴力搜寻
已失败, 原因: 暴力搜索时间过长
虽然失败了, 但是也是我立马想到的方案, 还是利用邻接表的形式, 对于queries中每一组 都进行一次完成的深度优先搜索, 所以会有很多的重复过程, 然后最终导致时间超时.
整体的解题思路还是和前面的题目一样, 还是先构建邻接表, 然后进行深度优先遍历.
// 构建邻接表 Map<Integer, List<Integer>> cache = new HashMap<>(); for(int[] item : prerequisites) { if(cache.get(item[0]) == null) { cache.put(item[0], new ArrayList<>()); } cache.get(item[0]).add(item[1]); }在这种考虑情况下, 有人会说为啥不能把先前的遍历过程中已知的关系存储起来呢? 其实我当时也是在想这样的问题, 我该如何解决, 但是当时没有想到合适的解决方案, 所以就直接采用了暴力搜寻的方案了.
List<Boolean> result = new ArrayList<>(); for(int[] item : queries) { result.add(dfs(cache, cache.get(item[0]), item[1])); }对于深度遍历方法的实现, 当我们遇到没有邻接表的时候,就直接返回false, 认为两个课程直接没有任何关系.
其他按照正常情况寻找即可. 还是那话, 暴力搜寻很简单, 但是容易时间超时.
public Boolean dfs(Map<Integer, List<Integer>> cache, List<Integer> subCache, int find) { if (subCache == null) { return false; } for (Integer item : subCache) { if (item == find) { return true; } if (dfs(cache, cache.get(item), find)) { return true; } } return false; }接下来,我们看一下整体的解题思路如下所示.
class Solution { public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { // 构建邻接表 Map<Integer, List<Integer>> cache = new HashMap<>(); for(int[] item : prerequisites) { if(cache.get(item[0]) == null) { cache.put(item[0], new ArrayList<>()); } cache.get(item[0]).add(item[1]); } List<Boolean> result = new ArrayList<>(); for(int[] item : queries) { result.add(dfs(cache, cache.get(item[0]), item[1])); } return result; } public Boolean dfs(Map<Integer, List<Integer>> cache, List<Integer> subCache, int find) { if (subCache == null) { return false; } for (Integer item : subCache) { if (item == find) { return true; } if (dfs(cache, cache.get(item), find)) { return true; } } return false; } }
复杂度分析:
- 时间复杂度: O(n²), 每一个节点都最多要搜寻一遍邻接表内容.
- 空间复杂度: O(n), 会创建两个空间
result、cache, 每一个空间都与所有课程节点数成线性关系.
结果如下所示.
-
深度优先遍历 + 优先矩阵
通过上面的失败解题经验, 我们知道, 我们必须要找到一个合适的方式来存储
课程 i和 所有课程的关系, 这时候我们就必须要构建一个关系矩阵. 我们创建一个numCourses x numCourses的矩阵. 用来存储每一个课程和任意课程的关系.
然后我们通过深度优先遍历往矩阵中填充
true和false, 这时候有一个问题, 我们如何知道课程 A是课程 B的 间接先导课程 呢?直接先导课程好说, 我们通过邻接表就可以获得, 那 间接先导课程 呢?
这里就要说一点, 那就是通过邻接节点来解决这个问题, 在递归过程中, 我们一定会先搞定邻接节点的关系表, 假设如图所示.
在上图中, 假设我们查找课程为
1, 查找到邻接节点2中。 我们会找到2中的邻接关系, 如果1和2有直接的邻接关系, 那么1和 2 中的 所有邻接节点 都有先导关系.找到这样的逻辑之后, 为了防止重复多次遍历, 我们需要一个数组来记录已经查找过的点(这个点以及查找了所有的邻接关系 X轴方向)
然后我们看一下我们的解题过程.
依然是, 先构建邻接表.
// 构建邻接表 Map<Integer, List<Integer>> cache = new HashMap<>(); for(int[] item : prerequisites) { if(cache.get(item[0]) == null) { cache.put(item[0], new ArrayList<>()); } cache.get(item[0]).add(item[1]); }然后就是构建矩阵
isPre和 已经遍历过的节点数组viboolean[] vi = new boolean[numCourses]; boolean[][] isPre = new boolean[numCourses][numCourses];然后就是对每一个课程都进行深度优先遍历.
for(int i = 0; i < numCourses; i++) { dfs(cache, isPre, vi, i); }在深度优先遍历方法中, 我们首先要记录是否被遍历过, 如果遍历过, 那就不遍历这个节点了, 也是为了防止存在环的情况.
// 判断先前是否遍历过,这个return包含两个意义. // 1. 判断本次是否遍历过,防止有环 // 2. 判断别的邻接表条目是否遍历过, 防止过度遍历 if (vi[index]) { return; }然后把当前节点添加到已经查找完成的数组中.
vi[index] = true;然后就是对当前节点的所有邻接节点进行遍历.
for (int item : list) { // 添加直接关系 isPre[index][item] = true; dfs(cache, isPre, vi, item); // 添加间接关系 for (int i = 0; i < isPre.length; ++i) { isPre[index][i] = isPre[index][i] | isPre[item][i]; } }上面的代码我们就可以如何添加的间接关系, 是通过
isPre[index][i] = isPre[index][i] | isPre[item][i]来判断的.这样, 整体的解题过程就完成了.
接下来, 我们一起看下完整的解题过程.
class Solution { public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { // 构建邻接表 Map<Integer, List<Integer>> cache = new HashMap<>(); for(int[] item : prerequisites) { if(cache.get(item[0]) == null) { cache.put(item[0], new ArrayList<>()); } cache.get(item[0]).add(item[1]); } boolean[] vi = new boolean[numCourses]; boolean[][] isPre = new boolean[numCourses][numCourses]; for(int i = 0; i < numCourses; i++) { dfs(cache, isPre, vi, i); } List<Boolean> result = new ArrayList<>(); for(int[] item : queries) { result.add(isPre[item[0]][item[1]]); } return result; } public void dfs(Map<Integer, List<Integer>> cache, boolean[][] isPre, boolean[] vi, int index) { // 判断先前是否遍历过,这个return包含两个意义. // 1. 判断本次是否遍历过,防止有环 // 2. 判断别的邻接表条目是否遍历过, 防止过度遍历 if (vi[index]) { return; } vi[index] = true; List<Integer> list = cache.get(index); if (list != null) { for (int item : list) { // 添加直接关系 isPre[index][item] = true; dfs(cache, isPre, vi, item); // 添加间接关系 for (int i = 0; i < isPre.length; ++i) { isPre[index][i] = isPre[index][i] | isPre[item][i]; } } } } }
复杂度分析:
- 时间复杂度: O(numCourses² + m + n)
- 空间复杂度: O(numCourses² + n)，其中
numCourses为课程数，n为题目给出的先决条件的数目，主要为构建有向图和矩阵isPre的空间开销。注意返回值不计入空间复杂度。
结果如下所示.
Comments | 0 条评论