​力扣解法汇总1376. 通知所有员工所需的时间

news/2024/4/21 1:25:44/

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

公司里有 n 名员工,每个员工的 ID 都是独一无二的,编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。

在 manager 数组中,每个员工都有一个直属负责人,其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人,manager[headID] = -1。题目保证从属关系可以用树结构显示。

公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们,然后由这些下属通知他们的下属,直到所有的员工都得知这条紧急消息。

第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属(也就是说在 informTime[i] 分钟后,他的所有直属下属都可以开始传播这一消息)。

返回通知所有员工这一紧急消息所需要的 分钟数 。

示例 1:

输入:n = 1, headID = 0, manager = [-1], informTime = [0]
输出:0
解释:公司总负责人是该公司的唯一一名员工。

示例 2:

输入:n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出:1
解释:id = 2 的员工是公司的总负责人,也是其他所有员工的直属负责人,他需要 1 分钟来通知所有员工。
上图显示了公司员工的树结构。

提示:

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • 如果员工 i 没有下属,informTime[i] == 0 。
  • 题目 保证 所有员工都可以收到通知。

 

解题思路:

* 解题思路:
* 最常规的思路,肯定是根据输入值生成树结构。但是这样代码较长,而且效率较低,所以我们直接模仿这种树的节点遍历的方式来进行。
* 首先,构建一个map,key为bossId,value为List,存放所有下属的ID。
* 然后构建递归方法,递归方法中,输入bossId,返回其告之所有下属所需要的时间。
* 如果下属为0,则直接返回0。如果下属不为0,返回下属中最长的时间+自身告之的时间。

代码:

public class Solution1376 {public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < manager.length; i++) {int bossId = manager[i];List<Integer> subList = map.get(bossId);if (subList == null) {subList = new ArrayList<>();map.put(bossId, subList);}subList.add(i);}return search(headID, map, informTime);}private int search(int bossId, Map<Integer, List<Integer>> map, int[] informTime) {List<Integer> integers = map.get(bossId);if (integers == null || integers.size() == 0) {return 0;}int maxTime = 0;for (int id : integers) {maxTime = Math.max(search(id, map, informTime), maxTime);}return maxTime + informTime[bossId];}}


http://www.ppmy.cn/news/56977.html

相关文章

RK3588平台开发系列讲解(进程篇)Linux中进程的一生

平台内核版本安卓版本RK3588Linux 5.10Android 12文章目录 一、Linux 系统中进程的一生二、Linux 系统中的进程树三、Linux 进程的分类四、进程优先级五、进程系统调用沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍 Linux 进程的相关知识。 一、Linux 系统…

多线程、协程和多进程并发编程

37.1 如何通俗理解线程和进程&#xff1f; 进程&#xff1a;进程就是正在执⾏的程序。 线程&#xff1a;是程序执⾏的⼀条路径, ⼀个进程中可以包含多条线程。 通俗理解&#xff1a;例如你打开抖⾳&#xff0c;就是打开⼀个进程&#xff0c;在抖⾳⾥⾯和朋友聊天就是开启了⼀条…

Docker基础知识全解析

​ Docker是一个开源的容器化平台&#xff0c;可以让开发者在容器中构建、打包、运行和发布应用程序&#xff0c;从而实现应用程序的快速部署和可移植性。Docker将应用程序和依赖项打包在一个轻量级的可移植容器中&#xff0c;这个容器可以在任何平台上运行&#xff0c;不会受到…

计算机组成原理第五章(2)---中断

5.1概述 产生和应用 在IO设备和主机交换数据时&#xff0c;由于设备本身的机电特性的影响&#xff0c;其工作速度比较低&#xff0c;与CPU无法匹配&#xff0c;如果采用程序查询的方式需要CPU进行等待&#xff0c;但是如果在等待的过程中CPU可以执行其他的程序&#xff0c;可…

arthas--watch函数执行数据观测

目录 背景 参数说明 参考 背景 watch能方便的观察到指定函数的调用情况。能观察到的范围为&#xff1a;返回值、抛出异常、入参&#xff0c;通过编写 OGNL 表达式进行对应变量的查看。ognl学习&#xff0c;可以参考&#xff1a;https://xiaopanjia.blog.csdn.net/article/d…

制造管理与生产管理,到底哪个更重要?

制造工业是各个国家经济的重要组成部分&#xff0c;也是整体经济运行的基础。生产管理则是制造工业的核心。随着科技和全球市场的飞速发展&#xff0c;制造和生产管理面临着新的挑战和机遇。优秀的制造和生产管理能力是一个企业取得成功的关键之一。 一、制造管理的概念及现状…

IS-IS协议基础知识

文章目录 前言介绍地址格式报文格式区域及路由器类型区域类型路由器类型Level-1 路由器Level-2 路由器Level-1-2路由器 IS-IS 网络类型DIS及伪节点伪节点DIS与OSPF的DR/BDR不同之处 IS-IS 邻接关系握手报文邻接关系的建立 IS-IS 链路状态数据库概述数据库同步报文泛洪机制数据库…

js 操作数组内容

js 操作数组内容 数组添加元素&#xff08;更改原数组&#xff09; push和unshift会返回添加了新元素的数组长度 push从数组最后加入&#xff0c;unshift从数组最前面加入 const arr ["a", "b", "c"]; arr.push("d"); //返回4…

从0搭建Vue3组件库(十一): 集成项目的编程规范工具链(ESlint+Prettier+Stylelint)

欲先善其事,必先利其器。一个好的项目是必须要有一个统一的规范,比如代码规范,样式规范以及代码提交规范等。统一的代码规范旨在增强团队开发协作、提高代码质量和打造开发基石,所以每个人必须严格遵守。 本篇文章将引入 ESLintPrettierStylelint 来对代码规范化。 ESlint ES…

深入浅出 Compose Compiler(1) Kotlin Compiler KCP

前言 Compose 的语法简洁、代码效率非常高&#xff0c;这主要得益于 Compose Compiler 的一系列编译期魔法&#xff0c;帮开发者生成了很多样板代码。但编译期插桩也阻碍了我们对于 Compose 运行原理的认知&#xff0c;想要真正读懂 Compose 就必须先了解它的 Compiler。本系列…

第14章 项目采购管理

文章目录 采购管理包括如下几个过程14.2 编制采购计划 462编制采购计划的输出1&#xff09;采购管理计划2&#xff09;采购工作说明书3&#xff09;采购文件 14.2.3 工作说明书&#xff08;SOW&#xff09; 14.3 实施采购 47414.3.2 实施采购的方法和技术 476&#xff08;1&…

安装KVM

安装KVM 1 检查系统是否支持虚拟化 看看CPU是否支持虚拟化。 # grep -E -o vmx|svm /proc/cpuinfo 注意&#xff1a;返回vmx代表支持因特尔&#xff08;Intel&#xff09;系列CPU的虚拟化&#xff0c;返回svm代表支持AMD系列CPU的虚拟化。 2 安装软件包。 使用yum安装KVM…

【Java】抽象类接口Object类

目录 1.抽象类 2.接口 2.1实现多个接口 2.2接口之间的关系 2.3接口使用实例 2.3.1Comparable接口 2.3.2Comparator接口 2.3.2Clone接口 2.4抽象类与接口的区别 3.Object类 3.1getClass方法 3.2equals方法 3.3hashcode方法 1.抽象类 定义&#xff1a;抽象方法&…

socket套接字

前言 两个应用程序如果需要进行通讯最基本的一个前提就是能够唯一的标示一个进程&#xff0c;我们知道IP层的ip地址可以唯一标示主机&#xff0c;而TCP层协议和端口号可以唯一标示主机的一个进程&#xff0c;这样我们可以利用ip地址&#xff0b;协议&#xff0b;端口号唯一标示…

JAVA医院管理云HIS统计报表子系统、系统管理字系统功能实现

一、统计报表子系统 统计报表子系统功能模块&#xff1a;包括门诊收入汇总、住院收入汇总、收费统计报表、收费明细报表、 缴款日报、门诊收费汇总、住院科室日志、住院结算汇总、医疗项目统计、检查项目统计、 检验项目统计、月末收支汇总、药品进销存统计。 &#xff08;1…

Qt之QGraphicsView实现截图(漏洞百出且BUG丛生版,部分源码+注释)

文章目录 一、截图操作示例图1.图元绘制示例2.文本添加操作示例3.设置操作示例4.截图拖动示例5.文件保存示例6.剪切板粘贴示例 二、内容指路和思路三、部分源码1.自定义文本框源码2.多类型图形数据的存储3.截图源码 总结相关文章 一、截图操作示例图 1.图元绘制示例 下方一次…

【英语】大学英语CET考试,写作部分(论述文+应用文,6篇范文)

文章目录 3项评分标准&#xff08;内容&结构&#xff0c;语言&#xff09;0.1 论述文个人小结 1、论述文&#xff1a;审题与功能句2、论述文&#xff1a;修饰内容和名言模板3、论述文&#xff1a;现象作文&利弊分析4、论述文&#xff1a;给出权威论据和有侧重的现象5、…

TPM-TPM-Profile-PTP协议-2

TCG_PCClient_Device_Driver_Design_Principles_TPM2p0_v1p1_r4_211104_final.pdf 4 简介 本文档补充了 TCG PC Client Platform TPM Profile for TPM 2.0 Specification [PTP]&#xff1b; 特别是&#xff0c;本文档为有兴趣开发 DD 的 DD 编写者提供指导&#xff0c;以便与旨…

Photoshop如何使用通道之实例演示?

文章目录 0.引言1.利用通道调整图像的颜色2.给风景照替换天空3.制作故障艺术效果4.使用通道抠取复杂图像 0.引言 因科研等多场景需要进行绘图处理&#xff0c;笔者对PS进行了学习&#xff0c;本文通过《Photoshop2021入门教程》及其配套素材结合网上相关资料进行学习笔记总结&a…

电脑中病毒了怎么修复,计算机Windows系统预防faust勒索病毒方法

随着计算机系统的不断发展&#xff0c;我们所面对的网络安全威胁也变得越来越严重。其中&#xff0c;较为常见且危险的威胁就是勒索病毒。随着勒索病毒加密算法的不断升级&#xff0c;最近faust勒索病毒开始流行。Faust勒索病毒主要的攻击目标是Windows操作系统&#xff0c;一旦…