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

【LeetCode 算法】Parallel Courses III 并行课程 III-拓扑

文章目录

  • Parallel Courses III 并行课程 III

Parallel Courses III 并行课程 III

问题描述:

给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 r e l a t i o n s [ j ] = [ p r e v C o u r s e j , n e x t C o u r s e j ] relations[j] = [prevCourse_j, nextCourse_j] relations[j]=[prevCoursej,nextCoursej] ,表示课程 p r e v C o u r s e j prevCourse_j prevCoursej 必须在课程 n e x t C o u r s e j nextCourse_j nextCoursej 之前 完成(先修课的关系)。同时给你一个下标从 0 开始的整数数组 time ,其中 t i m e [ i ] time[i] time[i] 表示完成第 ( i + 1 ) (i+1) (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数:

如果一门课的所有先修课都已经完成,你可以在 任意 时间开始这门课程。
你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。

注意:测试数据保证一定可以完成所有课程(也就是先修课的关系构成一个有向无环图)。

1 < = n < = 5 ∗ 1 0 4 0 < = r e l a t i o n s . l e n g t h < = m i n ( n ∗ ( n − 1 ) / 2 , 5 ∗ 1 0 4 ) r e l a t i o n s [ j ] . l e n g t h = = 2 1 < = p r e v C o u r s e j , n e x t C o u r s e j < = n p r e v C o u r s e j ! = n e x t C o u r s e j 所有的先修课程对 [ p r e v C o u r s e j , n e x t C o u r s e j ] 都是互不相同的。 t i m e . l e n g t h = = n 1 < = t i m e [ i ] < = 1 0 4 先修课程图是一个有向无环图 1 <= n <= 5 * 10^4\\ 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)\\ relations[j].length == 2\\ 1 <= prevCourse_j, nextCourse_j <= n\\ prevCourse_j != nextCourse_j\\ 所有的先修课程对 [prevCourse_j, nextCourse_j] 都是 互不相同 的。\\ time.length == n\\ 1 <= time[i] <= 10^4\\ 先修课程图是一个有向无环图 1<=n<=51040<=relations.length<=min(n(n1)/2,5104)relations[j].length==21<=prevCoursej,nextCoursej<=nprevCoursej!=nextCoursej所有的先修课程对[prevCoursej,nextCoursej]都是互不相同的。time.length==n1<=time[i]<=104先修课程图是一个有向无环图

分析

该问题的复杂性并不大,是最简单的拓扑问题

就是必须要有一个固定的顺序来依次的访问,每个课程。问题中也提到不会存在环,而且是一个有向无环图

同时可以同时学习多门课程,相比较之前的一个问题中,要求一个学期只能选k个课程,条件更加宽松。

所以按照拓扑排序的思路来处理,就是需要构建一个图,图无非就是邻接表或者是邻接矩阵。

但是由于问题的规模限制,邻接表是一个比较合适的选择。

然后进行拓扑排序,同时用 f [ i ] f[i] f[i] 记录到达课程i时的最晚时间,而目标是完成所有课程的时候,需要的最少时间,所以要用 a n s ans ans记录每个课程的最晚结束时间

时间复杂度 O ( M + N ) O(M+N) O(M+N)

空间复杂度 O ( M + N ) O(M+N) O(M+N)

代码

拓扑

class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] indeg = new int[n+1];List<Integer>[] g = new ArrayList[n+1];for(int i=1;i<=n;i++){g[i] = new ArrayList();}for(int[] re: relations){int from = re[0],to = re[1];indeg[to]++;g[from].add(to);} Queue<Integer> queue = new LinkedList();for(int i=1;i<=n;i++){if(indeg[i]>0) continue;queue.offer(i);}int[] f = new int[n+1];int ans =0;while(!queue.isEmpty()){int idx = queue.poll(); int end = f[idx]+ time[idx-1];ans = Math.max(ans,end);for(int nx: g[idx]){f[nx]= Math.max(f[nx],end);indeg[nx]--;if(indeg[nx]==0){queue.offer(nx);}}} return ans;}
}

时间复杂度 O ( M + N ) O(M+N) O(M+N)

空间复杂度 O ( M + N ) O(M+N) O(M+N)

Tag

Array

Graph

Topological Sort

相关文章:

【LeetCode 算法】Parallel Courses III 并行课程 III-拓扑

文章目录 Parallel Courses III 并行课程 III问题描述&#xff1a;分析代码拓扑 Tag Parallel Courses III 并行课程 III 问题描述&#xff1a; 给你一个整数 n &#xff0c;表示有 n 节课&#xff0c;课程编号从 1 到 n 。同时给你一个二维整数数组 relations &#xff0c;其…...

进行消息撤回功能的测试时,需要考虑哪些?

进行消息撤回功能的测试时&#xff0c;可以考虑以下测试点&#xff1a; 1. 功能可用性测试&#xff1a;确认消息撤回功能是否能够正常使用&#xff0c;并且在不同的场景下&#xff08;例如单聊、群聊&#xff09;是否表现一致。 2. 撤回时限测试&#xff1a;检查消息撤回的时…...

C语言动态内存管理(三)

目录 五、C/C程序的内存开辟1.图解2.关键点 六、柔性数组1.什么是柔性数组2.两种语法形式3.柔性数组的特点4.柔性数组的创建及使用在这个方案中柔性数组的柔性怎么体现出来的? 5.不用柔性数组&#xff0c;实现数组可大可小的思路6.对比 总结 五、C/C程序的内存开辟 1.图解 &a…...

通过cmake工程生成visual studio解决方案

1、前言 visual studio是一个很强大的开发工具&#xff0c;这个工具主要是通过解决方案对我们的源码进行编译等操作。但是我们很多时候拿到的可能并不是一个直接的解决方案&#xff0c;可能是是一个cmake工程&#xff0c;那么这个时候我们就需要通过cmake工程生成解决方案&…...

STM32CubeMX配置STM32G031多通道ADC + DMA采集(HAL库开发)

时钟配置HSI主频配置64M 勾选打开8个通道的ADC 使能连续转换模式 添加DMA DMA模式选择循环模式 使能DMA连续请求 采样时间配置160.5 转换次数为8 配置好8次转换的顺序 配置好串口&#xff0c;选择异步模式配置好需要的开发环境并获取代码 修改main.c 串口重定向 #include &…...

Vue入门项目——WebApi

Vue入门——WebApi vue3项目搭建组合式API响应式APIreactive()ref() 生命周期钩子computed计算属性函数watch监听函数父子通信模板引用组合选项 vue3项目搭建 简单看下Vue3的优势吧 下载安装npm及node.js16.0以上版本&#xff08;确保安装成功可用如下代码检查版本&#xff0…...

【电源专题】电量计参数RSOC/RM/FCC定义

在文章【电源芯片】电量计(Gauge)介绍中我们讲到电量计的功能就是监测电池、计量电量。 那么电量计其实也是有很多算法的,比如【电源专题】电量计估计电池荷电状态方法(开路电压法及库仑计法)的差别文章所说的开路电压法和库仑计法。当然还有如阻抗跟踪法、CEDV算法等。 …...

实际开发中,React应用常见问题【持续更新中】

实际开发中&#xff0c;React应用常见问题【持续更新中】 实际开发中&#xff0c;React应用常见问题【持续更新中】 一、路由相关 “react-router-dom”: “^6.14.2”, “react”: “^18.2.0”, 1、监听路由 import { useLocation } from react-router-domexport default func…...

HTML5前端开发工程师的岗位职责说明(合集)

HTML5前端开发工程师的岗位职责说明1 职责 1、根据产品设计文档和视觉文件&#xff0c;利用HTML5相关技术开发移动平台的web前端页面; 2、基于HTML5.0标准进行页面制作&#xff0c;编写可复用的用户界面组件; 3、持续的优化前端体验和页面响应速度&#xff0c;并保证兼容性和…...

Go编写服务监管程序

前言 程序的目的&#xff1a;一个基于Linux系统下的进程监控与管理工具&#xff0c;它能够监控指定的进程或服务的运行情况&#xff0c;并在发现它们不存在或出现异常时自动进行重启操作。这个程序就像一个可靠的看门狗&#xff0c;时刻守护着系统的稳定运行。 程序的本身是周期…...

API商品详情:详尽呈现产品信息的利器

API商品详情&#xff1a;详尽呈现产品信息的利器 随着电子商务的迅速发展&#xff0c;越来越多的企业和开发者开始关注和利用API来实现灵活、高效的商品展示和推广。而在这一领域中&#xff0c;API商品详情成为了无可替代的利器&#xff0c;为用户提供了极为详尽的产品信息。 …...

Cisco 路由器配置管理

大多数网络中断的最常见原因是错误的配置更改。对网络设备配置的每一次更改都伴随着造成网络中断、安全问题甚至性能下降的风险。计划外更改使网络容易受到意外中断的影响。 Network Configuration Manager 网络更改和配置管理 &#xff08;NCCM&#xff09;解决方案&#xff…...

java面试真题附参考答案【下册】

tips&#xff1a;下面简述题为java面试真题&#xff0c;阅读本文且感兴趣的&#xff0c;还有将要面试的小伙伴有条件的准备一下笔和纸&#xff0c;将之转述出来成为自己的知识&#xff0c;希望接下来的面试好运连连 上一册&#xff1a;java面试真题【上册】_CsDn.FF的博客-CSD…...

2023牛客多校第三场 B.Auspiciousness

传送门 前题提要:没得说,赛时根本没想到dp,赛后翻各大题解看了很久,终于懂了dp的做法,故准备写一篇题解. 首先,先定义一下我们的 d p dp dp方程,考虑将处于 [ 1 , n ] [1,n] [1,n]的数当做小数,将处于 [ n 1 , 2 ∗ n ] [n1,2*n] [n1,2∗n]的数当做大数.那么对于我们的摸牌结…...

Numpy—数组的分隔与转置

⛳数组的切分 split 分隔 numpy.split 函数沿特定 的轴将数组分割为子数组&#xff0c;格式如下&#xff1a; numpy.split(ary, indices_or_sections, axis)参数说明&#xff1a; arry&#xff1a;被分割的数组。indices_or_sections&#xff1a;如果是一个整数&#xff0c;就…...

PyTorch中级教程:深入理解自动求导和优化

在你已经掌握了如何使用PyTorch构建神经网络的基础上&#xff0c;接下来我们将深入探讨PyTorch的两个核心特性&#xff1a;自动求导&#xff08;Autograd&#xff09;和优化&#xff08;Optimization&#xff09;。这两个特性在深度学习模型的训练过程中起着至关重要的作用。 …...

ES6基础知识六:你是怎么理解ES6中 Promise的?使用场景?

一、介绍 Promise&#xff0c;译为承诺&#xff0c;是异步编程的一种解决方案&#xff0c;比传统的解决方案&#xff08;回调函数&#xff09;更加合理和更加强大 在以往我们如果处理多层异步操作&#xff0c;我们往往会像下面那样编写我们的代码 doSomething(function(resu…...

数据库CAST()函数,格式(CAST AS decimal)

语法&#xff1a; CAST (expression AS data_type) 参数说明&#xff1a; expression&#xff1a;任何有效的SQServer表达式。 AS&#xff1a;用于分隔两个参数&#xff0c;在AS之前的是要处理的数据&#xff0c;在AS之后是要转换的数据类型。 data_type&#xff1a;目标系统…...

LRU 缓存结构

文章目录 LRU实现 LRU 优先去除最久没有访问到的数据。 实现 通过组合哈希表&#xff08;Hash Table&#xff09;和双向链表&#xff08;Doubly Linked List&#xff09;实现 LRU 缓存。并且以 O(1) 的时间复杂度执行 get 和 put 操作核心是对节点的新增、访问都会让节点移动…...

DAY1,Qt [ 手动实现登录框(信息调试类,按钮类,行编辑器类,标签类的使用)]

1.手动实现登录框&#xff1b; ---mychat.h---头文件 #ifndef MYCHAT_H #define MYCHAT_H#include <QWidget> #include <QDebug> //打印信息 #include <QIcon> //图标 #include <QPushButton> //按钮 #include <QLineEdit> //行编辑器类 #in…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

Easy Excel

Easy Excel 一、依赖引入二、基本使用1. 定义实体类&#xff08;导入/导出共用&#xff09;2. 写 Excel3. 读 Excel 三、常用注解说明&#xff08;完整列表&#xff09;四、进阶&#xff1a;自定义转换器&#xff08;Converter&#xff09; 其它自定义转换器没生效 Easy Excel在…...

简单聊下阿里云DNS劫持事件

阿里云域名被DNS劫持事件 事件总结 根据ICANN规则&#xff0c;域名注册商&#xff08;Verisign&#xff09;认定aliyuncs.com域名下的部分网站被用于非法活动&#xff08;如传播恶意软件&#xff09;&#xff1b;顶级域名DNS服务器将aliyuncs.com域名的DNS记录统一解析到shado…...

2025-06-08-深度学习网络介绍(语义分割,实例分割,目标检测)

深度学习网络介绍(语义分割,实例分割,目标检测) 前言 在开始这篇文章之前&#xff0c;我们得首先弄明白&#xff0c;什么是图像分割&#xff1f; 我们知道一个图像只不过是许多像素的集合。图像分割分类是对图像中属于特定类别的像素进行分类的过程&#xff0c;即像素级别的…...