leetcode.1376 通知所有员工所需的时间 - bfs/dfs + 树
1376. 通知所有员工所需的时间
目录
一、bfs
二、dfs
题目:
- 公司里有 n 名员工,每个员工的 ID 都是独一无二的,编号从 0 到 n - 1。
- 公司的总负责人通过 headID 进行标识。
- 在 manager 数组中,每个员工都有一个直属负责人,其中 manager[i] 是第 i 名员工的直属负责人。
- 对于总负责人,manager[headID] = -1。题目保证从属关系可以用树结构显示。
- 公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们,然后由这些下属通知他们的下属,直到所有的员工都得知这条紧急消息。
- 第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属(也就是说在 informTime[i] 分钟后,他的所有直属下属都可以开始传播这一消息)。
- 返回通知所有员工这一紧急消息所需要的 分钟数
一、bfs
思路:
刚开始读错题了,以为是所有人都通知到的总时间
但这题其实是,返回通知到最深一层的时间,即求最深树权值之和
我们可以用bfs遍历整棵树,队列存二元组【节点值,当前路累计权值】
如果发现没有子节点,则更新最大值
否则遍历子节点,累加权值入队
class Solution {static int N=100010;int[] h=new int[N],e=new int[N],ne=new int[N];int idx;public void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {int res=informTime[headID];Arrays.fill(h,-1);for(int i=0;i<n;i++) {if(manager[i]==-1) continue;add(manager[i],i);}Queue<int[]> q=new LinkedList<>();q.offer(new int[]{headID,informTime[headID]});while(!q.isEmpty()){var t=q.poll();int id=t[0],val=t[1];if(h[id]==-1) {res=Math.max(res,val);continue;}for(int i=h[id];i!=-1;i=ne[i]){int j=e[i];q.offer(new int[]{j,val+informTime[j]});}}return res;}
}
二、dfs
思路:
用dfs从根节点开始深入
计算每一个节点向下传递信息的最大值
class Solution {static int N=100010;int[] h=new int[N],e=new int[N],ne=new int[N];int idx;public void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}public int dfs(int u,int[] informTime){int res=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];res=Math.max(res,dfs(j,informTime));}return informTime[u]+res;}public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {int res=informTime[headID];Arrays.fill(h,-1);for(int i=0;i<n;i++) {if(manager[i]==-1) continue;add(manager[i],i);}return dfs(headID,informTime);}
}
相关文章:
leetcode.1376 通知所有员工所需的时间 - bfs/dfs + 树
1376. 通知所有员工所需的时间 目录 一、bfs 二、dfs 题目: 公司里有 n 名员工,每个员工的 ID 都是独一无二的,编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。在 manager 数组中,每个员工都有一个直属负责人&#x…...

AtCoder Beginner Contest 300——A-G题讲解
蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本初中生蒟蒻讲解一下AtCoder Beginner Contest 300这场比赛的A-G题! A - N-choice question 原题 Problem Statement Given integers A A A and…...

Go:值与指针
1. 计算机中的值 在百万年的演化历史中,人类对事物的属性进行了抽象,有了数量、精度、信息等概念的表示,对应的我们称之为整数、小数、文本文字等。计算机出现后,我们使用计算机对真实世界的问题进行建模,通过计算机的…...

【Linux】进程学习(2)---理解进程操作
文章目录 查看进程通过系统目录查看通过ps命令查看 通过系统调用获取进程标识符通过系统调用创建进程初识fork函数fork函数的返回值 进程状态阻塞与运行状态Linux内核源码中的进程状态运行状态-R浅度睡眠状态-S深度睡眠状态-D暂停状态-T僵尸状态-Z死亡状态-X 查看进程 通过系统…...

基于springcloud实现的医院信息系统
访问【WRITE-BUG数字空间】_[内附完整源码和文档] 医疗信息就诊系统,系统主要功能按照数据流量、流向及处理过程分为临床诊疗、药品管理、财务管理、患者管理。诊疗活动由各工作站配合完成,并将临床信息进行整理、处理、汇总、统计、分析等。本系统包括以…...

设计模式-创建型模式-(工厂、简单工厂、抽象工厂)
一、简单工厂模式 上代码 public class FoodFactory {public static Food makeFood(String name) {if (name.equals("noodle")) {Food noodle new LanZhouNoodle();noodle.addSpicy("more");return noodle;} else if (name.equals("chicken")…...
JAVA12新特性
JAVA12新特性 概述 2019年3月19日,java12正式发布了,总共有8个新的JEP(JDK Enhancement Proposals) JDK 12 is the open-source reference implementation of version 12 of the Java SE12 Platform as specified by by JSR 386 in the Java Community Process. JDK 12 reac…...

Nginx 静态文件、反向代理、负载均衡、缓存、SSL/TLS 加密、gzip 压缩 等等
Nginx的功能 1. 静态文件服务器2. 反向代理服务器3. 负载均衡4. 缓存5. SSL/TLS 加密6. URL 重写7. HTTP/28. WebSocket9. 反向代理缓存10. 安全限制11. gzip 压缩12. 请求限速13. 日志记录14. SSL 证书续订 Nginx 是一个高性能的开源 Web 服务器和反向代理服务器,它…...

Linux设备驱动模型(一)
一、sysfs文件系统 sysfs是一个虚拟文件系统,将内核总的设备对象的链接关系,以文件目录的方式表示出来,并提对设备提供读写接口。 二、kobject kobject是内核中对象表示的基类,可以认为所有的内核对象都是一个kobject kobject单…...

【Python入门篇】——Python基础语法(标识符与运算符)
作者简介: 辭七七,目前大一,正在学习C/C,Java,Python等 作者主页: 七七的个人主页 文章收录专栏: Python入门,本专栏主要内容为Python的基础语法,Python中的选择循环语句…...

扩展 VirtualBox 已分配磁盘的方法
扩展 VirtualBox 已分配磁盘的方法 第一步:用VirtualBox命令行调整已分配磁盘的大小第二步:用windows磁盘管理工具扩展磁盘空间其他无关配置如何选择虚拟机的芯片组 注意:扩展操作只支持 vdi 格式的磁盘,就是VirtualBox自己的磁盘…...

【LeetCode】646. 最长数对链
646. 最长数对链(中等) 思路 这道题和 300. 最长递增子序列 类似,我们可以定义 dp 数组,其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后,统计一遍各个位置的结果即可得到题目要求的结果。 但是题目中强…...

Makefile教程(Makefile的结构)
文章目录 前言一、Makefile的结构二、深入案例三、Makefile中的一些技巧总结 前言 一、Makefile的结构 Makefile 通常由一系列规则组成,每条规则定义了如何从源文件生成目标文件。每个规则又由目标、依赖和命令三部分组成。 下面是 Makefile 规则的基本结构&…...

SpringMVC(后)SSM整合
10、文件上传和下载 10.1、文件下载 ResponseEntity用于控制器方法的返回值类型,该控制器方法的返回值就是响应到浏览器的响应报文 使用ResponseEntity实现下载文件的功能 RequestMapping("/testDown") public ResponseEntity<byte[]> testResp…...

【博弈论】【第一章】博弈论导论
博弈论导论 【例题】选择数字【例题】巴什博弈【例题】射手博弈博弈论的基本概念:参与人战略行动信息支付函数【例题】分100元 课程概述: 【例题】选择数字 两个参与人A和B,轮流选择[3,4,5,6,7,8,9]中的一个整数(可重复)。当累计…...

keil移植linux(makefile)
文章目录 运行环境:1.1 freeRTOS_LED工程移植1)修改cubeMX配置2)setting设置3)launch设置4)修改makefile5)修改代码6)实验效果 运行环境: ubuntu18.04.melodic 宏基暗影骑士笔记本 stm32f427IIH6 stlink 9-24v可调电源 robomaster A 板 1.1 freeRTOS_L…...

C++——类和对象(3)
作者:几冬雪来 时间:2023年5月6日 内容:C类和对象内容讲解 目录 前言: 1.运算符重载(续): 2.赋值重载: 结尾: 前言: 在上一篇博客中我们再一次讲解了…...

itop-3568开发板驱动学习笔记(24)设备树(三)时钟实例分析
《【北京迅为】itop-3568开发板驱动开发指南.pdf》 学习笔记 文章目录 生产者属性#clock-cells 属性clock-output-namesclock-frequencyassigned-clockclock-indicesassigned-clock-parents 消费者属性 设备树中的时钟信息以时钟树形式体现,时钟树包括时钟的属性和结…...

linux中使用docker部署微服务
目录 一、制作jar包(如果看一眼很简单,可以直接使用结尾的jar) 1.首先创建一个微服务 demo2 2.启动微服务(在DemoApplication上右键执行启动就行) 注意:其他操作导致的 可能遇到的报错 3.修改端口 4.新…...

操作系统考试复习—第三章 优先级倒置 死锁问题
当前OS广泛采用优先级调度算法和抢占方式,然而在系统中存在着影响进程运行的资源从而可能产生"优先级倒置"现象 具体解释为:在原本的调度算法设计中,高优先级进程可以抢占低优先级的CPU资源,先执行高优先级任务。但是存…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...