亲宝软件园·资讯

展开

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

Grandyang 人气:0
想了解C++实现LeetCode(210.课程清单之二)的相关内容吗,Grandyang在本文为您仔细讲解C++实现课程清单之二的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++实现课程清单之二,C++实现LeetCode课程清单之二,下面大家一起来学习吧。

[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:

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

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

加载全部内容

相关教程
猜你喜欢
用户评论