LeetCode[207]课程表

难度:Medium

题目:

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 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 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

 Related Topics

  • 深度优先搜索
  • 广度优先搜索
  • 拓扑排序

重点!!!解题思路

第一步:

明确解题手段:仔细读题,可发现要先完成前置课程,必须先完成后置课程,那么后置课程其实可以看做是前置课程的一个入度(indegree),只有当一个节点入度为0时,它才可以被学习,理解到这里就可以发现此题可使用拓扑排序来解决。

第二步:

拓扑排序思路:1.把原数组关系看作是一个图

                         2.需要一个能记录每个节点的入度的数组

                         3.需要一个二维集合来记录每个0入度节点对应的子节点

                         4.需要一个队列来将入度为0的节点添加到队列中去,每次出队的时候找到它们对应的子节点,并将子节点的入度-1,当子节点的入度为0就添加到队列中,继续判断

                         5.最后当出队数量与原数量一致,那么即为正确答案

源码+讲解:

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indeg=new int[numCourses];  //这个数组:入度统计List<List<Integer>> g=new ArrayList<>();  //二维集合: 统计每个入度为0节点对应的子节点for (int i=0;i<numCourses;i++){  //首先初始化二维集合g.add(new ArrayList<>());}Queue<Integer> q=new ArrayDeque<>();  //创建一个队列用于计数操作for (int[] prerequisite : prerequisites) {indeg[prerequisite[0]]++;  //遍历给定二维数组,前置节点入度+1g.get(prerequisite[1]).add(prerequisite[0]);  //后置节点对应一个前置节点}for (int i=0;i<indeg.length;i++){  //将入度为0的节点添加到队列中去if (indeg[i]==0) q.offer(i);}while (!q.isEmpty()){  int pre = q.poll();  //每次弹出的都是一个入度为0的前置节点numCourses--;  //每弹出一个,相当于总节点数少一个,当numCourses为0时,才是答案for (Integer cur : g.get(pre)) {  //根据前置节点取出所有后置节点,并将每个后置节点入度-1,直到减为0if (--indeg[cur]==0) q.offer(cur);}}return numCourses==0;}
}

 运行结果:

如果您还有什么疑问或解答有问题,可在下方评论,我会及时回复。

系列持续更新中,点个订阅吧,喜欢练习算法那就点个攒吧 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用上 Spring 的事件机制

本文主要是简单的讲述了Spring的事件机制&#xff0c;基本概念&#xff0c;讲述了事件机制的三要素事件、事件发布、事件监听器。如何实现一个事件机制&#xff0c;应用的场景&#xff0c;搭配Async注解实现异步的操作等等。希望对大家有所帮助。 Spring的事件机制的基本概念 …

xcode 的app工程与ffmpeg 4.4版本的静态库联调,ffmpeg内下的断点无法暂停。

先阐述一下我的业务场景&#xff0c;我有一个iOS的app sdk项目&#xff0c;下面简称 A &#xff0c;以及运行 A 的 app 项目&#xff0c;简称 A demo 。 引用关系为 A demo 引用了 A &#xff0c;而 A 引用了 ffmpeg 的静态库&#xff08;.a文件&#xff09;。此时业务出现了 b…

Linux上安装Keepalived,多台Nginx配置Keepalived(保姆级教程)

目录 一、yum安装 第一步&#xff1a;下载 第二步&#xff1a;编辑Keepalived配置文件&#xff08;第一台&#xff09; 第三步&#xff1a;编辑Keepalived配置文件&#xff08;第二台&#xff09; 第四步&#xff1a;我们在本机利用cmd ping一下 一、yum安装 第一步&…

【数据结构篇】手写双向链表、单向链表(超详细)

文章目录 链表1、基本介绍2、单向链表2.1 带头节点的单向链表测试类&#xff1a;链表实现类&#xff1a; 2.2 不带头节点的单向链表2.3 练习测试类&#xff1a;链表实现类&#xff1a; 3、双向链表测试类&#xff1a;双向链表实现类&#xff1a; 4、单向环形链表**测试类**&…

从零开始实现一个 mini-Retrofit 框架

前言 本篇文章将采用循序渐进的编码方式&#xff0c;从零开始实现一个Retorift框架&#xff0c;在实现过程中不断提出问题并分析实现&#xff0c;最终开发出一个mini版的Retrofit框架 演示一个使用OkHttp的项目Demo 为了更好的演示框架的实现过程&#xff0c;这里我先创建了一…

mongodb-win32-x86_64-2008plus-3.4.24-signed.msi

Microsoft Windows [版本 6.1.7601] 版权所有 (c) 2009 Microsoft Corporation。保留所有权利。C:\Users\Administrator>cd C:\MongoDB\Server\3.4\binC:\MongoDB\Server\3.4\bin>C:\MongoDB\Server\3.4\bin>mongod --help Options:General options:-h [ --help ] …

【MySQL】增删查改基础

文章目录 一、创建操作1.1 单行插入1.2 多行插入1.3 插入否则替换更新1.4 替换replace 二、查询操作2.1 select查询2.2 where条件判断2.3 order by排序2.4 limit筛选分页结果 三、更新操作四、删除操作4.1 删除一列4.2 删除整张表数据 五、插入查询结果 CRUD : Create(创建), R…

CS 144 Lab Four 收尾 -- 网络交互全流程解析

CS 144 Lab Four 收尾 -- 网络交互全流程解析 引言Tun/Tap简介tcp_ipv4.cc文件配置信息初始化cs144实现的fd家族体系基于自定义fd体系进行数据读写的adapter适配器体系自定义socket体系自定义事件循环EventLoop模板类TCPSpongeSocket详解listen_and_accept方法_tcp_main方法_in…

【雕爷学编程】Arduino动手做(188)---0.66寸OLED液晶屏模块

37款传感器与模块的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&#x…

Source Insight显示行号

1、默认不显示行号 (1)Source Insight默认是不显示行号的&#xff0c;如下图所示。 2、配置显示行号 2.1、方法1 (1)点击View→Line Numbers。 2.2、方法2 (1)空白处鼠标右键&#xff0c;在点击"Line Numbers"。 (2)配置显示行号后如下图所示。

使用hexo进行博客迁移

本文不会从0开始介绍如何通过hexo去搭建一个github page。因为最近折腾了下&#xff0c;发现这玩意儿确实写个博客很费劲&#xff0c;打算把他拖管到github当作我的知识库网站&#xff0c;我的主要文章还是通过mweb写完一键发布到博客园&#xff0c;然后csdn记录一些杂文和思考…

Liunx环境下git的详细使用(gitee版)

Liunx环境下git的详细使用&#xff08;gitee版&#xff09; 1.git是什么2.git操作2.1在gitee创建一个仓库2.2.gitignore2.3.git 3.git三板斧3.1add3.2 commit3.3push 4.git其他命令4.1查看当前仓库状态4.2查看提交日志4.3修改git里面文件名称4.4删除文件4.5修改远端仓库内容 1.…

低碳 Web 实践指南

现状和问题 2023年7月6日&#xff0c;世界迎来有记录以来最热的一天。气候变化是如今人类面临的最大健康威胁。据世界卫生组织预测2030年至2050年期间&#xff0c;气候变化预计每年将造成约25万人死亡。这是人们可以真切感受到的变化&#xff0c;而背后的主要推手是碳排放。 …

Java分布式微服务2——声明式Http客户端(Feign)与网关(Gateway)

文章目录 Http声明式客户端FeignFeign介绍与使用Feign自定义配置Feign性能优化Feign最佳实践方案 网关Gateway网关Gateway的作用与搭建路由断言工厂Route Predicate Factory路由过滤器GatewayFilter全局过滤器过滤器执行顺序网关的跨域处理 Http声明式客户端Feign Feign介绍与…

Python魔法解析:探索变量类型的丰富多彩世界!

在Python这个魔法般的编程语言中&#xff0c;变量是连接你与计算机世界的神奇桥梁。然而&#xff0c;这些变量并不是单一的&#xff0c;它们有着丰富多彩的类型。无论你是刚刚踏入编程的大门&#xff0c;还是想要深入了解Python的高级特性&#xff0c;本篇博客将带你探索变量的…

c++学习(特殊类设计)[30]

只能在堆上创建对象的类 如果你想要确保对象只能在堆上创建&#xff0c;可以通过将析构函数声明为私有&#xff0c;并提供一个静态成员函数来创建对象。这样&#xff0c;类的实例化只能通过调用静态成员函数来完成&#xff0c;而无法直接在栈上创建对象。 以下是一个示例&…

【PCIE】PCIE的驱动和pcie的端口驱动关系

pice驱动和pcie端口驱动区别 PCIe的端口服务驱动与PCIe驱动之间存在一定的关系&#xff0c;但它们是不同的概念。 PCIe驱动是用于管理和操作PCIe设备的驱动程序。它负责与硬件进行通信&#xff0c;并实现对PCIe设备的配置、数据传输以及其他相关操作。PCIe驱动通常涉及设备的…

【NLP概念源和流】 05-引进LSTM网络(第 5/20 部分)

一、说明 在上一篇博客中,我们讨论了原版RNN架构,也讨论了它的局限性。梯度消失是一个非常重要的缺点,它限制了RNN对较短序列的建模。香草 RNN 在相关输入事件和目标信号之间存在超过 5-10 个离散时间步长的时间滞时无法学习。这基本上限制了香草RNN在许多实际问题上的应用,…

NestJs Debug配置文件

&#xff08;事缓则圆,人缓则安,语迟则贵,虎行似病,鹰立似睡。清俞万春《荡寇志》&#xff09; {"version": "0.2.0","configurations": [{"type": "node","request": "launch","name": &quo…

基于LNMP架构搭建Discuz论坛

LNMP: L---->linux系统&#xff0c;操作系统。 N----->nginx网站服务&#xff08;前端),提供前端的静态页面服务。同时具有代理、转发的作用。&#xff08;转发就是转发后端请求&#xff0c;转发PHP&#xff09;&#xff0c;nginx没有处理动态资源的功能&#xff0c;他有…