课程表 IV

1462. 课程表 IV

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [a_i, b_i] 表示如果你想选 b_i 课程，你必须先选 a_i 课程。

有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。

先决条件也可以是间接的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [u_j, v_j]。对于第 j 个查询，您应该回答课程 u_j 是否是课程 v_j 的先决条件。

返回一个布尔数组 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 <= a_i, b_i <= n - 1
a_i != b_i
每一对 [a_i, b_i] 都不同
先修课程图中没有环。
0 <= u_i, v_i <= n - 1
u_i != v_i

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) { } };

php 解法, 执行用时: 340 ms, 内存消耗: 32.3 MB, 提交时间: 2023-09-12 09:50:43

class Solution {

    /**
     * @param Integer $numCourses
     * @param Integer[][] $prerequisites
     * @param Integer[][] $queries
     * @return Boolean[]
     */
    function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
        $g = array_fill(0, $numCourses, []);
        $indgree = array_fill(0, $numCourses, 0);
        $isPre = array_fill(0, $numCourses, array_fill(0, $numCourses, false));
        foreach ( $prerequisites as $p ) {
            $indgree[$p[1]]++;
            $g[$p[0]][] = $p[1];
        }

        $q = [];
        for ( $i = 0; $i < $numCourses; $i++ ) {
            if ( $indgree[$i] == 0 ) $q[] = $i;
        }
        while ( !empty($q) ) {
            $cur = array_shift($q);
            foreach ( $g[$cur] as $ne ) {
                $isPre[$cur][$ne] = true;
                for ( $i = 0; $i < $numCourses; $i++ ) {
                    $isPre[$i][$ne] |= $isPre[$i][$cur];
                }
                $indgree[$ne]--;
                if ( $indgree[$ne] == 0 ) $q[] = $ne;
            }
        }
        
        $res = [];
        foreach ( $queries as $query ) {
            $res[] = $isPre[$query[0]][$query[1]];
        }
        return $res;
    }
    

}

python3 解法, 执行用时: 376 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-12 07:46:21

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        g = [[] for _ in range(numCourses)]
        indgree = [0] * numCourses
        isPre = [[False] * numCourses for _ in range(numCourses)]
        for p in prerequisites:
            indgree[p[1]] += 1
            g[p[0]].append(p[1])

        q = []
        for i in range(numCourses):
            if indgree[i] == 0:
                q.append(i)
        while len(q) > 0:
            cur = q[0]
            q.pop(0)
            for ne in g[cur]:
                isPre[cur][ne] = True
                for i in range(numCourses):
                    isPre[i][ne] = isPre[i][ne] or isPre[i][cur]
                indgree[ne] -= 1
                if indgree[ne] == 0:
                    q.append(ne)
        res = []
        for query in queries:
            res.append(isPre[query[0]][query[1]])
        return res

python3 解法, 执行用时: 416 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-12 07:46:08

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        g = [[] for _ in range(numCourses)]
        vi = [False] * numCourses
        isPre = [[False] * numCourses for _ in range(numCourses)]
        for p in prerequisites:
            g[p[0]].append(p[1])

        def dfs(cur):
            if vi[cur]:
                return
            vi[cur] = True
            for ne in g[cur]:
                dfs(ne)
                isPre[cur][ne] = True
                for i in range(numCourses):
                    isPre[cur][i] = isPre[cur][i] | isPre[ne][i]

        for i in range(numCourses):
            dfs(i)
        res = []
        for query in queries:
            res.append(isPre[query[0]][query[1]])
        return res

java 解法, 执行用时: 10 ms, 内存消耗: 45.9 MB, 提交时间: 2023-09-12 07:45:49

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<Integer>();
        }
        boolean[] vi = new boolean[numCourses];
        boolean[][] isPre = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            g[p[0]].add(p[1]);
        }
        for (int i = 0; i < numCourses; ++i) {
            dfs(g, isPre, vi, i);
        }
        List<Boolean> res = new ArrayList<Boolean>();
        for (int[] query : queries) {
            res.add(isPre[query[0]][query[1]]);
        }
        return res;
    }

    public void dfs(List<Integer>[] g, boolean[][] isPre, boolean[] vi, int cur) {
        if (vi[cur]) {
            return;
        }
        vi[cur] = true;
        for (int ne : g[cur]) {
            dfs(g, isPre, vi, ne);
            isPre[cur][ne] = true;
            for (int i = 0; i < isPre.length; ++i) {
                isPre[cur][i] = isPre[cur][i] | isPre[ne][i];
            }
        }
    }
}

javascript 解法, 执行用时: 132 ms, 内存消耗: 52.3 MB, 提交时间: 2023-09-12 07:45:31

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    let g = new Array(numCourses).fill(0).map(() => new Array());
    let vi = new Array(numCourses).fill(false); 
    let isPre = new Array(numCourses).fill(0).map(() => new Array(numCourses).fill(false));
    for (let p of prerequisites) {
        g[p[0]].push(p[1]);
    }
    for (let i = 0; i < numCourses; ++i) {
        dfs(g, isPre, vi, i);
    }
    res = [];
    for (let query of queries) {
        res.push(isPre[query[0]][query[1]]);
    }
    return res;
};

var dfs = function(g, isPre, vi, cur) {
    if (vi[cur]) {
        return;
    }
    vi[cur] = true;
    for (let ne of g[cur]) {
        dfs(g, isPre, vi, ne);
        isPre[cur][ne] = true;
        for (let i = 0; i < isPre.length; ++i) {
            isPre[cur][i] = isPre[cur][i] | isPre[ne][i];
        }
    }
}

golang 解法, 执行用时: 88 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-12 07:45:10

// 深度优先搜索 + 拓扑排序
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
    g := make([][]int, numCourses)
    vi := make([]bool, numCourses)
    isPre := make([][]bool, numCourses)
    for i := 0; i < numCourses; i++ {
        isPre[i] = make([]bool, numCourses)
        g[i] = []int{}
    }
    for _, p := range prerequisites {
        g[p[0]] = append(g[p[0]], p[1])
    }

    for i := 0; i < numCourses; i++ {
        dfs(g, isPre, vi, i)
    }
    res := []bool{}
    for _, query := range queries {
        res = append(res, isPre[query[0]][query[1]])
    }
    return res
}

func dfs(g [][]int, isPre [][]bool, vi []bool, cur int) {
    if vi[cur] {
        return
    }
    vi[cur] = true
    for _, ne := range g[cur] {
        dfs(g, isPre, vi, ne)
        isPre[cur][ne] = true
        for i := 0; i < len(isPre); i++ {
            isPre[cur][i] = isPre[cur][i] || isPre[ne][i]
        }
    }
}

java 解法, 执行用时: 12 ms, 内存消耗: 46 MB, 提交时间: 2023-09-12 07:44:08

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<Integer>();
        }
        int[] indgree = new int[numCourses];
        boolean[][] isPre = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            ++indgree[p[1]];
            g[p[0]].add(p[1]);
        }
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indgree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int ne : g[cur]) {
                isPre[cur][ne] = true;
                for (int i = 0; i < numCourses; ++i) {
                    isPre[i][ne] = isPre[i][ne] | isPre[i][cur];
                }
                --indgree[ne];
                if (indgree[ne] == 0) {
                    queue.offer(ne);
                }
            }
        }
        List<Boolean> res = new ArrayList<Boolean>();
        for (int[] query : queries) {
            res.add(isPre[query[0]][query[1]]);
        }
        return res;
    }
}

javascript 解法, 执行用时: 136 ms, 内存消耗: 51.7 MB, 提交时间: 2023-09-12 07:43:42

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    let g = new Array(numCourses).fill(0).map(() => new Array());
    let indgree = new Array(numCourses).fill(0); 
    let isPre = new Array(numCourses).fill(0).map(() => new Array(numCourses).fill(false));
    for (let p of prerequisites) {
        ++indgree[p[1]];
        g[p[0]].push(p[1]);
    }
    let q = [];
    for (let i = 0; i < numCourses; ++i) {
        if (indgree[i] == 0) {
            q.push(i);
        }
    }

    while (q.length) {
        let cur = q.shift();
        for (let ne of g[cur]) {
            isPre[cur][ne] = true;
            for (let i = 0; i < numCourses; ++i) {
                isPre[i][ne] = isPre[i][ne] || isPre[i][cur];
            }
            --indgree[ne];
            if (indgree[ne] == 0) {
                q.push(ne);
            }
        }
    }
    res = [];
    for (let query of queries) {
        res.push(isPre[query[0]][query[1]]);
    }
    return res;
};

golang 解法, 执行用时: 88 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-12 07:43:24

// 广度优先搜索 + 拓扑排序
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
    g := make([][]int, numCourses)
    indgree := make([]int, numCourses)
    isPre := make([][]bool, numCourses)
    for i, _ := range isPre {
        isPre[i] = make([]bool, numCourses)
        g[i] = []int{}
    }
    for _, p := range prerequisites {
        indgree[p[1]]++
        g[p[0]] = append(g[p[0]], p[1])
    }

    q := []int{}
    for i := 0; i < numCourses; i++ {
        if indgree[i] == 0 {
            q = append(q, i)
        }
    }
            
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for _, ne:= range g[cur] {
            isPre[cur][ne] = true
            for i := 0; i < numCourses; i++ {
                isPre[i][ne] = isPre[i][ne] || isPre[i][cur]
            }
            indgree[ne]--
            if indgree[ne] == 0 {
                q = append(q, ne)
            }
        }
    }
    res := []bool{}
    for _, query := range queries {
        res = append(res, isPre[query[0]][query[1]])
    }
    return res
}

python3 解法, 执行用时: 3868 ms, 内存消耗: 19 MB, 提交时间: 2023-08-18 15:42:55

class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        self.graph = collections.defaultdict(list)
        for pre in prerequisites:
            self.graph[pre[0]].append(pre[1])
        return [self.dfs(query[0], query[1]) for query in queries]
    
    # start -> end ?
    @functools.lru_cache
    def dfs(self, start, end):
        if start == end:
            return True
        return any(self.dfs(nxt, end) for nxt in self.graph[start])

python3 解法, 执行用时: 832 ms, 内存消耗: 19 MB, 提交时间: 2023-08-18 15:42:02

class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        dp = [[False] * n for _ in range(n)]       
        for p, c in prerequisites:
            dp[p][c] = True

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dp[i][k] and dp[k][j]:
                        dp[i][j] = True
        ans = []
        for i, j in queries:
            ans.append(dp[i][j])
        return ans

cpp 解法, 执行用时: 420 ms, 内存消耗: 57.8 MB, 提交时间: 2023-08-18 15:41:10

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        int n = numCourses;
        vector<vector<bool>> dp(n, vector<bool>(n, 0));

        for (auto &pre : prerequisites) {
            dp[pre[0]][pre[1]] = true;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j]);
                }
            }
        }

        vector<bool> ans;
        for (auto &query : queries) {
            ans.push_back(dp[query[0]][query[1]]);
        }
        return ans;
    }
};

cpp 解法, 执行用时: 172 ms, 内存消耗: 61.7 MB, 提交时间: 2023-08-18 15:40:57

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        int n = numCourses;
        vector<vector<int>> graph(n);

        for (auto &pre : prerequisites) {
            graph[pre[0]].push_back(pre[1]);
        }

        vector<vector<bool>> isReached(n, vector<bool>(n));
        for (int i = 0; i < n; i++) {
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (auto &v : graph[u]) {
                    if (!isReached[i][v]) { /* 从课程i到达的其他课程进行标记 */
                        isReached[i][v] = true;
                        q.push(v);
                    }
                }
            }
        }

        vector<bool> ans;
        for (auto &query : queries) {
            ans.push_back(isReached[query[0]][query[1]]);
        }
        return ans;
    }
};

cpp 解法, 执行用时: 180 ms, 内存消耗: 60.2 MB, 提交时间: 2023-08-18 15:40:41

class Solution {
public:
    bool dfs(int start, int end) {
        if (memo[start][end] == 1) { /* start是end的先修课程 */
            return true;
        }
        if (memo[start][end] == -1) { /* 不是先修课程 */
            return false;
        }
        for (auto &mid : graph[start]) { /* 通过其他课程中转 */
            if (dfs(mid, end)) {
                memo[start][end] = true;
                return true;
            }
        }
        memo[start][end] = -1;
        return false;
    }

    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        int n = numCourses;
        graph = vector<vector<int>>(n);
        memo  = vector<vector<int>>(n, vector<int>(n));

        /* 建立邻接表 */
        for (auto &pre : prerequisites) {
            graph[pre[0]].push_back(pre[1]);
            memo[pre[0]][pre[1]] = 1;
        }

        vector<bool> ans;
        for (auto &query : queries) {
            /* dfs判断两个点是否存在依赖关系 */
            ans.push_back(dfs(query[0], query[1]));
        }
        return ans;
    }
    vector<vector<int>> graph;
    vector<vector<int>> memo;
};

上一题

下一题

详情