690. 员工的重要性

系统管理员 2022-10-21 01:26 138阅读 0赞

#### 2021-05-01 LeetCode 每日一题 ####

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

这里可以使用BFS/DFS去解题。因为我递归用的不怎么熟悉，所以选择用递推的方式。

因为题目提供的是员工的id，而我们需要计算员工的重要性，所以基本思路就是，先通过id拿到Employee，加入队列尾，每次循环，从队列头开始拿，直到队列为空，一次循环其实就相当于把某个员工的直接下属员工全部遍历了一遍。然后拿到该员工的直接下属员工，再加入队列尾。直到退出while循环即可。

/*
    // Definition for Employee.
    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    };
    */
    
    class Solution {
        public int getImportance(List<Employee> employees, int id) {
            int res = 0;
            Queue<Employee> queue = new LinkedList<>();
            queue.offer(getEmployee(employees, id));
    
            while (!queue.isEmpty()) {
                int len = queue.size();
                for (int i = 0; i < len; i++) {
                    Employee employee = queue.poll();
                    res += employee.importance;
    
                    for (Integer childId : employee.subordinates) {
                        queue.offer(getEmployee(employees, childId));
                    }
                }
            }
    
            return res;
        }
    
        private Employee getEmployee(List<Employee> employees, int id) {
            for (Employee e : employees) {
                if (e.id == id) {
                   return e;
                }
            }
    
            return null;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/3204dc470fbe4331abb852f15a2556b2.png