员工的重要性(力扣:690)
程序员文章站
2022-05-21 08:13:51
...
员工的重要性
题目
员工的重要性(力扣:690)
给定一个保存员工信息的数据结构,它包含了员工唯一的id,重要度 和 直系下属的id。
比如,员工1是员工2的领导,员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]],员工2的数据结构是[2, 10, [3]],员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属,但是由于并不是直系下属,因此没有体现在员工1的数据结构中。
现在输入一个公司的所有员工信息,以及单个员工id,返回这个员工和他所有下属的重要度之和。
分析
该题的数据结构,其实就是一个树的结构。题目可以抽象为,查找某个员工为根节点的,员工自己和它的所有下属的重要性之和。
我们可以使用辅助Map来帮助我们实现快速查找员工。
代码实现
class Employee {
public int id;
public int importance;
public List<Integer> subordinates;
};
Map<Integer, Employee> employeeMap = new HashMap<>();
/**
* 690. 员工的重要性
* @param employees
* @param id
* @return
*/
public int getImportance(List<Employee> employees, int id) {
for (Employee employee : employees){
employeeMap.put(employee.id, employee);
}
return searchImportance(employeeMap.get(id), id);
}
private int searchImportance(Employee employee, int id){
if (employee == null || id <= 0){
return 0;
}
int sum = employee.importance;
for (Integer subId : employee.subordinates){
sum += searchImportance(employeeMap.get(subId), subId);
}
return sum;
}
推荐阅读