Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-07-13 22:51:55
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:
作者: a9486l (a9486l)   2023-07-13 22:52:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com