[leetcode] 1462. Course Schedule IV

[plh97]

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
    })
};

解决思路

1. 我一开始是试试,广度优先, 换成深度优先. 但是没有什么卵用,

2. 用双向链表, 但是没写出来. bug一大堆. 况且据我所知, 双向链表属于锦上添花, 没啥用.

3. 空间换时间, 在循环外面生成一张查询表, 于是有了下面的答案, 有一定效果. 但是我的查询表不够高效, 我的是 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
    })
};