山西省消防总队建设工程备案网站,兰州网站建设招聘,怎样做ppt下载网站,电子商务网站建设与管理课程的意义1376. 通知所有员工所需的时间
目录
一、bfs 二、dfs 题目#xff1a; 公司里有 n 名员工#xff0c;每个员工的 ID 都是独一无二的#xff0c;编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。在 manager 数组中#xff0c;每个员工都有一个直属负责人#x…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 N100010;int[] hnew int[N],enew int[N],nenew 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 resinformTime[headID];Arrays.fill(h,-1);for(int i0;in;i) {if(manager[i]-1) continue;add(manager[i],i);}Queueint[] qnew LinkedList();q.offer(new int[]{headID,informTime[headID]});while(!q.isEmpty()){var tq.poll();int idt[0],valt[1];if(h[id]-1) {resMath.max(res,val);continue;}for(int ih[id];i!-1;ine[i]){int je[i];q.offer(new int[]{j,valinformTime[j]});}}return res;}
} 二、dfs 思路 用dfs从根节点开始深入 计算每一个节点向下传递信息的最大值 class Solution {static int N100010;int[] hnew int[N],enew int[N],nenew 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 res0;for(int ih[u];i!-1;ine[i]){int je[i];resMath.max(res,dfs(j,informTime));}return informTime[u]res;}public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {int resinformTime[headID];Arrays.fill(h,-1);for(int i0;in;i) {if(manager[i]-1) continue;add(manager[i],i);}return dfs(headID,informTime);}
}
