​LeetCode刷题实战210:课程表 II

简介: 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 课程表 II,我们先来看题面:https://leetcode-cn.com/problems/course-schedule-ii/


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

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

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

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.


题意


现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。

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

示例

示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[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] 。
说明:
输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

解题


本题跟 207 题完全一致,只是增加了路径输出。207可以点击看, LeetCode刷题实战207:课程表

广度优先

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      unordered_map<int, unordered_set<int>> m;
      vector<int> indegree(numCourses, 0);
      for(auto& pre : prerequisites)
      {
        m[pre[1]].insert(pre[0]);
        indegree[pre[0]]++;
      }
      queue<int> q;
      int tp, finish = 0, i;
      for(i = 0; i < numCourses; ++i)
        if(indegree[i] == 0)
          q.push(i);
      vector<int> ans(numCourses);
      i = 0;
    while(!q.empty())
    {
      tp = q.front();
      finish++;
      ans[i++] = tp;
      q.pop();
      for(auto id : m[tp])
      {
        if(--indegree[id] == 0)
          q.push(id);
      }
    }
    if(i != numCourses)
      return {};
    return ans;
    }
};


深度优先

class Solution {
    unordered_map<int, unordered_set<int>> m;
    vector<int> ans;
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
      for(auto& pre : prerequisites)
      {
            m[pre[1]].insert(pre[0]);
            indegree[pre[0]]++;
        }
        bool can = true;
        vector<int> visited(numCourses,0);
      for(int i = 0; i < numCourses; ++i)
        {
            if(indegree[i]==0)//从入度0的开始
                dfs(i, visited, can);
            if(!can)
                return {};
        }
        if(ans.size() < numCourses)//不够个数,说明有的存在环
            return {};
        reverse(ans.begin(),ans.end());//反序
        return ans;
    }
    void dfs(int i, vector<int> & visited, bool &can)
    {
        if(!can) return;
        if(visited[i]==2) return;
        if(visited[i]==1)
        {
            can = false;
            return;
        }
        visited[i] = 1;//进入的时候为1
        for(auto id : m[i])
            dfs(id, visited, can);
        visited[i] = 2;//出去的时候为2
        ans.push_back(i);//出去的时候push进去,(这是最后做的)最终答案反序即可
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

相关文章
|
16天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
16天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
17天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
17天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
17天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
17天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
17天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
17天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
17天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
17天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串