690.员工的重要性

目标

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

给定一个员工数组 employees，其中：

• employees[i].id 是第 i 个员工的 ID。
• employees[i].importance 是第 i 个员工的重要度。
• employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。

给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。

示例 1：

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

示例 2：

输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5
输出：-3
解释：员工 5 的重要度为 -3 并且没有直接下属。因此，员工 5 的总重要度为 -3。

说明：

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• 所有的 employees[i].id 互不相同。
• -100 <= employees[i].importance <= 100
• 一名员工最多有一名直接领导，并可能有多名下属。
• employees[i].subordinates 中的 ID 都有效。

思路

有一个数据结构 Employee，属性有 id、重要性、下属id集合。现在要查找给定id员工的重要性，即自身及下属的重要性之和。

直接使用map映射id与员工对象，使用dfs或者bfs搜索并累加重要性即可。

代码

/**
 * @date 2024-08-26 14:59
 */
public class GetImportance690 {
    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }

    public int getImportance(List<Employee> employees, int id) {
        Employee root = null;
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        int res = 0;
        Queue<Employee> q = new ArrayDeque<>(employees.size());
        q.offer(map.get(id));
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Employee node = q.poll();
                res += node.importance;
                for (Integer subordinate : node.subordinates) {
                    q.offer(map.get(subordinate));
                }
            }
        }
        return res;
    }
}

性能