798236606 发表于 2020-3-8 13:11:30

LeetCode 5354. 通知所有员工所需的时间

传送门：https://leetcode-cn.com/problems/time-needed-to-inform-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)//利用底层员工通知时间为0的设定进行剪枝
            {
                int temp = 0;
                for (int j = manager; j != -1; j = manager)temp += informTime;
                ans = max(ans, temp);
            }
      }

      return ans;
    }
};

2.自顶向下
建图+BFS
class Solution {
public:
    vector<int> member;
   
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
      for (int i = 0; i < n; ++i) if (i != headID) member].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) q.push({each, temp + informTime});
      }
      
      return ans;
    }
};
页: [1]
查看完整版本: LeetCode 5354. 通知所有员工所需的时间