欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

员工的重要性(力扣: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;
    }