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 中每取出一个数组就将其存在结果中,最终若有向图中有环,则结果中元素的个数不等于总课程数,那我们将结果清空即可。代码如下:

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++实现另类字典内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode数组练习题

    目录 1.存在重复元素 2.最大子序和 3.两数之和 4.合并两个有序数组 5.两个数组的交集II 6.买卖股票的最佳时机 7.杨辉三角 8.重塑矩阵 9.有效的数独 10.矩阵置零 总结 1.存在重复元素 排序数组,之后遍历是否有重复的元素 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for(int i=1;i<nums.length;i++){ if(nums[i-1]==nums[i]){ return

  • C++实现LeetCode(692.前K个高频词)

    [LeetCode] 692.Top K Frequent Words 前K个高频词 Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alph

  • C++实现LeetCode(347.前K个高频元素)

    [LeetCode] 347. Top K Frequent Elements 前K个高频元素 Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume

  • C++实现LeetCode(676.实现神奇字典)

    [LeetCode] 676.Implement Magic Dictionary 实现神奇字典 Implement a magic directory with buildDict, and search methods. For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary. For the method search, you'll be given a

  • C++实现LeetCode(648.替换单词)

    [LeetCode] 648.Replace Words 替换单词 In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another w

  • C++实现LeetCode(209.最短子数组之和)

    [LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和 Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead. Example:  Input: s = 7, num

  • 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] G

  • C++实现LeetCode(207.课程清单)

    [LeetCode] 207. Course Schedule 课程清单 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

  • C++实现LeetCode(45.跳跃游戏之二)

    [LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i

  • C++实现LeetCode(90.子集合之二)

    [LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • C++实现LeetCode(126.词语阶梯之二)

    [LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed

  • C++实现LeetCode(140.拆分词句之二)

    [LeetCode] 140.Word Break II 拆分词句之二 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Not

  • Oracle不同数据库间对比分析脚本

    正在看的ORACLE教程是:Oracle不同数据库间对比分析脚本. Oracle数据库开发应用中经常对数据库管理员有这样的需求,对比两个不同实例间某模式下对象的差异或者对比两个不同实例某模式下表定义的差异性,这在涉及到数据库软件的开发应用中是经常遇到的.一般数据库软件的开发都是首先在开发数据库上进行,开发到一定程度后,系统投入运行,此时软件处于维护阶段.针对在系统运行中遇到的错误.bug等,还有应用系统的升级,经常需要调整后台程序,数据库开发人员经常遇到这样一种尴尬的事情,维护到一定时期,开发库

  • java二叉树的数据插入算法介绍

    目录 例题: 对于二叉树的遍历有三种方式 二叉树插入数据的原理/思路是什么? 代码实现 整体代码 全部代码 例题: leetcode 第701题 二叉树插入数据 题目: 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树. 返回插入后二叉搜索树的根节点. 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同. 对于二叉树的遍历有三种方式 前序遍历:根左右 的顺序 中序遍历:左根右 的顺序 后序遍历:左右根 的顺序 二叉树插入数据的原理/思路是什么? 二叉树的左侧的数会比右

随机推荐