0记忆深度搜索中等 LeetCode1462. 课程表 IV_leetcode课程表四

1462. 课程表 IV

描述

你总共需要上 n 门课，课程编号依次为 0 到 n-1 。
有的课会有直接的先修课程，比如如果想上课程 0 ，你必须先上课程 1 ，那么会以 [1,0] 数对的形式给出先修课程数对。
给你课程总数 n 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries 。
对于每个查询对 queries[i] ，请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。
请返回一个布尔值列表，列表中每个元素依次分别对应 queries 每个查询对的判断结果。

分析

记忆深度搜索

• 构建邻接表，记录所有以某一个课程为先修课程的课程
• 判断a是不是b的先修课程，从a的链表中遍历并且向下递归直到找到b或递归结束返回false。
• 建立一个numCourses*numCourses的数组，将每次递归的结果都保存在数组中。

class Solution {
    List<List<Integer>> adjoin = new ArrayList<>();
    int[][] memory;
    List<Boolean> res = new ArrayList<>();
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        int n = numCourses;
        memory = new int[n][n];
        for(int i = 0; i < n; i++){
            adjoin.add(new ArrayList<>());
        }
        for(int i = 0; i < prerequisites.length; i++){
            adjoin.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        for(int i = 0; i < queries.length; i++){
            res.add(dfs(queries[i][0],queries[i][1]));
        }
        return res;
    }

    public boolean dfs(int a, int b){
        if(memory[a][b] == 1 || a == b){
            return true;
        }
        if(memory[a][b] == -1){
            return false;
        }
        List<Integer> li = adjoin.get(a);
        for(int i : li){
            if(dfs(i,b)){
                memory[i][b] = 1;
                return true;
            }
        }
        memory[a][b] = -1;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37