Re: [閒聊] 每日LeetCode

https://leetcode.com/problems/course-schedule/description/ 207. Course Schedule 你要修 n 堂課，prerequisites 是一個陣列，prerequisites[i] = [ai, bi] 表示你要修 ai 之前你必須要修 bi，返回 true 或 false 表示是否可以修完所有課。 Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible. 思路： 1.拓樸排序的典型題目，課程的依賴關係可以被表示為一個圖，可以用DFS或BFS來解。 2.用BFS來解就是先從入度為0的點開始拓寬，只有下一個點入度也為0的時候才加入隊列 （入度為 0 表示前面的課已經修完），然後為了避免循環再加入一個Set紀錄已經走 過的點，每次循環時當修完 a 課程就把 a 可以到達的點入度 -1，每個節點的入度 就會不斷減少。 3.最後只要檢查所有點的入度都為0就表示所有課都修完了。 Java Code： --------------------------------------------------- class Solution { public boolean canFinish(int n, int[][] prerequisites) { List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } int[] in = new int[n]; for (int[] prerequisite : prerequisites) { graph.get(prerequisite[1]).add(prerequisite[0]); in[prerequisite[0]]++; } Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (in[i] == 0) { queue.offer(i); } } while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int curr = queue.poll(); visited[curr] = true; for (int next : graph.get(curr)) { in[next]--; if (!visited[next] && in[next] == 0) { queue.offer(next); } } } } for (int i = 0; i < n; i++) { if (in[i] != 0) { return false; } } return true; } } --------------------------------------------------- -- https://i.imgur.com/PIoxddO.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689259918.A.842.html