資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
