员工的重要性

此博客链接：

员工的重要性

题目链接：https://leetcode-cn.com/problems/employee-importance/

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:

输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:

一个员工最多有一个直系领导，但是可以有多个直系下属
员工数量不超过2000。

题解：

       思路：看完题目，我以为是求直系下属的重要性，并且示例也都是只有直系下属，没有下属的下属，这。。。然后我一顿操作，看着直接按照一维算的。而且取值也不对。

一开始我是这样写的：

class Solution {

    public int getImportance(List<Employee> employees, int id) {

        if(List[id].subordinates==null)

        return List[id].importance;

        int len=List[id].subordinates.size();

        int sum=List[id].importance;

        for(int i=0;i<len;i++)

        {

             sum=sum+List[List[id].subordinates(i)].importance;

        }

        return sum;

    }

}

 后来改了一波，发现自己真是啥也不会啊，真是菜啊，下面代码是意向天开，自认为题目给的Id是按照顺序的，但是，不现实。

错误2代码

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        if(employees[id].subordinates==null)
        return employees[id].importance;
        int len=employees[id].subordinates.size();
        int sum=employees[id].importance;
        for(int i=0;i<len;i++)
        {
             sum=sum+employees[employees[id].subordinates(i)].importance;
        }
        return sum;
    }
}

对上面代码进行修改，因为题目给的员工的id不一定是按照顺序给的，所以我们需要遍历List,取List中的id和给的id做比较，然后再访问下属。

重新整理一下思路：huangfei

                            本题是让求重要性，那么一个老板可以有好多下属，下属可能还有下属，这些都要算重要性。

                 首先，我们先找到给的id的员工，这个员工可能有下属，找这个员工的下属，找到下属后，下属可能还存在下属，直到找到最后一个员工没有下属为止，把所有员工的重要性加载一起，就是题目所求的。

       这里特别像树的结构，一个节点下面存在孩子，孩子可能还存在孩子，遍历到孩子节点，把所有节点的重要性全加一起。这里我采用层次遍历，遍历员工的Id,进队列，在节点出队列时，把节点的重要性加起来，并把当前节点的下属进队列。

class Solution {
    public int getImportance(List<Employee> employees, int id) {
    Queue <Integer> queue=new LinkedList();
    int result=0;
    for(Employee e:employees)
    {
        if(e.id==id)
        {
         queue.add(id);
        }
    }
    while(!queue.isEmpty()){
            int len=queue.size();   
            for(int i=0;i<len;i++)
            {
                 int temp=queue.poll();
                 for(Employee e:employees)
                 {
                    if(e.id==temp)
                    {
                        result=result+e.importance;
                    for(Integer num:e.subordinates)
                    {
                        queue.add(num);
                    }
                    break;
                    } 
                    
                 }
            }

    }
return result;

    }
}

哈哈，虽然写的烂，但是好歹ac了。