员工的重要性
难度:
标签:
题目描述
代码结果
运行时间: 103 ms, 内存: 17.2 MB
/*
* 题目思路:
* 1. 定义一个 Employee 类,包含 id、重要度和下属 id 列表。
* 2. 使用 HashMap 存储所有员工信息,以便快速查找员工。
* 3. 使用 Stream 计算指定员工及其下属的重要度之和。
*/
import java.util.*;
import java.util.stream.*;
class Employee {
public int id;
public int importance;
public List<Integer> subordinates;
}
public class Solution {
private Map<Integer, Employee> employeeMap = new HashMap<>();
public int getImportance(List<Employee> employees, int id) {
employees.forEach(e -> employeeMap.put(e.id, e));
return getTotalImportance(id);
}
private int getTotalImportance(int id) {
Employee employee = employeeMap.get(id);
return employee.importance + employee.subordinates.stream()
.mapToInt(this::getTotalImportance)
.sum();
}
}
解释
方法:
本题解使用深度优先搜索(DFS)的方法,用哈希表 mp 存储员工 ID 到员工对象的映射,然后从给定的员工 ID 开始递归计算所有下属员工的重要度之和。在DFS过程中,对于每个员工,将其自身的重要度与所有直系下属的重要度相加,直到下属员工为空,然后回溯并返回总重要度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中,你提到使用哈希表来存储员工ID到员工对象的映射,这种方法在处理非连续或非整数ID时是否有特殊考虑或限制?
▷🦆
题解使用了深度优先搜索(DFS)进行数据遍历,这种方式在处理特别大的员工层级结构时是否会遇到栈溢出问题?如果会,如何避免?
▷🦆
题解中的递归函数`dfs`在计算总重要度时直接累加了自身和所有直系下属的重要度,这在有循环引用(即员工间存在环形结构)的情况下是否会导致无限递归?
▷🦆
在哈希表`mp`的使用中,如果输入的员工ID不存在于员工列表中,题解中的代码将如何处理?
▷