( “ 图 “ 之 拓扑排序 ) 207. 课程表 ——【Leetcode每日一题】

❓207. 课程表

难度:中等

你这个学期必须选修 numCourses 门课程,记为 0numCourses - 1

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi

例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

示例 2:

输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

提示:

  • 1 < = n u m C o u r s e s < = 1 0 5 1 <= numCourses <= 10^5 1<=numCourses<=105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

💡思路:拓扑排序(BFS)

可以将选修课程先后顺序看作有向图的边:

  • 只要该有向图不存在环,就能完成所有课程的学习。
  • 以下是判断有向图是否存在环的基本步骤:
    1. 统计每个节点的入度(即指向该节点的边的数量),并将入度为 0 的节点加入到一个队列中。
    2. 从队列中取出一个节点,并将其从图中删除,同时将其所有指向的节点的入度减 1 。如果某个节点的入度减为 0 ,则将其加入队列。
    3. 重复步骤2,直到队列为空。
    4. 如果在执行拓扑排序的过程中,存在某个节点的入度始终不为 0 ,则说明存在环,否则该有向图为DAG。

相同题解的题目:210. 课程表 II

🍁代码:(Java、C++)

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] courList = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            courList[i] = new ArrayList<>();
        }
        int[] inNum = new int[numCourses];//每个课程的入度数
        for(int[] p : prerequisites){//找到所有该前修课程之后的课程
            courList[p[1]].add(p[0]);
            inNum[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<Integer>();//存储所有入度为0的课程
        for (int i = 0; i < numCourses; i++) {
			if (inNum[i] == 0) {
				q.offer(i);
			}
		}
        while(!q.isEmpty()){//删除入度为0的点
            int curNum = q.poll();
            for(int it : courList[curNum]){
                if(--inNum[it] == 0) q.offer(it);
            }
            courList[curNum].clear();
        }
        for(int num : inNum){//如果还存在入度不为0的点,则一定存在环
            if(num != 0) return false;
        }
        return true;
    }
}

C++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<list<int>> courList(numCourses);
        vector<int> inNum(numCourses, 0);//每个课程的入度数
        for(auto p : prerequisites){//找到所有以该课程为前修课程的课程
            courList[p[1]].push_back(p[0]);
            inNum[p[0]]++;
        }
        queue<int> q;//存储所有入度为0的课程
        for (int i = 0; i < numCourses; i++) {
			if (inNum[i] == 0) {
				q.push(i);
			}
		}
        while(!q.empty()){//删除入度为0的点
            int curNum = q.front();
            q.pop();
            auto it = courList[curNum].begin();
            while(it != courList[curNum].end()){
                if(--inNum[*it] == 0) q.push(*it);
                it++;
            }
            courList[curNum].clear();
        }
        for(int num : inNum){//如果还存在入度不为0的点,则一定存在环
            if(num != 0) return false;
        }
        return true;
    }
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n + m ) O(n + m) O(n+m),其中 n 为课程数,m为先修课程的要求数。
  • 空间复杂度 O ( n + m ) O(n + m) O(n+m)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/17402.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

自动驾驶中地图匹配定位技术总结

引言 汽车定位是让自动驾驶汽车知道自身确切位置的技术&#xff0c;在自动驾驶系统中担负着相当重要的职责。汽车定位涉及多种传感器类型和相关技术&#xff0c;主要可分为卫星定位、惯性导航定位、地图匹配定位以及多传感器融合定位几大类。其中地图匹配定位技术利用道路物理…

redis使用总结

目录 redis安装与登录redis 持久化RDB(Redis DataBase)AOF(Append Only File)RDB-AOF混合持久纯缓存模式 redis 的 keyredis 的数据类型和常见应用场景StringListHashMapSet集合ZSet有序集合bitmap位图HyperLogLog基数统计GEO 地理空间Stream 流bitfiled redis 事务事务的正常执…

【微机原理】8088/8086微处理器

目录 一、8088/8086的功能结构 1.总线接口部件&#xff08;BIU&#xff09; 2.执行部件&#xff08;EU&#xff09; 二、8088/8086的寄存器结构&#xff08;14个&#xff09; 溢出标志的概念 溢出和进位的区别 8086CPU是Intel系列的16位微处理器&#xff0c;他有16根数据…

servlet技术

什么是Servlet? Servlet 是 javaEE 规范之一. 规范就是接口 Servlet 是 javaWeb三大组件之一 三大组件分别是: Servlet程序, Flter过滤器, Listener监听器Servlet 是运行在服务器上的一个 java 小程序, 他可以接收客户端发送过来的请求, 并响应数据给客户端. 手动实现S…

电话号码的字母组合

题目&#xff1a;17. 电话号码的字母组合 - 力扣&#xff08;Leetcode&#xff09; 思路&#xff1a; 给定一个电话号码字符串 digits&#xff0c;须输出它所能表示的所有字母组合。我们可以先定义一个数字字符到字母表的映射表 numToStr&#xff0c;然后再用 Combine 函数递归…

Apache Kafka 进阶(一)

官网 Apache Kafka是一个开源的分布式事件流平台&#xff0c;被数千家公司用于高性能数据管道、流分析、数据集成和关键任务应用。 核心能力 高吞吐量 在网络有限的吞吐量下&#xff0c;使用延迟低至2ms的机器集群交付消息。可扩展性 将生产集群扩展到1000个代理&#xff0c…

互联网陪诊系统功能方案

互联网陪诊系统是一款为用户提供陪同患者到医院就医全程陪同&#xff0c;排队约号&#xff0c;排队检查&#xff0c;排队缴费&#xff0c;取送结果&#xff0c;代办买药&#xff0c;代办问诊等。 业务线上预约平台&#xff0c;让客户享受到最为专业的医院助医服务. 功能介绍 专…

阿里云g8i服务器Intel Xeon(Sapphire Rapids) Platinum 8475B

阿里云服务器ECS通用型实例规格族g8i采用2.7 GHz主频的Intel Xeon(Sapphire Rapids) Platinum 8475B处理器&#xff0c;3.2 GHz睿频&#xff0c;g8i实例采用阿里云全新CIPU架构&#xff0c;可提供稳定的算力输出、更强劲的I/O引擎以及芯片级的安全加固。阿里云百科分享阿里云服…

PMP项目管理-[第八章]质量管理

质量管理知识体系&#xff1a; 规划质量管理&#xff1a; 管理质量&#xff1a; 控制质量 &#xff1a; 8.1 质量和等级的区别 质量定义&#xff1a;作为实现的性能或成果&#xff0c;是一系列内在特性满足要求的程度 等级定义&#xff1a;作为设计意图&#xff0c;是对用途相同…

DP(9)--插头DP

DP(9)--插头DP /* Mondriaan’s Dream题目大意&#xff1a;在 N*M 的棋盘内铺满 1*2 或 2*1 的多米诺骨牌&#xff0c;求方案数。 砖只有横放和竖放两种状态&#xff0c;把横放记为两个0&#xff0c;竖放记为上1下0&#xff0c;逐格DP&#xff0c;每次无论前一格…

详解MySQL慢SQL定位、分析

目录 1.概述 2.慢SQL定位 3.SQL性能分析 3.1.例子 3.2.SQL性能分析 3.3.参数说明 3.3.1.id 3.3.2.select_type 3.3.3.key_len 3.3.4.rows 3.3.5.type 3.3.6.extra 1.概述 解决慢SQL的问题无非3步&#xff1a; 定位慢SQL分析慢SQL优化慢SQL 本文将按顺序介绍前两…

【MySQL】SQL优化

上一篇索引是针对查询语句进行优化,但在MySQL中可不仅有查询语句,针对其他的SQL语句同样也能进行优化 文章目录 1.插入数据2.主键优化3.order by 优化4.group by优化5.limit优化6.update优化 1.插入数据 插入数据所使用的关键字为insert,SQL语句为 insert into 表名(字段1,字…

恢复item2和oh-my-zsh的配置

1. 首先正常安装item2 2. 加载onedrive里的传家宝iterm2_default_profile.json&#xff0c;让iterm2的配置生效 2. 然后正常安装oh-my-zsh (官方步骤&#xff1a; sh -c "$(curl -fsSL https://raw.githubusercontent.com/ohmyzsh/ohmyzsh/master/tools/install.sh)&q…

BUUCTF ciscn_2019_c_1

小白垃圾做题笔记而已&#xff0c;不建议阅读。 1前期&#xff1a; 其实刚开始拿到程序的时候我还以为是逆向题放错地方了。唉&#xff0c;做题太少了。啥也不会。我是大笨蛋。 题目中用的是ubuntu18&#xff0c;我的ubuntu没怎么用过&#xff0c;vmtools都不能用&#xff0c…

什么是GPT模型,GPT下载和国内镜像

什么是GPT模型&#xff0c;GPT模型是通过预训练的方式&#xff0c;采用无监督学习方式&#xff0c;大量语料输入&#xff0c;经过多次训练后得到模型。它能够自动学习并理解自然语言中的语义、句法和语法信息&#xff0c;并可以用于文本生成、对话系统、情感分析、机器翻译等自…

零死角玩转stm32中级篇3-SPI总线

本篇博文目录: 一.基础知识1.什么是SPI2.SPI和IIC有什么不同3.SPI的优缺点4.SPI是怎么实现通信的5.SPI 数据传输的步骤6.SPI菊花链7.通过SPI实现数据的读和写 二.STM32F103C8T6芯片SPI协议案例代码 一.基础知识 1.什么是SPI SPI&#xff08;Serial Peripheral Interface&#…

Flask开发之环境搭建

目录 1、安装flask 2、创建Flask工程 ​编辑 3、初始化效果 4、运行效果 5、设置Debug模式 6、设置Host 7、设置Port 8、在app.config中添加配置 1、安装flask 如果电脑上从没有安装过flask&#xff0c;则在命令行界面输入以下命令&#xff1a; pip install flask 如果电…

给大家介绍几个手机冷门但好用的小技巧

技巧一&#xff1a;拍照识别植物 手机的拍照识别植物功能是指在使用手机相机时&#xff0c;可以通过对植物进行拍照&#xff0c;并通过植物识别技术&#xff0c;获取植物的相关信息和资料。其主要优点如下&#xff1a; 方便实用&#xff1a;使用拍照识别植物功能&#xff0c;…

【Java笔试强训 18】

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔&#x1f93a;&#x1f93a;&#x1f93a; 目录 一、选择题 二、编程题 &#x1f525;统计每…

基于springcloud微服务的java课程资源在线学习考试系统

在我国&#xff0c;由于计算机与网络技术的不断发展&#xff0c;信息化建设的不断深入&#xff0c;不管是企业、学校或个人都在结合计算机网络技术队现有的管理或生活中的一些环节进行开发研究&#xff0c;运用计算机进行一些必要的数据信息管理&#xff0c;分析及发布&#xf…
最新文章