原文链接: https://leetcode-cn.com/problems/QA2IGt

中文题目

现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。

给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。

请根据给出的总课程数  numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。

可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

 

示例 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,1,2,3] or [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 门课，直接修第一门课就可。

 

提示:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• prerequisites 中不存在重复元素

 

注意：本题与主站 210 题相同：https://leetcode-cn.com/problems/course-schedule-ii/

通过代码

高赞题解

我总结了剑指Offer专项训练的所有题目类型，并给出了刷题建议和所有题解。

在github上开源了，不来看看吗？顺道一提：还有C++、数据结构与算法、计算机网络、操作系统、数据库的秋招知识总结，求求star了，这对我真的很重要？

$\Rightarrow$通关剑2

拓扑排序

Kahn

执行用时：16 ms, 在所有 C++ 提交中击败了93.75%的用户
内存消耗：13 MB, 在所有 C++ 提交中击败了86.25%的用户

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 存储边集同时统计入度
        vector<vector<int>> edges(numCourses);
        vector<int> inDegree(numCourses);
        for (const vector<int>& prerequisite : prerequisites) {
            edges[prerequisite[1]].push_back(prerequisite[0]);
            inDegree[prerequisite[0]]++;
        }
        queue<int> q;
        // 入度为0的结点入队
        // 如上图所示可以用栈，一回事，没有严格顺序
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0)
                q.push(i);
        }
        vector<int> ans;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            ans.push_back(node);
            // 某个结点出队后，起指向的所有结点入度-1，减到0立即入队
            for (int i = 0; i < edges[node].size(); ++i) {           
                if (--inDegree[edges[node][i]] == 0) 
                    q.push(edges[node][i]);
            }
        }
        // 结点集合不够数，那就返回空集
        if (ans.size() < numCourses) return {};
        return ans;
    }
};

DFS

TODO

统计信息

通过次数	提交次数	AC比率
1928	3295	58.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言