数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中通知所有员工所需的时间
假设一家公司有 n 名员工，每名员工都有一个唯一的 ID。这些 ID 的范围从 0 到 n - 1。公司的负责人是 ID 为 headID 的人。每个员工都有一个直属经理，在 manager 数组中给出，其中 manager[i] 是第 i 个员工的直属经理，manager[headID] = -1。并且保证从属关系具有树状结构。这里，公司负责人想要将一条紧急新闻通知给公司所有员工。他可以通知他的直属下属，然后他们会通知他们的下属，依此类推，直到所有员工都知道紧急新闻。第 i 个员工需要 informTime[i] 分钟来通知他所有的直属下属（因此，在 informTime[i] 分钟后，他所有的直属下属都可以开始传播新闻）。我们必须找到通知所有员工紧急新闻所需的时间（分钟）。所以，如果输入类似于 n = 6，headID = 2，manager = [2,2,-1,2,2,2]，infromTime = [0,0,1,0,0,0]，那么输出将是 1。
为了解决这个问题，我们将遵循以下步骤：
ret := 0
定义一个名为 graph 的大小为 n 的数组，设置 root := -1
对于 i 从 0 到 manager 数组的大小
u := managet[i] 且 v := i
如果 u 为 -1，则设置 root := v，并进行下一次迭代
将 v 插入到 graph[u] 中
定义一个队列 q，将 root 插入到 q 中，并定义一个名为 time 的大小为 n 的数组
直到 q 不为空
curr := q 的第一个元素，并从 q 中删除第一个元素
如果 graph[curr] 列表的大小为 0，则跳过到下一次迭代
对于 i 从 0 到 graph[curr] 列表的大小
将 graph[curr, i] 插入到 q 中
time[graph[curr, i]] := time[curr] + informTime[curr]
对于 i 从 0 到 n – 1：ret := ret 和 time[i] 的最大值
返回 ret
示例（C++）
让我们看看以下实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
int ret = 0;
vector <int> graph[n];
int root = -1;
for(int i = 0; i < manager.size(); i++){
int u = manager[i];
int v = i;
if(u == -1) {
root = v;
continue;
}
graph[u].push_back(v);
}
queue <int> q;
q.push(root);
vector <int> time(n);
while(!q.empty()){
int curr = q.front();
q.pop();
if(!graph[curr].size()) continue;
for(int i = 0; i < graph[curr].size(); i++){
q.push(graph[curr][i]);
time[graph[curr][i]] = time[curr] + informTime[curr];
}
}
for(int i = 0; i <n; i++)ret = max(ret, time[i]);
return ret;
}
};
main(){
vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0};
Solution ob;
cout << (ob.numOfMinutes(6, 2, v, v1));
}输入
6 2 [2,2,-1,2,2,2] [0,0,1,0,0,0]
输出
1
413 次浏览
