Leetcode1376. 通知所有员工所需的时间(medium,DFS,DP)_leetcode 1376通知所有员工所需时间。

目录

1. 题目描述

2. 方法一

2.1 思路

2.2 代码实现

3. 方法二：动态规划

3.1 思路

3.2 代码实现 

---

1. 题目描述

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

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

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

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

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

示例 1：

输入：n = 1, headID = 0, manager = [-1], informTime = [0]
输出：0
解释：公司总负责人是该公司的唯一一名员工。

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/time-needed-to-inform-all-employees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

2. 方法一

2.1 思路

        因为员工从属关系是的树结构表示，每条边对应的数值是父节点的通知时间。所以本题的实质上是求从根节点到每个叶子节点的加权和的最大值。

        第一感是深度优先。

        基于邻接列表的图表示方式比较方便进行搜索，所以可以先基于manager生成邻接列表。当然由于本题中明确的是树结构，而且搜索是从顶到底的，所以只需要children列表即可。

        以下用递归的方式实现深度优先搜索。

2.2 代码实现

import time
from typing import List
 
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        childs = dict()
        for k in range(n):
            childs[k] = []
        
        for k in range(n):
            parent = manager[k]
            if parent in childs:
                childs[parent].append(k)
        
        def dfs(root) -> int:
            # The longest time cost from the specified root, to the leaf of its subtree
            longestTime = 0
            for child in childs[root]:
                t = dfs(child)
                longestTime = t if t > longestTime else longestTime
            return longestTime + informTime[root]
        
        return dfs(headID)
    
if __name__ == "__main__":
    
    sln = Solution()
    
    n = 1
    headID = 0
    manager = [-1]
    informTime = [0]
    print(sln.numOfMinutes(n, headID, manager, informTime))
    
    n = 6 
    headID = 2
    manager = [2,2,-1,2,2,2] 
    informTime = [0,0,1,0,0,0]
    print(sln.numOfMinutes(n, headID, manager, informTime))

        执行用时：436 ms, 在所有 Python3 提交中击败了44.59%的用户

        内存消耗：51.3 MB, 在所有 Python3 提交中击败了31.14%的用户

3. 方法二：动态规划

3.1 思路

        对于每个员工，通知到达他的时间等于通知到达他的上级的时间以及他的上级发通知所需要的时间。

        由此可以得到一个动态规划解决方案。

3.2 代码实现 

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        memo = dict()
        memo[headID] = 0
        
        def dp(staff:int) -> int:
            if staff in memo:
                return memo[staff]
            t = dp(manager[staff]) + informTime[manager[staff]]
            memo[staff] = t
            return t
        
        maxT = 0
        for k in range(n):
            t = dp(k)
            maxT = t if t > maxT else maxT
        
        return maxT

        执行用时：360 ms, 在所有 Python3 提交中击败了73.44%的用户

        内存消耗：88.1 MB, 在所有 Python3 提交中击败了5.24%的用户

        回到主目录：笨牛慢耕的Leetcode每日一解题解笔记(动态更新。。。)