当前位置: 首页 > news >正文

leetcode 210.课程表II

思路:拓补排序

其实就是对于第一个题的问题变了一个问法,上一个题本质上是求有没有环,这道题本质上就是让你求出来符合没有环的路径输出而已,本质上没有什么区别。

不同就在于这里需要你额外开一个数组用来存储你遍历这个有向图的路径。

注意:并不是说存储返回就完事了,因为所给的数据有可能是不构成拓补排序的要求的,我们需要判断一下这个图是不是有向无环图,如果是,那么拓补排序是可以的;不是的话,我们在存储路径的时候会重复一个环的点,导致输出错误。

这里的判断有没有环其实就是用一个计数器判断是不是符合全部点都遍历,不出现重复的情况下。

上代码:

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>>s(numCourses);vector<int>counts(numCourses,0);for(int i=0;i<prerequisites.size();i++){s[prerequisites[i][1]].push_back(prerequisites[i][0]);counts[prerequisites[i][0]]++;}queue<int>q;vector<int>res;int cnt=0;for(int i=0;i<numCourses;i++){if(counts[i]==0){q.push(i);res.push_back(i);}}while(!q.empty()){int tmp=q.front();q.pop();++cnt;for(int i:s[tmp]){if(--counts[i]==0){q.push(i);res.push_back(i);}}}if(cnt==numCourses){return res;}else{return {};}}
};

相关文章:

leetcode 210.课程表II

思路&#xff1a;拓补排序 其实就是对于第一个题的问题变了一个问法&#xff0c;上一个题本质上是求有没有环&#xff0c;这道题本质上就是让你求出来符合没有环的路径输出而已&#xff0c;本质上没有什么区别。 不同就在于这里需要你额外开一个数组用来存储你遍历这个有向图…...

SpringBootTest测试框架五

示例 package com.xxx;import com.xxx.ut.AbstractBasicTest; import com.xxx.ut.uttool.TestModel; import...

赛事|基于SprinBoot+vue的CSGO赛事管理系统(源码+数据库+文档)

CSGO赛事管理系统 目录 基于SprinBootvue的CSGO赛事管理系统 一、前言 二、系统设计 三、系统功能设计 1系统功能模块 2管理员功能模块 3参赛战队功能模块 4合作方功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&…...

线性化技巧:绝对值变量的线性化

文章目录 1. 问题2. 线性化3. 缺少 x i x i − 0 x_i^ \times x_i^- 0 xi​xi−​0 有什么问题4. 延伸思考5. 参考文献 1. 问题 以方述诚老师课件中的案例为例&#xff1a; m a x 3 x 1 − 2 x 2 − 4 ∣ x 3 ∣ s . t . − x 1 2 x 2 ≤ − 5 3 x 2 − x 3 ≥ 6 2 x 1 …...

List基本使用(C++)

目录 1.list的介绍 2.list的使用 list的构造 list的size() 和 max_size() list遍历操作 list元素修改操作 assign()函数 push_front(),push_back 头插&#xff0c;尾插 pop_front() pop_back 头删尾删 insert()函数 swap()函数 resize()函数 clear()函数 list类数…...

ELK 日志监控平台(一)- 快速搭建

文章目录 ELK 日志监控平台&#xff08;一&#xff09;- 快速搭建1.ELK 简介2.Elasticsearch安装部署3.Logstash安装部署4.Kibana安装部署5.日志收集DEMO5.1.创建SpringBoot应用依赖导入日志配置文件 logback.xml启动类目录结构启动项目 5.2.创建Logstash配置文件5.3.重新启动L…...

工作中写单片机代码,与学校里有什么不同?

来聊聊我的经历&#xff0c;提供几个提升方向&#xff0c;亲测有效&#xff0c;希望能让你少走几年弯路。 10几年前&#xff0c;还没参加工作的时候&#xff0c;主要是玩玩开发板&#xff0c;也接触不到实际产品的代码&#xff0c;很好奇那些产品级的代码是怎样的。 第一份工作…...

Unity LayerMask避坑笔记

今天使用Physics2D.OverlapAreaNonAlloc进行物理检测时候&#xff0c;通过LayerMask.NameToLayer传入了int值的LayerMask&#xff0c;结果一直识别不到&#xff0c;经过Debug才找到问题&#xff0c;竟是LayerMask的“值”传输有问题&#xff0c;记录一下。 直接贴代码输出结果&…...

(原创)从右到左排列RecycleView的数据

问题的提出 当我们写一个Recycleview时&#xff0c;默认的效果大概是这样的&#xff1a; 当然&#xff0c;我们也可以用表格布局管理器GridLayoutManager做成这样&#xff1a; 可以看到&#xff0c;默认的绘制方向是&#xff1a; 从左到右&#xff0c;从上到下 那么问题来了…...

【C语言】数据指针地址的取值、赋值、自增操作避坑

【C语言】数据指针的取值、赋值、自增操作避坑 文章目录 指针地址指针自增指针取值、赋值附录&#xff1a;压缩字符串、大小端格式转换压缩字符串浮点数压缩Packed-ASCII字符串 大小端转换什么是大端和小端数据传输中的大小端总结大小端转换函数 指针地址 请看下列代码&#…...

Java进阶-SpringCloud使用BeanUtil工具类简化对象之间的属性复制和操作

在Java编程中&#xff0c;BeanUtil工具类是一种强大且便捷的工具&#xff0c;用于简化对象之间的属性复制和操作。本文将介绍BeanUtil的基本功能&#xff0c;通过详细的代码示例展示其应用&#xff0c;并与其他类似工具进行对比。本文还将探讨BeanUtil在实际开发中的优势和使用…...

【ES6】ECMAS6新特性概览(一):变量声明let与const、箭头函数、模板字面量全面解析

&#x1f525; 个人主页&#xff1a;空白诗 &#x1f525; 热门专栏&#xff1a;【JavaScript】 文章目录 &#x1f33f; 引言一、 let 和 const - 变量声明的新方式 &#x1f31f;&#x1f4cc; var的问题回顾&#x1f4cc; let的革新&#x1f4cc; const的不变之美 二、 Arro…...

刷题之从前序遍历与中序遍历序列构造二叉树(leetcode)

从前序遍历与中序遍历序列构造二叉树 前序遍历&#xff1a;中左右 中序遍历&#xff1a;左中右 前序遍历的第一个数必定为根节点&#xff0c;再到中序遍历中找到该数&#xff0c;数的左边是左子树&#xff0c;右边是右子树&#xff0c;进行递归即可。 #include<vector>…...

微信小程序--微信开发者工具使用小技巧(3)

一、微信开发者工具使用小技巧 1、快速创建小程序页面 在app.json中的pages配置项&#xff0c;把需要创建的页面填写上去 2、快捷键使用 进入方式 1&#xff1a; 文件–>首选项–> keyboard shortcuts 进入快捷键查看与设置 进入方式 2&#xff1a; 设置–>快捷键…...

JDBC的 PreparedStatement 的用法和解释

文章目录 前言1、封装数据库连接和关闭操作数据库配置文件 config.properties 2、批量添加操作3、查询操作4、修改和删除操作总结 前言 PreparedStatement是预编译的,对于批量处理可以大大提高效率. 也叫JDBC存储过程 1、封装数据库连接和关闭操作 package org.springblade.m…...

LeetCode 面试150

最近准备面试&#xff0c;我以前不愿意面对的 现在保持一颗本心&#xff0c;就是专注于算法思想&#xff0c;语言基础的磨炼&#xff1b; 不为速成&#xff0c;不急功近利的想要比赛&#xff0c;或者为了面试。 单纯的本心&#xff0c;体验算法带来的快乐&#xff0c;是一件非常…...

xmake+xrepo自建仓库添加交叉编译工具链

xmakexrepo自建仓库添加交叉编译工具链 最近想将交叉编译工具链放到xrepo自建仓库中&#xff0c;在xmake中引用&#xff0c;方便多个电脑快速实现交叉编译。 xmake官方文档感觉不够详细&#xff0c;折腾了好久&#xff0c;这里做个记录。 基本步骤如下&#xff1a; 添加自建…...

论文阅读》学习了解自己:一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023

《论文阅读》学习了解自己&#xff1a;一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023 前言 简介研究现状任务定义模型架构Learning to know myselfLearning to avoid Misidentification损失函数实验结果消融实验 前言 亲身阅读感受分享&#xff0c;细节画图解释…...

[Java EE] 网络编程与通信原理(三):网络编程Socket套接字(TCP协议)

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …...

MyBatis懒加载数据(大批量数据处理)

使用范例 Cursor约定使用Iterator去懒加载数据&#xff0c;以时间换空间&#xff0c;非常适合处理通常无法容纳在内存中的数百万个项目查询。如果在 resultMap 中使用集合&#xff0c;则必须使用 resultMap 的 id 列对游标 SQL 查询进行排序(resultOrdered“true”)。 //为了避…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...