LeetCode 热题 100 | 图论(二)

目录

1  基础知识

1.1  什么是拓扑排序

1.2  如何进行拓扑排序

1.3  拓扑排序举例

2  207. 课程表

3  210. 课程表 II


菜鸟做题,语言是 C++

1  基础知识

1.1  什么是拓扑排序

含义:根据节点之间的依赖关系来生成一个有序的序列。

应用:

  • 在项目管理中,按照任务之间的的依赖关系来安排执行顺序。
  • 在编译原理中,按照编译单元的依赖关系来确定编译单元的生成顺序。
  • 在程序设计中,按照模块之间的依赖关系来确定模块的加载和执行顺序。

突然想起来好像在操作系统原理里学过!

1.2  如何进行拓扑排序

排序步骤:

  1. 选择入度为 0 的节点加入到排序结果中,并从图中移除该节点以及它的所有出边;
  2. 重复步骤 1,每次都选择入度为 0 的节点加入到排序结果中,并更新图中剩余节点的入度;
  3. 重复步骤 1 和 2,直到所有的节点都被加入到排序结果中,或者不再存在入度为 0 的节点。

名词解释:

  • → 节点  属于节点的 入边
  • 节点 →  属于节点的 出边

如果图中不再存在入度为 0 的节点,且并非所有的节点都被加入到排序结果中,那么说明原图中存在环。综上,拓扑排序的主要功能是帮助安排顺序,顺带帮助检测图中有没有环。

1.3  拓扑排序举例

下图描述了一个拓扑排序过程。

① 入度为 0 的节点有 B、D,我们任意选择 B,并删除它的出边:

② 入度为 0 的节点有 A、D,我们任意选择 A,并删除它的出边;更新后,入度为 0 的节点有 C、D,我们任意选择 C,并删除它的出边:

③ 入度为 0 的节点有 D,我们选择 D,并删除它的出边;更新后,入度为 0 的节点有 F,我们选择 F,并删除它的出边:

以此类推,不再赘述。通过 “任意选择” 一词可以看出,拓扑排序的结果不止一种。

2  207. 课程表

感觉解题方法和拓扑排序关系不大,更多的是从题意出发;想了很久要怎么才能把思路表述清楚,最终认为还是看代码来得快 TT

解题思路:假设有先修课程对 [0,1] 和 [0,2]

  • 初始化:获取每门课程的先修课程数组,比如:0 对应 [1,2]
  • 初始化:设置记录访问状态的数组,并将访问状态全部置为 0
  • 循环:访问每门课程,判断它的先修课程是否已经被全部修完
  • 如果它的先修课程未被全部修完,则表明无法完成所有课程的学习

访问状态:

  • visited[course] = 0:该门课程还未被学习
  • visited[course] = 1:该门课程正在被学习
  • visited[course] = 2:该门课程已经被学习

针对 “该门课程正在被学习” 的说法,需要说明的是,这是算法题而不是现实生活!如果一门课正在被学习,不是代表学习它需要一段时间,而是代表它的先修课程不可能被修完,导致我们永远学不了它。

class Solution {
public:vector<int> visited;vector<vector<int>> mustFinish;bool possible = true;void helper(int course) {// 指明该门课程正在被学习visited[course] = 1;// 判断其先修课程是否已被修完for (auto & preCourse : mustFinish[course]) {// 递归访问未被学习的先修课程if (visited[preCourse] == 0) {helper(preCourse);if (!possible) return;// 先修课程正在被学习(因为卡住了)} else if (visited[preCourse] == 1) {possible = false;return;}}// 指明该门课程已经被学习visited[course] = 2;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {visited.resize(numCourses);mustFinish.resize(numCourses);// 获取每门课程的先修课程数组for (auto & p : prerequisites) {mustFinish[p[0]].push_back(p[1]);}// 循环访问每门课程for (int i = 0; i < numCourses && possible; ++i) {helper(i);}return possible;}
};

3  210. 课程表 II

在  207. 课程表  的基础上,增加一个数据结构来存储课程顺序即可。

唯一区别在于:

for (int i = 0; i < numCourses && possible && !visited[i]; ++i)

新增条件 !visited[i],不允许已经被访问过的课程再被访问,避免了课程重复被学习。

class Solution {
public:vector<int> visited;vector<vector<int>> mustFinish;bool possible = true;vector<int> ans;void helper(int course) {visited[course] = 1;for (auto & preCourse : mustFinish[course]) {if (visited[preCourse] == 0) {helper(preCourse);if (!possible) return;} else if (visited[preCourse] == 1) {possible = false;return;}}visited[course] = 2;ans.push_back(course);}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {visited.resize(numCourses);mustFinish.resize(numCourses);for (auto & p : prerequisites) {mustFinish[p[0]].push_back(p[1]);}for (int i = 0; i < numCourses && possible && !visited[i]; ++i) {helper(i);}if (possible) return ans;return {};}
};

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

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

相关文章

Mybatis实现分页查询数据(代码实操讲解)

在MyBatis中实现分页查询的常见方式有两种&#xff1a;使用MyBatis内置的分页插件如PageHelper&#xff0c;或者手动编写分页的SQL语句。下面我将为你提供两种方式的示例代码。 使用PageHelper分页插件 首先&#xff0c;确保你的项目中已经添加了PageHelper的依赖。在Maven项…

gpt批量工具,gpt批量生成文章工具

GPT批量工具在今天的数字化时代扮演着越来越重要的角色&#xff0c;它们通过人工智能技术&#xff0c;可以自动批量生成各种类型的文章&#xff0c;为用户提供了便利和效率。本文将介绍5款不同的GPT批量工具&#xff0c;并介绍一款知名的147GPT生成工具&#xff0c;以及另外一款…

js SheetJS 合并表格导出到同一个excel中

最近有个需求,我在一个页面显示了4个表格, 然后合并导出到excel文件中 四个表,四个sheet,一个excel文件 最后导出时这样: 实现: 1,页面有个导出的checkbox,勾选则导出,不勾选不处理 2,在一个函数中,集中处理四个表数据获取,并将结果返回出来 //获取数据后返回为…

代码随想录算法训练营第三十四天| 860.柠檬水找零 、406.根据身高重建队列 、452. 用最少数量的箭引爆气球

文章目录 1.柠檬水找零2.根据身高重建队列3.用最少数量的箭引爆气球 1.柠檬水找零 在柠檬水摊上&#xff0c;每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品&#xff0c;&#xff08;按账单 bills 支付的顺序&#xff09;一次购买一杯。 每位顾客只买一杯柠檬水&#xf…

(四)关系模型之关系代数

4.1关系代数概述 基于集合&#xff0c;提供了一系列的关系代数操作&#xff1a;并、差、笛卡尔积(广义积)、 选择、投影和更名等基本操作以及交、 连接和关系除等扩展操作&#xff0c;是一种集合思维的操作语言。关系代数操作以一个或多个关系为输入&#xff0c;结果是一个新的…

食品加工生产污废水处理如何达标排放

食品加工行业作为一个重要的工业部门&#xff0c;在生产过程中产生大量的污废水。合理、高效地处理这些污废水&#xff0c;实现达标排放&#xff0c;是保护环境和促进可持续发展的重要举措。本文将探讨食品加工生产污废水处理的方法和措施&#xff0c;以达到达标排放的目标。 首…

FreeRTOS操作系统学习——内存管理

C库函数与FreeRTOS内存管理区别 在C语言的库函数中&#xff0c;有mallc、free等函数可以申请以及释放内存空间&#xff0c;那么这为什么不适用于FreeRTOS的内存管理呢&#xff1f; 不适合用在资源紧缺的嵌入式系统中这些函数的实现过于复杂、占据的代码空间太大并非线程安全的…

小黑长沙特种兵归来,身体比较虚弱的js逆向烧脑之路:招标网搜索数据获取

通过有道翻译逆向的初步尝试&#xff0c;这次尝试一下招标网的数据获取感觉轻松了许多!!加油小黑黑 寻找接口地址(通过响应部分&#xff0c;推断出该部分为搜索数据获取接口) 复制curl&#xff0c;构造Python请求信息 进入https://curlconverter.com/python/&#xff0c;通过c…

HarmonyOS创建项目和应用—设置数据处理位置

项目和应用介绍 关于项目 项目是资源、应用的组织实体。资源包括服务器、数据库、存储&#xff0c;以及您的应用、终端用户的数据等。在您使用部分服务时&#xff0c;您是数据的控制者&#xff0c;数据将按照您设置的数据处理位置来存储在指定区域。 通常&#xff0c;您不需…

HTTPS如何保证数据传输的安全性 以及CA签发证书验签

暴力输出&#xff1a; 越看会越深入&#xff0c;睡前难以想通&#xff0c;后深入研究。得之。 有问题 请留言。 ----------追求内心的富足与平和。日行一善。 亓苏姑娘

停止Tomcat服务的方式

运行脚本文件停止 运行Tomcat的bin目录中提供的停止服务的脚本文件 关闭命令 # sh方式 sh shutdown.sh# ./方式 ./shutdown.sh操作步骤 运行结束进程停止 查看Tomcat进程&#xff0c;获得进程id kill进程命令 # 执行命令结束进程 kill -9 65358 操作步骤 注意 kill命令是…

相机类型的分辨率长宽、靶面尺寸大小、像元大小汇总

镜头的靶面尺寸大于等于相机靶面尺寸。 相机的芯片长这样&#xff0c;绿色反光部分&#xff08;我的手忽略&#xff09;&#xff1a; 基本所有像素的相机的靶面大小都可以在这个表格里面找到。 镜头的靶面尺寸在镜头外表上可以找到&#xff0c;选型很重要&#xff01;

如何在2.2.1版Aduino IDE中开发ESP32

ESP32芯片集成了WIFI和蓝牙&#xff0c;而且关于生态也很不错&#xff0c;越来越多的学习者和开发者选择此类芯片&#xff0c;而不像用keil开发STM32或者51一样&#xff0c;ESP32虽然也有官方的ESP32-IDF开发软甲&#xff0c;但是经过我个人的实操体验&#xff0c;不适合小白或…

Blender和3ds Max哪个会是行业未来?

Blender和3ds Max都是很强大的三维建模和渲染软件&#xff0c;各有各的好处。选择哪个软件更好&#xff0c;要看你的需求、预算、技术水平以及行业趋势等因素。 Blender最大的优点是免费且开源&#xff0c;这对预算有限的个人和小团队来说很有吸引力。它有很多建模工具和功能&…

Unity编辑器功能Inspector快捷自动填充数据和可视化调试

我们有时候可能需要在面板增加一些引用&#xff0c;可能添加脚本后要手动拖动&#xff0c;这样如果有大量的脚本拖动也是不小的工作量 实例 例如&#xff1a;我的脚本需要添加一个Bone的列表&#xff0c;一个个拖动很麻烦。 实现脚本 我们可以用这样的脚本来实现。 public…

GFP-GAN环境搭建推理测试

引子 近期&#xff0c;文生图&#xff0c;wav2lip很火&#xff0c;文生图&#xff0c;见识的太多&#xff0c;不多说了。wav2lip其通过语音驱动唇部动作并对视频质量进行修复&#xff0c;里面一般涉及到三个步骤&#xff0c;文本到语音转化&#xff0c;语音驱动唇部动作&#…

[XJTU-SY-BD]基础03 - 包络谱生成

1.分析结果 包络图是第三行。第一行水平时域信号&#xff0c;第二行垂直时域信号&#xff0c;第三行对第1行信号在故障频点包络计算后的结果。 上方是最终的视图。右下角我把光标对准了低频位置的那个故障峰&#xff0c;与理论值是一致的. 2.源码 2.1 测试例程源码 import …

Nature 研究亮点(Volume 626 Issue 8001, 29 February 2024)

文章目录 激光雕刻肥皂膜卵细胞的回收系统巴斯克语的起源产后抑郁症的治疗 激光雕刻肥皂膜 研究者&#xff1a;Haitao Xu 和 Yu Zhao&#xff0c;清华大学&#xff0c;北京。 发现&#xff1a;在特定条件下&#xff0c;可以使用激光在肥皂膜上进行雕刻。肥皂膜由洗涤剂分子&am…

护眼灯哪个牌子好?热门护眼台灯测评对比:明基/书客/柏曼,速度戳进来了解!

近年来&#xff0c;市场上出现了大量新型护眼台灯&#xff0c;让消费者在面对众多选择时感到困惑。在选购护眼台灯的时候&#xff0c;我们需要谨慎考虑&#xff0c;有些护眼台灯因为不合格&#xff0c;在使用过程中发热可能会产生有毒物质&#xff0c;对健康造成不良影响。那么…

Nginx使用—http基础知识

web访问流程 当我们在客户端通过浏览器输入网址的时候&#xff0c;这时候是访问不到服务器的&#xff0c; 先会去找到DNS解析服务器&#xff0c;DNS解析服务器返回IP地址&#xff0c; 客户端通过http协议向服务端发送请求&#xff0c;服务器响应请求并返回对应的资源给客户端&a…