【5.1】LeetCode每日一题· 员工的重要性

2021年05月01日 7时42分

标签： LeetCode 哈希表 dfs

## 题目描述
给定一个保存员工信息的数据结构，它包含了员工 唯一的 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, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。
```

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

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/employee-importance "题目链接")

## 解题思路
原来的数据结构不方便通过员工的id查找其重要度和所有的直系下属，因此首先使用哈希表建立`{员工id}->{重要度，{直系下属}}`的映射，这样所有的员工就形成了一棵有根树，对其进行深度优先搜索或者广度优先搜索即可。

注意题目要求的是某个员工和其所有**下属**的重要度之和，而非**直系下属**的重要度之和，一开始看错题目了导致了答案出错。

## 代码
```cpp
/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int dfs(unordered_map<int, pair<int, vector<int>>>& importance,int id){
        int res = importance[id].first;
        for(int& subordinate: importance[id].second){
            res += dfs(importance, subordinate);
        }
        return res;
    }
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, pair<int, vector<int>> > importance;
        Employee* target;
        int res = 0;
        for(Employee* employee: employees){
            importance[employee->id].first = employee->importance;
            importance[employee->id].second = employee->subordinates;
        }
        res = dfs(importance, id);
        return res;
        
    }
};
```

## 用时和内存
> 执行用时：32 ms，在所有 C++提交中击败了91.36%的用户
> 内存消耗：14.2 MB，在所有 C++提交中击败了46.93%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.1】LeetCode每日一题· 员工的重要性

所有评论

暂无评论

新增评论