LeetCode 210. Course Schedule II
LeetCode 210. 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] 。 示例 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] 。 示例 3:
输入:numCourses = 1, prerequisites = [] 输出:[0]
提示: 1 <= numCourses <= 2000 0 <= prerequisites.length <= numCourses * (numCourses - 1) prerequisites[i].length == 2 0 <= ai, bi < numCourses ai != bi 所有[ai, bi] 互不相同
算法
(拓扑排序) O(n m)
关于拓扑排序算法详见 Course Schedule 。
拓扑排序时用的队列的进队顺序就是一个可行的输出方案。\
时间复杂度
假设 n 为点数,m 为边数,拓扑排序仅遍历所有的点和边一次,故总时间复杂度为 O(n m)。
空间复杂度
需要额外 O(n m) 的空间存储邻接表,点的入度,队列和答案。
C 代码
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> in_degree(numCourses, 0);
for (int i = 0; i < prerequisites.size(); i ) {
in_degree[prerequisites[i].first] ;
graph[prerequisites[i].second].push_back(prerequisites[i].first);
}
queue<int> q;
vector<bool> vis(numCourses, false);
vector<int> ans;
for (int i = 0; i < numCourses; i )
if (in_degree[i] == 0)
q.push(i);
while (!q.empty()) {
int sta = q.front();
q.pop();
ans.push_back(sta);
vis[sta] = true;
for (int i
= 0; i < graph[sta].size(); i ) {
in_degree[graph[sta][i]]--;
if (in_degree[graph[sta][i]] == 0)
q.push(graph[sta][i]);
}
}
for (int i = 0; i < numCourses; i )
if (vis[i] == false)
return vector<int>{};
return ans;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhcbcgab
-
微信小程序没声音怎么办
PHP中文网 06-15 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
微信人名旁边有个图标有什么用
PHP中文网 03-11 -
微信提示登录环境异常是什么意思原因
PHP中文网 04-09 -
微信获取用户openid失败怎么办
PHP中文网 03-26 -
photoshop怎么把印章抠出并放在另一张图上
PHP中文网 06-15 -
EhViewer(E绅士)最新版_ehviewer白色版彩色版_Ehviewer显示网络错误怎么办?e站进不去了怎么办
Evanpatchouli 09-19 -
Excel筛选和排序是灰色的怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24