Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間10月前 (2025/01/27 18:47)推噓0(0推 0噓 0→)

https://leetcode.com/problems/course-schedule-iv 1462. Course Schedule IV 給你numCourses表示課程數量prerequisites[i] = [ai, bi]表示要修完ai的課才可以修 bi的課， queries[j] = [uj, vj]為判斷是否要先修uj才可以修vj，返回一個長度跟 queries一樣長的列表表示每次查詢的結果。思路: 1.先依照先決條件建圖 2.使用dfs找出點i可以訪問到的所有點，標記connected[a][i],connected[b][i],... = true 直接跑dfs會tle所以要加上記憶化搜索 3.直接判斷queries的查詢兩點是否有通就好 java code ----------------------------------------- class Solution { Boolean[][] connected; public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { // 建圖 Map<Integer, List<Integer>> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new ArrayList<>()); } for (int[] prerequisite : prerequisites) { graph.get(prerequisite[0]).add(prerequisite[1]); } this.connected = new Boolean[n][n]; for (int i = 0; i < n; i++) { dfs(i, i, graph); } List<Boolean> res = new ArrayList<>(); for (int[] query : queries) { int a = query[0]; int b = query[1]; res.add(connected[b][a] != null && connected[b][a]); } return res; } void dfs(int id, int curr, Map<Integer, List<Integer>> graph) { if (connected[curr][id] != null) { return; } connected[curr][id] = true; for (int next : graph.get(curr)) { dfs(id, next, graph); } } } ----------------------------------------- -- 你跟我說這個我有什麼辦法 https://i.imgur.com/wb5zrOy.jpeg