blog
blog copied to clipboard
[leetcode] 1462. Course Schedule IV
https://leetcode.com/problems/course-schedule-iv/
题目意思是给定三个输入参数
n, prerequisites, queries
Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation:
n=2 代表有两个数, 0,1,
prerequisites = [[1,0]] 代表 1指向0,
queries = [[0,1],[1,0]] 代表我们需要验证查询 是否存在 1指向0 和 0指向1 的关系.
返回[false, true] 代表 第一个指向是不存在, 第二个指向存在.
Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]
Explanation: 这个复杂一点, 因为需要查询多层关系
我的第一版答案, 可以解决上面的问题. 但是运行超时了. 输入参数
var checkIfPrerequisite = function(n, prerequisites, queries) {
return queries.map((query,i) => {
const [from , to] = query
const stack = [from]
const seen = new Set()
while(stack.length>0) {
const curr = stack.pop()
const targets = prerequisites.filter(pre => pre[0]==curr)
for(let target of targets) {
if (seen.has(target)) continue
if (target[1]==to) {
return true
}
seen.add(target)
stack.push(target[1])
}
}
return false
})
};
解决思路
-
我一开始是试试,广度优先, 换成深度优先. 但是没有什么卵用,
-
用双向链表, 但是没写出来. bug一大堆. 况且据我所知, 双向链表属于锦上添花, 没啥用.
-
空间换时间, 在循环外面生成一张查询表, 于是有了下面的答案, 有一定效果. 但是我的查询表不够高效, 我的是 map -> [数组]->[数组].
经过以上优化后的代码如下, 之前n只能是72, 现在n能跑到100了, 这说明这个思路是对的.
var checkIfPrerequisite = function(n, prerequisites, queries) {
// from to map collection
const map = prerequisites.reduce((m,e)=>{
if (!m[e]) m[e] = [];
m[e] = [...m[e], ...prerequisites.filter(query => query[0]==e[1])]
return m;
}, {})
// console.log(map)
return queries.map(([from, to]) => {
const stack = prerequisites.filter(pre => pre[0]==from)
const seen = new Set()
while(stack.length>0) {
// console.log('stack1', stack)
const curr = stack.shift()
if (curr[1]==to) {
return true
}
for(let target of map[curr]) {
if (target[1]==to) {
return true
}
if (seen.has(target)) continue
seen.add(target)
stack.push(target)
}
}
return false
})
};
这个时候大脑已经崩了. 直接翻答案.
经过进一步优化,终于解决了这个问题. 原来我上面的查询关系表太low了, 真正的高效查询表是一个图
举个例子
[[0,1],[1,2],[2,3],[3,4]]
应该生成如下图
0
1
2
3
4
[4,3],[4,1],[4,0],[3,2],[3,1],[3,0],[2,1],[2,0],[1,0]
对应的图应该是.. 我就不画了, 没绘画天赋...
4
1 0 3
2 1
而图的最佳表示方式就是map. 而map的查询速度是非常高效的. 而如果有了这样的抽象思维, 问题自然迎刃而解, 其实就是图的搜索.
{
4: [3,1,0],
3: [2,1,0],
2: [1,0],
1: [0],
0: []
}
最终答案
Runtime: 1020 ms, faster than 24.19% of JavaScript online submissions for Course Schedule IV. Memory Usage: 78.6 MB, less than 6.45% of JavaScript online submissions for Course Schedule IV.
/**
* @param {number} n
* @param {number[][]} prerequisites
* @param {number[][]} queries
* @return {boolean[]}
*/
var checkIfPrerequisite = function(n, prerequisites, queries) {
// this way to generate a map
const map = [...Array(n)].map(() => []);
for (let [pre, next] of prerequisites) {
map[pre].push(next);
}
return queries.map(([from, to]) => {
const stack = [from]
const seen = new Set()
// 此处依旧是 bfs
while(stack.length>0) {
const curr = stack.shift()
for(let target of map[curr]) { // 查询到map对应的 数组关系
if (target==to) { // 如果查询到了 对应的值, 抛出.
return true
}
if (seen.has(target)) continue // 此处缓存已经走过的路, 防止无限循环查询
seen.add(target)
stack.push(target)
}
}
return false
})
};