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