|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
传送门:https://leetcode-cn.com/problems ... form-all-employees/
解:
1.自底向上
从每一个底层员工向上找上司,类似于并查集的查找。由于每次都要遍历一遍到老板的路径,时间效率不高。
- class Solution {
- public:
- int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
- int ans = 0;
- for (int i = 0; i < n; ++i)
- {
- if (!informTime[i])//利用底层员工通知时间为0的设定进行剪枝
- {
- int temp = 0;
- for (int j = manager[i]; j != -1; j = manager[j]) temp += informTime[j];
- ans = max(ans, temp);
- }
- }
- return ans;
- }
- };
复制代码
2.自顶向下
建图+BFS
- class Solution {
- public:
- vector<int> member[100005];
-
- int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
- for (int i = 0; i < n; ++i) if (i != headID) member[manager[i]].push_back(i);
-
- int ans = 0;
- queue<pair<int, int>> q;
- q.push({headID, 0});
-
- while (!q.empty())
- {
- int id = q.front().first;
- int temp = q.front().second;
- q.pop();
-
- ans = max(ans, temp);
- for (int each: member[id]) q.push({each, temp + informTime[id]});
- }
-
- return ans;
- }
- };
复制代码 |
|