Keshawn_lu's Blog

Leetcode 1376. 通知所有员工所需的时间

广度优先遍历
字数统计: 577阅读时长: 2 min
2023/05/01 Share

题目简介：

公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。

在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。

公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。

第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。

返回通知所有员工这一紧急消息所需要的 分钟数 。

示例 1：

graph

1
2
3
4
输入：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 。
  • 题目 保证 所有员工都可以收到通知。

思路：

首先利用哈希表建立树形结构。

将{员工id, 通知消息所需要花费的总时间}作为二元组压入队列中，初始化时将{headID, 0}压入。

依次遍历，将当前员工的下属依次压入队列，并同时更新花费时间的最大值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

        unordered_map<int, vector<int>> map;

        for(int i = 0; i < manager.size(); ++i){

            map[manager[i]].push_back(i);
        }

        queue<pair<int, int>> qu;
        qu.push({headID, 0});

        int res = 0;
        while(!qu.empty()){

            auto [id, time] = qu.front();
            qu.pop();

            for(auto& low_id : map[id]){

                qu.push({low_id, time + informTime[id]});

                res = max(res, time + informTime[id]);
            }
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网