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

Categories:

题目描述
思路分析
1. 解法一：树形 DFS/BFS（推荐）
相似题目

题目描述

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

思路分析

解法一：树形 DFS/BFS（推荐）

核心思路：

构建管理关系的邻接表。

从 headID 开始 DFS/BFS，子节点通知时间为父节点时间加上 informTime[parent]。

取所有节点通知时间最大值。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            int m = manager[i];
            if (m != -1) {
                g[m].add(i);
            }
        }
        return dfs(headID, g, informTime);
    }

    private int dfs(int u, List<Integer>[] g, int[] informTime) {
        int max = 0;
        for (int v : g[u]) {
            max = Math.max(max, dfs(v, g, informTime));
        }
        return informTime[u] + max;
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        if manager[i] != -1 {
            g[manager[i]] = append(g[manager[i]], i)
        }
    }

    var dfs func(int) int
    dfs = func(u int) int {
        max := 0
        for _, v := range g[u] {
            t := dfs(v)
            if t > max {
                max = t
            }
        }
        return informTime[u] + max
    }

    return dfs(headID)
}

相似题目

题目	难度	考察点
1136. 平行课程	中等	拓扑
207. 课程表	中等	图遍历
210. 课程表 II	中等	图遍历
543. 二叉树的直径	简单	树 DP
102. 二叉树的层序遍历	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/57463229