LeetCode算法题-Employee Importance（Java实现）

佚名 5年前 (2019-03-29) 算法 2090人围观抢沙发百度已收录

这是悦乐书的第291次更新，第309篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第159题（顺位题号是690）。定义员工信息的数据结构，其中包括员工的唯一ID，他的重要性值以及他的直接下属ID。例如，员工1是员工2的领导者，员工2是员工3的领导者。他们的重要性值分别为15,10和5。然后，员工1具有[1,15，[2]]等数据结构，员工2具有[2,10，[3]]，员工3具有[3,5，[]]。请注意，虽然员工3也是员工1的下属，但该关系不是直接的。现在，根据公司的员工信息和员工ID，您需要返回该员工及其所有下属的总重要性值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：[[1,5，[2,3]]，[2,3，[]]，[3,3，[]]]，1

输出：11

说明：员工1具有重要性值5，他有两个直接下属：员工2和员工3.他们都具有重要性值3.因此员工1的总重要性值是5 + 3 + 3 = 11。

注意：

一名员工最多只有一名直接领导，但是可以有多名下属。
最多员工人数不超过2000人。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

题目的意思是找到所给id员工的重要性以及所有下属员工重要性之和，如果其下属员工本身也有下属，也要算进去，也就是说该问题的子问题还是问题本身。因此我们可以使用递归的方法。

先找到当前id所在的员工信息和其下属员工的id集合，我们将其下属员工id放入HashSet中，然后再去遍历所有员工集合，如果HashSet中包含当前员工的id，就累加上其重要值，然后对其下属员工进行再处理，调用递归方法，最后返回sum。

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        return helper(employees, id);
    }

    public int helper(List<Employee> employees, int id){
        List<Integer> sub = null;
        int sum = 0;
        for (Employee em : employees) {
            if (em.id == id) {
                sub = em.subordinates;
                sum += em.importance;
                break;
            }
        }
        Set<Integer> set = new HashSet<Integer>();
        for (Integer num : sub) {
            set.add(num);   
        }
        for (Employee em : employees) {
            if (set.contains(em.id)) {
                sum += helper(employees, em.id);
            }
        }
        return sum;
    }
}

03 第二种解法

我们可以对第一种解法再优化下，依旧使用递归，但是使用HashMap对初始员工数据进行处理，以id为key，以员工信息为value。递归方法中，以id为参数，查找当前id在HashMap中对应的员工信息，定义一个sum变量，初始值为当前员工的重要性，遍历当前员工的下属员工id集合，调用递归方法本身，最后返回sum。

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {

    public Map<Integer, Employee> map ;
    public int getImportance(List<Employee> employees, int id) {
        map = new HashMap<Integer, Employee>();
        for (Employee em : employees) {
            map.put(em.id, em);
        }
        return helper(id);
    }

    public int helper(int id){
        Employee em = map.get(id);
        int sum = em.importance;
        for (Integer num : em.subordinates) {
            sum += helper(num);
        }
        return sum;
    }
}

04 第三种解法

我们也可以使用迭代的方式来处理，借助队列来实现，当然你也可以使用栈。依旧是将所有的员工信息遍历放入HashMap中，以id为key，以员工信息为value。然后创建一个队列，将参数id作为初始元素入队列，接着对队列中的数据进行处理，出队列，然后使用id在HashMap中查找对应的value，找到后，累加上其重要值，然后遍历该员工的下属，将下属的id加入到队列中去，一直循环处理，直到队列为空。最后返回sum。

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {

    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();
        for (Employee em : employees) {
            map.put(em.id, em);
        }
        int sum = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(id);
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            Employee e = map.get(temp);
            sum += e.importance;
            for (Integer num : e.subordinates) {
                queue.offer(num);
            }
        }
        return sum;
    }
}