易班网站的建设内容,网络营销方案模板,如何开发微信微网站,辽宁省建设工程造价管理协会网站题目描述
公司里有 n 名员工#xff0c;每个员工的 ID 都是独一无二的#xff0c;编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。
在 manager 数组中#xff0c;每个员工都有一个直属负责人#xff0c;其中 manager[i] 是第 i 名员工的直属负责人。对于总负责…题目描述
公司里有 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 。 题目 保证 所有员工都可以收到通知。
分析
我们只需要从总负责人出发访问所有下属访问的同时计算出当前节点下属的得到通知的时间返回最大的时间。这里采用BFS算法遍历。
代码
class Solution {public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {LinkedListInteger treenew LinkedList();tree.add(headID);int ans0;int[] dpnew int[n];//dp[i]表示节点i得到通知的时间dp[headID]0;while(tree.isEmpty()false){int nodetree.poll();for(int i0;in;i){//对于每个节点找到它的子节点if(manager[i]node){tree.add(i);//当前节点得到信息的时间父节点时间父节点到当前节点的时间dp[i]dp[node]informTime[node];ansMath.max(ans,dp[i]);//取最大时间}}}return ans;}
}优化
对于每一个节点寻找子节点的过程中都需要遍历一遍manager[]时间复杂度是On^2。我们可以先把节点对应的子节点先找出来这样寻找子节点就不需要遍历整个数组。
class Solution {public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {LinkedListInteger treenew LinkedList();tree.add(headID);int[] dpnew int[n];dp[headID]0;//先找出每个节点的子节点保存到map中HashMapInteger,ListInteger mapnew HashMap();for(int i0;in;i){if(map.containsKey(manager[i])){map.get(manager[i]).add(i);}else {ListInteger listnew ArrayList();list.add(i);map.put(manager[i],list);}}int ans0;while(tree.isEmpty()false){int nodetree.poll();if(map.containsKey(node)){for(int i:map.get(node)){tree.add(i);dp[i]dp[node]informTime[node];ansMath.max(ans,dp[i]);}}}return ans;}
}时间复杂度On
