【LeetCode】【算法】209. 课程表

LeetCode 209. 课程表

题目描述

你这个学期必须选修numCourses门课程,记为0到numCourses- 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出,其中 prerequisites[i] = [a_i,b_i] ,表示如果要学习课程a_i则必须先学习课程b_i。
例如,先修课程对[0, 1]表示:想要学习课程0,你需要先完成课程1。
请你判断是否可能完成所有课程的学习?如果可以,返回true;否则,返回false。

思路

这是一个经典的拓扑排序问题,什么是拓扑排序问题?我理解就是需要判断先完成什么事儿再完成什么事儿的那种问题
可以考虑通过建立一个图,对于入度为0的图先开始做搜索,看最后能不能把所有的图节点遍历掉。
第一步:根据给定的prerequisites建立一个类型为List<List<Integer>>edges的列表,其中下标i表示第i门课程,List<Integer>则表示第i门课程的后置课程;同时还有一个indeg=new int[numCourses]数组,该数组中记录每门课程有多少门前置课程
第二步:建立队列,遍历indeg数组,寻找那些前置课程门数为0的课程,并入队到队列尾
第三步:建立一个visited变量存储学习的课程数量,while(队列不为空时)

  • ①出队首元素;
  • ②学习课程数+1;
  • ③通过上面的第一步的List<List<Integer>> edges获得该门课程的所有后置课程,遍历里边的元素for (int v:edges.get(u))对于里面的元素执行:
    --indeg[v];因为该门课程的前置课程数量-1
    if (indeg[v]==0)说明该元素此时入度为0(没有前置课程了),入队到队列尾

第四步:返回visited == numCourses,就知道能否学完所有课程了

代码

class Solution {List<List<Integer>> edges;int[] indeg;public boolean canFinish(int numCourses, int[][] prerequisites) {// 建立图以后做搜索edges = new ArrayList<>();for (int i = 0; i < numCourses; i++){edges.add(new ArrayList<>());}indeg = new int[numCourses];for (int[] prerequisite : prerequisites) {edges.get(prerequisite[1]).add(prerequisite[0]);++indeg[prerequisite[0]]; // 记录这个位置有几个子节点,便于后续做广度优先搜索 -> 但是真的有必要吗?edges[prerequisite[0]]的长度不行吗}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (indeg[i] == 0){ // 找到入度为0的节点开始广度优先搜索queue.offer(i);}}int visited = 0;while (!queue.isEmpty()){++visited;int u = queue.poll(); // 出队for (int v: edges.get(u)){ // 广度优先搜索,里面的内容入队--indeg[v];if (indeg[v] == 0){ // 直到这个节点不再被其他节点所指,才能入队继续遍历它下面的节点queue.offer(v);}}}return visited == numCourses;}
}

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

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

相关文章

[mysql]mysql的DML数据操作语言增删改,以及新特性计算列,阿里巴巴开发手册mysql相关

1DML数据操作语言,增加删除改数据 插入数据INSERT 插入添加数据,两种方法 方式1:VALUES添加数据 #准备工作 USE atguigudb; CREATE TABLE IF NOT EXISTS emp1( id INT, name VARCHAR(15), hire_data DATE, salary DOUBLE(10,2)); SELECT * FROM emp1 INSERT INTO em…

【华为云-云驻共创】UCS跨云多活容灾:让业务高可用不再是难题

【摘要】云原生应用深入到企业各个业务场景&#xff0c;云原生正在走向分布式化&#xff0c;跨云跨域统一协同治理&#xff0c;保证一致应用体验&#xff0c;这些新的需求日益凸显。而容灾是确保服务高可用的保障&#xff0c;但即使应用部署在云上&#xff0c;也无法避免市政方…

R语言生物群落(生态)数据统计分析与绘图丨tidyverse数据清洗、多元统计分析、随机森林、回归及混合效应模型、结构方程模型等

R 语言的开源、自由、免费等特点使其广泛应用于生物群落数据统计分析。生物群落数据多样而复杂&#xff0c;涉及众多统计分析方法。内容以生物群落数据分析中的最常用的统计方法回归和混合效应模型、多元统计分析技术及结构方程等数量分析方法为主线&#xff0c;通过多个来自经…

极简实现酷炫动效:Flutter隐式动画指南第二篇之一些酷炫的隐式动画效果

目录 前言 1.弹性放大按钮效果 2.旋转和缩放组合动画 3.颜色渐变背景动画 4.缩放进出效果 前言 在上一篇文章中&#xff0c;我们介绍了Flutter中的隐式动画的一些相关知识&#xff0c;在这篇文章中,我们可以结合多个隐式动画 Widget 在 Flutter 中创建一些酷炫的视觉效果&…

数字马力二面面试总结

24.03.07数字马力二面面试总结 前段时间找工作,做的一些面试笔记总结 大家有面试录音或者记录的也可以发给我,我来整理答案呀 数字马力二面面试总结 24.03.07数字马力二面面试总结你可以挑一个你的最有挑战性的,有难度的,最具有复杂性的项目,可以简单说一下。有没有和算…

C语言例题练手(1)

前几篇博客的内容已经涉及了C语言的部分语法知识&#xff0c;我们可以尝试做一些编程题&#xff0c;或者换一种说法就是可以写出什么样的程序以此来解决一些问题。 题目来自牛客网https://www.nowcoder.com和C语言菜鸟教程C 语言教程 | 菜鸟教程 数值计算 【例1】带余除法计…

大模型LLama3!!!Ollama下载、部署和应用(保姆级详细教程)

首先呢&#xff0c;大家在网站先下载ollama软件 这就和anaconda和python是一样的 废话不多说 直接上链接&#xff1a;Download Ollama on Windows 三个系统都支持 注意&#xff1a; 这里的Models&#xff0c;就是在上面&#xff0c;大家点开之后&#xff0c;里面有很多模型…

【359】基于springboot的智慧草莓基地管理系统

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本智慧草莓基地管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据…

MongoDB笔记03-MongoDB索引

文章目录 一、前言1.1 概述1.2 MongoDB索引使用B-Tree还是BTree&#xff1f;1.3 B 树和 B 树的对比1.4 总结 二、索引的类型2.1 单字段索引2.2 复合索引2.3 其他索引 三、索引的管理操作3.1 索引的查看3.2 索引的创建3.2.1 单字段索引3.2.2 复合索引 3.3 索引的移除3.3.1 指定索…

string模拟实现流插入(输出)+流提取(输入)

个人主页&#xff1a;Jason_from_China-CSDN博客 所属栏目&#xff1a;C系统性学习_Jason_from_China的博客-CSDN博客 所属栏目&#xff1a;C知识点的补充_Jason_from_China的博客-CSDN博客 string模拟实现clear 模拟实现clear的目的是在流提取的时候我们清空之前的数据&#x…

C++入门基础知识134—【关于C 库函数 - gmtime()】

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///C爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于C 库函数 - gmtime()的相关内容&#xf…

ERP学习笔记-预处理eeglab

第一步&#xff1a;数据格式转化 import data&#xff1a;读取收集到的原始数据文件.vhdr格式 读取后的样子&#xff1a; 将数据保存为.set文件 第二步&#xff1a;通道定位 读取.set文件 Channel locations部分为unknown&#xff0c;表明通道的坐标未知 增加默认的设置 Chan…

查缺补漏----用户上网过程(HTTP,DNS与ARP)

&#xff08;1&#xff09;HTTP 来自湖科大计算机网络微课堂&#xff1a; ① HTTP/1.0采用非持续连接方式。在该方式下&#xff0c;每次浏览器要请求一个文件都要与服务器建立TCP连接当收到响应后就立即关闭连接。 每请求一个文档就要有两倍的RTT的开销。若一个网页上有很多引…

谷歌推出全新AI生成游戏玩法 —— 无限生成角色生活模拟游戏“Unbounded”

随着人工智能技术的飞速发展,游戏行业正迎来前所未有的创新。近日,谷歌宣布了一款名为“Unbounded”的新型游戏,这是一款基于生成式AI技术的角色生命模拟游戏,它将为玩家带来前所未有的开放性和互动性体验。 项目概览 项目名称:Unbounded类型:生成式无限游戏(Generati…

论文阅读:DynamicDet: A Unified Dynamic Architecture for Object Detection

论文地址&#xff1a;[2304.05552] DynamicDet: A Unified Dynamic Architecture for Object Detection 代码地址&#xff1a;GitHub - VDIGPKU/DynamicDet: [CVPR 2023] DynamicDet: A Unified Dynamic Architecture for Object Detection 概要 本文提出了一种名为 DynamicD…

关于在GitLab的CI/CD中用docker buildx本地化多架构打包dotnet应用的问题

关于在GitLab的CI/CD中用docker buildx本地化多架构打包dotnet应用的问题 这是一个DevOps综合性问题docker buildx多架构打包.NET应用的问题用QEMU模拟多架构环境打包 这是一个DevOps综合性问题 网络上的方案都是细分的领域&#xff0c;未见一个集成了GitLabdockerdotnet的多架…

翻译工具开发技术笔记:《老挝语翻译通》app支持语音识别翻译功能,怎么提高语音识别的准确度呢?

《老挝语翻译通》app是一款专为老挝语翻译设计的免费工具&#xff0c;支持文本翻译、老挝文OCR文字识别提取、文字转语音。这款工具以其技术优势和用户友好的界面&#xff0c;为用户提供了便捷的老挝语翻译体验。 技术特点 文本翻译&#xff1a;支持双语输入&#xff0c;提供精…

qt QListView详解

1、概述 QListView 是 Qt 框架中的一个视图类&#xff0c;用于展示模型中的数据。它基于 QAbstractItemView&#xff0c;支持多种视图模式&#xff0c;如列表视图&#xff08;List View&#xff09;、图标视图&#xff08;Icon View&#xff09;等。QListView 是模型/视图框架…

初识C++(上) -- C++的关键字、命名空间、缺省参数以及函数的重载

目录 一、C的关键字&#xff08;C98&#xff09; 二、命名空间 1、命名冲突 2、命名空间 2.1 命名空间的定义 (1). 命名空间定义的例子以及命名空间的嵌套&#xff1a; (2). 同一个工程中允许存在多个相同名称的命名空间,编译器最后会合成同一个命名空间中&#xff1a; 2…

MySQL_客户端工具建库.

前言&#xff1a; 通过前面的学习我们已经了解到什么是数据库&#xff0c;以及数据库是如何安装的&#xff0c;相信大家都已将数据库安装好了&#xff0c;让我们接下来开始新的学习吧&#xff01;&#xff01;&#xff01; 1.MySQL客户端工具 1. MySQL Workbench MySQL :: D…