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 表示前面的課已經修完），每次循環時當修完 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<>();
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();
for (int next : graph.get(curr)) {
in[next]--;
if (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
推
07/13 22:52,
2年前
, 1F
07/13 22:52, 1F
※ 編輯: Rushia (60.250.69.212 臺灣), 07/14/2023 09:30:48
討論串 (同標題文章)
完整討論串 (本文為第 366 之 719 篇)：