【LetMeFly】210.课程表 II力扣题目链接:https://leetcode.cn/problems/course-schedule-ii/
现在你总共有 numCourses
门课需要选,记为 0
到 numCourses - 1
。给你一个数组 prerequisites
,其中 prerequisites[i] = [ai , bi ]
,表示在选修课程 ai
前 必须 先选修 bi
。
例如,想要学习课程 0
,你需要先完成课程 1
,我们用一个匹配来表示:[0,1]
。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
示例 1:
输入: numCourses = 2, prerequisites = [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
TEXT
示例 2:
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3]
。另一个正确的排序是 [0,2,1,3]
。 TEXT
示例 3:
输入: numCourses = 1, prerequisites = []
输出: [0]
TEXT
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai , bi < numCourses
ai != bi
所有[ai , bi ]
互不相同
方法一:拓扑排序这道题和LeetCode 0207.课程表 非常类似,不同的是这道题需要返回选课的顺序。
我们直接把上一题的代码搬过来,稍加修改即可。
在拓扑排序过程中,如果某个节点的入度为,那么就说明这门课的先修课已经全部“学完”了,下一门课就可以学习这一门,因此把这门课添加到答案中即可。
AC代码 C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : vector<int > findOrder (int numCourses, vector<vector<int >>& prerequisites) { vector<vector<int >> graph (numCourses); vector<int > indegree (numCourses) ; vector<int > ans; for (int i = prerequisites.size () - 1 ; i >= 0 ; i--) { indegree[prerequisites[i][0 ]]++; graph[prerequisites[i][1 ]].push_back (prerequisites[i][0 ]); } int remainNode = numCourses; queue<int > q; for (int i = 0 ; i < numCourses; i++) { if (!indegree[i]) { remainNode--; q.push (i); ans.push_back (i); } } while (q.size ()) { int thisNode = q.front (); q.pop (); for (int & toNode : graph[thisNode]) { indegree[toNode]--; if (!indegree[toNode]) { remainNode--; q.push (toNode); ans.push_back (toNode); } } } if (remainNode) { return {}; } else { return ans; } } };
CPP
Python1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def findOrder (self, numCourses: int , prerequisites: List [List [int ]] ) -> List [int ]: graph = [[] for _ in range (numCourses)] indegree = [0 ] * numCourses for a, b in prerequisites: graph[b].append(a) indegree[a] += 1 q = deque() for i in range (numCourses): if not indegree[i]: q.append(i) ans = [] while q: thisCourse = q.popleft() ans.append(thisCourse) for to in graph[thisCourse]: indegree[to] -= 1 if not indegree[to]: q.append(to) return ans if len (ans) == numCourses else []
PYTHON
同步发文于CSDN,原创不易,转载请附上原文链接 哦~ Tisfy:https://letmefly.blog.csdn.net/article/details/126461788