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
思路:拓补排序 其实就是对于第一个题的问题变了一个问法,上一个题本质上是求有没有环,这道题本质上就是让你求出来符合没有环的路径输出而已,本质上没有什么区别。 不同就在于这里需要你额外开一个数组用来存储你遍历这个有向图…...
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 xixi−0 有什么问题4. 延伸思考5. 参考文献 1. 问题 以方述诚老师课件中的案例为例: 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 头插,尾插 pop_front() pop_back 头删尾删 insert()函数 swap()函数 resize()函数 clear()函数 list类数…...
ELK 日志监控平台(一)- 快速搭建
文章目录 ELK 日志监控平台(一)- 快速搭建1.ELK 简介2.Elasticsearch安装部署3.Logstash安装部署4.Kibana安装部署5.日志收集DEMO5.1.创建SpringBoot应用依赖导入日志配置文件 logback.xml启动类目录结构启动项目 5.2.创建Logstash配置文件5.3.重新启动L…...
工作中写单片机代码,与学校里有什么不同?
来聊聊我的经历,提供几个提升方向,亲测有效,希望能让你少走几年弯路。 10几年前,还没参加工作的时候,主要是玩玩开发板,也接触不到实际产品的代码,很好奇那些产品级的代码是怎样的。 第一份工作…...
Unity LayerMask避坑笔记
今天使用Physics2D.OverlapAreaNonAlloc进行物理检测时候,通过LayerMask.NameToLayer传入了int值的LayerMask,结果一直识别不到,经过Debug才找到问题,竟是LayerMask的“值”传输有问题,记录一下。 直接贴代码输出结果&…...
(原创)从右到左排列RecycleView的数据
问题的提出 当我们写一个Recycleview时,默认的效果大概是这样的: 当然,我们也可以用表格布局管理器GridLayoutManager做成这样: 可以看到,默认的绘制方向是: 从左到右,从上到下 那么问题来了…...
【C语言】数据指针地址的取值、赋值、自增操作避坑
【C语言】数据指针的取值、赋值、自增操作避坑 文章目录 指针地址指针自增指针取值、赋值附录:压缩字符串、大小端格式转换压缩字符串浮点数压缩Packed-ASCII字符串 大小端转换什么是大端和小端数据传输中的大小端总结大小端转换函数 指针地址 请看下列代码&#…...
Java进阶-SpringCloud使用BeanUtil工具类简化对象之间的属性复制和操作
在Java编程中,BeanUtil工具类是一种强大且便捷的工具,用于简化对象之间的属性复制和操作。本文将介绍BeanUtil的基本功能,通过详细的代码示例展示其应用,并与其他类似工具进行对比。本文还将探讨BeanUtil在实际开发中的优势和使用…...
【ES6】ECMAS6新特性概览(一):变量声明let与const、箭头函数、模板字面量全面解析
🔥 个人主页:空白诗 🔥 热门专栏:【JavaScript】 文章目录 🌿 引言一、 let 和 const - 变量声明的新方式 🌟📌 var的问题回顾📌 let的革新📌 const的不变之美 二、 Arro…...
刷题之从前序遍历与中序遍历序列构造二叉树(leetcode)
从前序遍历与中序遍历序列构造二叉树 前序遍历:中左右 中序遍历:左中右 前序遍历的第一个数必定为根节点,再到中序遍历中找到该数,数的左边是左子树,右边是右子树,进行递归即可。 #include<vector>…...
微信小程序--微信开发者工具使用小技巧(3)
一、微信开发者工具使用小技巧 1、快速创建小程序页面 在app.json中的pages配置项,把需要创建的页面填写上去 2、快捷键使用 进入方式 1: 文件–>首选项–> keyboard shortcuts 进入快捷键查看与设置 进入方式 2: 设置–>快捷键…...
JDBC的 PreparedStatement 的用法和解释
文章目录 前言1、封装数据库连接和关闭操作数据库配置文件 config.properties 2、批量添加操作3、查询操作4、修改和删除操作总结 前言 PreparedStatement是预编译的,对于批量处理可以大大提高效率. 也叫JDBC存储过程 1、封装数据库连接和关闭操作 package org.springblade.m…...
LeetCode 面试150
最近准备面试,我以前不愿意面对的 现在保持一颗本心,就是专注于算法思想,语言基础的磨炼; 不为速成,不急功近利的想要比赛,或者为了面试。 单纯的本心,体验算法带来的快乐,是一件非常…...
xmake+xrepo自建仓库添加交叉编译工具链
xmakexrepo自建仓库添加交叉编译工具链 最近想将交叉编译工具链放到xrepo自建仓库中,在xmake中引用,方便多个电脑快速实现交叉编译。 xmake官方文档感觉不够详细,折腾了好久,这里做个记录。 基本步骤如下: 添加自建…...
论文阅读》学习了解自己:一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023
《论文阅读》学习了解自己:一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023 前言 简介研究现状任务定义模型架构Learning to know myselfLearning to avoid Misidentification损失函数实验结果消融实验 前言 亲身阅读感受分享,细节画图解释…...
[Java EE] 网络编程与通信原理(三):网络编程Socket套接字(TCP协议)
🌸个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 🏵️热门专栏:🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 🧀Java …...
MyBatis懒加载数据(大批量数据处理)
使用范例 Cursor约定使用Iterator去懒加载数据,以时间换空间,非常适合处理通常无法容纳在内存中的数百万个项目查询。如果在 resultMap 中使用集合,则必须使用 resultMap 的 id 列对游标 SQL 查询进行排序(resultOrdered“true”)。 //为了避…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
