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 the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

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:

  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?
  3. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  4. Topological sort could also be done via BFS.

这道课程清单的问题对于我们学生来说应该不陌生,因为在选课的时候经常会遇到想选某一门课程,发现选它之前必须先上了哪些课程,这道题给了很多提示,第一条就告诉了这道题的本质就是在有向图中检测环。 LeetCode 中关于图的题很少,有向图的仅此一道,还有一道关于无向图的题是 Clone Graph。个人认为图这种数据结构相比于树啊,链表啊什么的要更为复杂一些,尤其是有向图,很麻烦。第二条提示是在讲如何来表示一个有向图,可以用边来表示,边是由两个端点组成的,用两个点来表示边。第三第四条提示揭示了此题有两种解法,DFS 和 BFS 都可以解此题。先来看 BFS 的解法,定义二维数组 graph 来表示这个有向图,一维数组 in 来表示每个顶点的入度。开始先根据输入来建立这个有向图,并将入度数组也初始化好。然后定义一个 queue 变量,将所有入度为0的点放入队列中,然后开始遍历队列,从 graph 里遍历其连接的点,每到达一个新节点,将其入度减一,如果此时该点入度为0,则放入队列末尾。直到遍历完队列中所有的值,若此时还有节点的入度不为0,则说明环存在,返回 false,反之则返回 true。代码如下:

解法一:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> in(numCourses);
        for (auto a : prerequisites) {
            graph[a[1]].push_back(a[0]);
            ++in[a[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] != 0) return false;
        }
        return true;
    }
};

下面来看 DFS 的解法,也需要建立有向图,还是用二维数组来建立,和 BFS 不同的是,像现在需要一个一维数组 visit 来记录访问状态,这里有三种状态,0表示还未访问过,1表示已经访问了,-1 表示有冲突。大体思路是,先建立好有向图,然后从第一个门课开始,找其可构成哪门课,暂时将当前课程标记为已访问,然后对新得到的课程调用 DFS 递归,直到出现新的课程已经访问过了,则返回 false,没有冲突的话返回 true,然后把标记为已访问的课程改为未访问。代码如下:

解法二:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> visit(numCourses);
        for (auto a : prerequisites) {
            graph[a[1]].push_back(a[0]);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (!canFinishDFS(graph, visit, i)) return false;
        }
        return true;
    }
    bool canFinishDFS(vector<vector<int>>& graph, vector<int>& visit, int i) {
        if (visit[i] == -1) return false;
        if (visit[i] == 1) return true;
        visit[i] = -1;
        for (auto a : graph[i]) {
            if (!canFinishDFS(graph, visit, a)) return false;
        }
        visit[i] = 1;
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/207

参考资料:

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

https://leetcode.com/problems/course-schedule/discuss/58524/Java-DFS-and-BFS-solution

https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java

https://leetcode.com/problems/course-schedule/discuss/162743/JavaC%2B%2BPython-BFS-Topological-Sorting-O(N-%2B-E)

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

(0)

相关推荐

  • C++实现LeetCode(190.颠倒二进制位)

    [LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re

  • C++实现LeetCode(198.打家劫舍)

    [LeetCode] 198. House Robber 打家劫舍 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

  • C++实现LeetCode(202.快乐数)

    [LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(199.二叉树的右侧视图)

    [LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1     

  • C++实现LeetCode(309.买股票的最佳时间含冷冻期)

    [LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • 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(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

  • 基于vue开发的在线付费课程应用过程

    使用 vux UI组件库 使用 vue-navigation 缓存页面,此库实现了前进刷新后退读缓存的功能,像原生APP导航一样.用子路由的方式实现tabbar有bug,用vuex解决了. 使用 lib-flexible 解决移动页面适配 来一个清单 "dependencies": { "fastclick": "^1.0.6", "lib-flexible": "^0.3.2", "lodash

  • C语言实现销售管理系统课程设计

    本文实例为大家分享了C语言实现销售管理系统的具体代码,供大家参考,具体内容如下 一.C程序设计课程设计题目简介 该设计要求学生以某公司销售管理业务为背景,设计.开发一套“销售管理系统”软件. 通过该题目的设计过程,可以培养学生结构化程序设计的思想,加深对高级语言基本语言要素和控制结构的理解,针对c语言中的重点和难点内容进行训练,独立完成有一定工作量的程序设计任务,同时强调好的程序设计风格.得到软件工程的综合训练,提高解决实际问题的能力. 二.C程序设计课程设计的任务 1.查阅文献资料,一般在5篇

  • Git 常用命令清单(整理且详细)

    git工作区,暂存区,版本库之间的关系: 我们建立的项目文件夹就是工作区,在初始化git(git init)版本库之后会生成一个 .git文件,可以将该文件理解成git的版本库repository,.git文件里面还有很多文件其中有一个index文件就是缓存区也叫stage,git还自动生成一个分支master,及指向该分支的指针head. (.命名开头的文件是不可见文件,如果想要显示文件,需要设置:打开计算机->组织->文件夹和搜索选项->查看->高级设置->显示隐藏的文件

  • Hibernate 主清单文件配制的详细介绍

    Hibernate 主清单文件配制的详细介绍 1 Hiernate 清单配制文件 方式一 在工程src目录下创建 hibernate.cfg.xml 文件 Hiernate 开始加载时,会默认的方式去工程src目录下扫描 hibernate.cfg.xml文件,然后加载配制 public class H3Utils { private static SessionFactory factory = new Configuration().configure().buildSessionFacto

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • 使用批处理文件生成文件列表清单

    使用批处理文件生成文件列表清单,友友们都会遇到这样的情况:想要复制一个文件夹下所有文件的名字,或者将所有文件的名字列出一个清单,用手工复制的话吃力不讨好还容易出差错.小编今天在这里分享一个简单的小方法,自制bat批处理命令自动生成文件清单方便一次性复制. 方法: 先进入文件目录下,建立一个.txt格式的纯文档文件. 在这个文本文档中复制下列命令,并且保存. 复制代码 代码如下: @echo off dir /b /on >list.txt 将这个文本文档的后缀名从.txt修改为.bat 双击执行

  • C#通过windows注册表获取软件清单的方法

    本文实例讲述了C#通过windows注册表获取软件清单的方法.分享给大家供大家参考.具体如下: foreach (string SoftwareName in Object.SoftwareList()) { textBox.Text += SoftwareName + Environment.NewLine; } //////////////////////////////////////////////////////////////////////// /// <summary> ///

  • Python爬取Coursera课程资源的详细过程

    有时候我们需要把一些经典的东西收藏起来,时时回味,而Coursera上的一些课程无疑就是经典之作.Coursera中的大部分完结课程都提供了完整的配套教学资源,包括ppt,视频以及字幕等,离线下来后会非常便于学习.很明显,我们不会去一个文件一个文件的下载,只有傻子才那么干,程序员都是聪明人! 那我们聪明人准备怎么办呢?当然是写一个脚本来批量下载了.首先我们需要分析一下手工下载的流程:登录自己的Coursera账户(有的课程需要我们登录并选课后才能看到相应的资源),在课程资源页面里,找到相应的文件

随机推荐