LeetCode 题解工作台
员工的重要性
你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。 给定一个员工数组 employees ，其中： employees[i].id 是第 i 个员工的 ID。 employees[i].importance 是第 i 个员工的重要度。 employees[i].…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 存储所有员工的信息，其中键是员工的 ID，值是员工对象。然后我们从给定的员工 ID 开始深度优先搜索，每次遍历到一个员工时，将该员工的重要度加到答案中，并递归遍历该员工的所有下属，将下属的重要度也加到答案中。 时间复杂度 ，空间复杂度 。其中 是员工的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
给定一个员工数组 employees，其中：
employees[i].id是第i个员工的 ID。employees[i].importance是第i个员工的重要度。employees[i].subordinates是第i名员工的直接下属的 ID 列表。
给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。
示例 1：
输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1 输出：11 解释： 员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。
示例 2：
输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5 输出：-3 解释：员工 5 的重要度为 -3 并且没有直接下属。 因此，员工 5 的总重要度为 -3。
提示：
1 <= employees.length <= 20001 <= employees[i].id <= 2000- 所有的
employees[i].id互不相同。 -100 <= employees[i].importance <= 100- 一名员工最多有一名直接领导，并可能有多名下属。
employees[i].subordinates中的 ID 都有效。
解题思路
方法一：哈希表 + DFS
我们用一个哈希表 存储所有员工的信息，其中键是员工的 ID，值是员工对象。然后我们从给定的员工 ID 开始深度优先搜索，每次遍历到一个员工时，将该员工的重要度加到答案中，并递归遍历该员工的所有下属，将下属的重要度也加到答案中。
时间复杂度 ，空间复杂度 。其中 是员工的数量。
"""
# Definition for Employee.
class Employee:
def __init__(self, id: int, importance: int, subordinates: List[int]):
self.id = id
self.importance = importance
self.subordinates = subordinates
"""
class Solution:
def getImportance(self, employees: List["Employee"], id: int) -> int:
def dfs(i: int) -> int:
return d[i].importance + sum(dfs(j) for j in d[i].subordinates)
d = {e.id: e for e in employees}
return dfs(id)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) because each employee is visited once through either DFS or BFS. Space complexity is O(N) due to the hash map and potential recursion stack or BFS queue storage. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for candidates building a hash map to avoid repeated array scans.
- question_mark
Watch if recursion correctly handles indirect subordinates in nested hierarchies.
- question_mark
Check for both DFS and BFS awareness in accumulating total importance.
常见陷阱
外企场景- error
Summing only direct subordinates and ignoring deeper levels.
- error
Repeatedly scanning the employee array instead of using a hash map for O(1) lookups.
- error
Failing to handle employees with negative importance values correctly.
进阶变体
外企场景- arrow_right_alt
Compute total importance but return the highest importance path in the hierarchy instead of the sum.
- arrow_right_alt
Allow dynamic addition or removal of subordinates and recalculate importance on the fly.
- arrow_right_alt
Calculate importance with constraints on maximum traversal depth for partial aggregation scenarios.