gpt4 book ai didi

C++实现LeetCode(210.课程清单之二)

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 29 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++实现LeetCode(210.课程清单之二)由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

[LeetCode] 210. Course Schedule II 课程清单之二

There are a total of n courses you have to take, labeled from 0 to n-1. 。

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] 。

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. 。

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. 。

Example 1

Input: 2, [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   course 0. So the correct course order is [0,1] . 。

Example 2

Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] . 。

Note

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

Hints

  • This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  • Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  • Topological sort could also be done via BFS.

这题是之前那道 Course Schedule 的扩展,那道题只让我们判断是否能完成所有课程,即检测有向图中是否有环,而这道题我们得找出要上的课程的顺序,即有向图的拓扑排序 Topological Sort,这样一来,难度就增加了,但是由于我们有之前那道的基础,而此题正是基于之前解法的基础上稍加修改,我们从 queue 中每取出一个数组就将其存在结果中,最终若有向图中有环,则结果中元素的个数不等于总课程数,那我们将结果清空即可。代码如下:

?
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
class Solution {
public :
     vector< int > findOrder( int numCourses, vector<pair< int , int >>& prerequisites) {
         vector< int > res;
         vector<vector< int > > graph(numCourses, vector< int >(0));
         vector< int > in(numCourses, 0);
         for (auto &a : prerequisites) {
             graph[a.second].push_back(a.first);
             ++in[a.first];
         }
         queue< int > q;
         for ( int i = 0; i < numCourses; ++i) {
             if (in[i] == 0) q.push(i);
         }
         while (!q.empty()) {
             int t = q.front();
             res.push_back(t);
             q.pop();
             for (auto &a : graph[t]) {
                 --in[a];
                 if (in[a] == 0) q.push(a);
             }
         }
         if (res.size() != numCourses) res.clear();
         return res;
     }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/210 。

类似题目:

Course Schedule 。

参考资料:

https://leetcode.com/problems/course-schedule-ii/ 。

https://leetcode.com/problems/course-schedule-ii/discuss/59330/Concise-JAVA-solution-based-on-BFS-with-comments 。

https://leetcode.com/problems/course-schedule-ii/discuss/59342/Java-DFS-double-cache-visiting-each-vertex-once-433ms 。

到此这篇关于C++实现LeetCode(269.另类字典)的文章就介绍到这了,更多相关C++实现另类字典内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。

原文链接:https://www.cnblogs.com/grandyang/p/4504793.html 。

最后此篇关于C++实现LeetCode(210.课程清单之二)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(210.课程清单之二)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com