房屋租赁网站开发模版,建站程序下载,eclipse网站开发流程,网页设计与制作公告栏1. 题目
公司里有 n 名员工#xff0c;每个员工的 ID 都是独一无二的#xff0c;编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。
在 manager 数组中#xff0c;每个员工都有一个直属负责人#xff0c;其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人…1. 题目
公司里有 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 分钟来通知所有员工。
上图显示了公司员工的树结构。示例 3 输入n 7, headID 6, manager [1,2,3,4,5,6,-1],
informTime [0,6,5,4,3,2,1]
输出21
解释总负责人 id 6。他将在 1 分钟内通知 id 5 的员工。
id 5 的员工将在 2 分钟内通知 id 4 的员工。
id 4 的员工将在 3 分钟内通知 id 3 的员工。
id 3 的员工将在 4 分钟内通知 id 2 的员工。
id 2 的员工将在 5 分钟内通知 id 1 的员工。
id 1 的员工将在 6 分钟内通知 id 0 的员工。
所需时间 1 2 3 4 5 6 21 。示例 4
输入n 15, headID 0, manager [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6],
informTime [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
输出3
解释第一分钟总负责人通知员工 1 和 2 。
第二分钟他们将会通知员工 3, 4, 5 和 6 。
第三分钟他们将会通知剩下的员工。示例 5
输入n 4, headID 2, manager [3,3,-1,2], informTime [0,0,162,914]
输出1076提示
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 。
题目 保证 所有员工都可以收到通知。来源力扣LeetCode 链接https://leetcode-cn.com/problems/time-needed-to-inform-all-employees 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
从叶子时间等于0的开始往上找
class Solution {
public:int numOfMinutes(int n, int headID, vectorint manager, vectorint informTime) {if(n 1)return informTime[0];//1个人直接返回他的时间int i, t 0, tmax 0, leader;for(i 0; i n; i)//n个人{if(informTime[i] 0)//底层员工{t 0;leader manager[i];//他的领导编号while(manager[leader] ! -1)//领导的上级编号不为-1{t informTime[leader];//时间累加leader manager[leader];//往上找再上一级}t informTime[leader];//最后一个领导if(t tmax)tmax t;//更新最大值}}return tmax;}
};执行用时488 ms 内存消耗87.8 MB
