Medium

题目描述

给定一个保存员工信息的数据结构，它包含了员工唯一的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：

输入：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。

约束条件：

  • 1 <= employees.length <= 2000
  • 1 <= employees[i].id <= 2000
  • 所有的员工id都是唯一的
  • -100 <= employees[i].importance <= 100
  • 一个员工最多有一个直系领导，可能有多个直系下属
  • employees[i].subordinates中的id都是有效id

解题思路

这是一个典型的图遍历问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

解题思路：

首先，我们需要将员工数组转换为哈希表，以便能够快速通过员工id查找到对应的员工对象。这样可以避免每次查找员工时都要遍历整个数组。

然后，从指定的员工id开始，递归地计算该员工及其所有直接和间接下属的重要度总和。具体步骤如下：

  1. 建立映射关系：用哈希表存储员工id到员工对象的映射
  2. DFS遍历：从目标员工开始，递归访问所有下属
    • 将当前员工的重要度加入总和
    • 对每个直系下属递归调用相同的过程
    • 返回当前员工及其所有下属的重要度总和

两种常见解法：

  • DFS（推荐）：代码简洁，空间复杂度较低
  • BFS：使用队列进行层次遍历，思路清晰但需要额外队列空间

由于这道题目的数据规模不大，两种方法的性能差异不明显，但DFS的代码更简洁，因此推荐使用DFS解法。

代码实现

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> mp;
        for (Employee* emp : employees) {
            mp[emp->id] = emp;
        }
        
        return dfs(mp, id);
    }
    
private:
    int dfs(unordered_map<int, Employee*>& mp, int id) {
        Employee* emp = mp[id];
        int total = emp->importance;
        
        for (int subId : emp->subordinates) {
            total += dfs(mp, subId);
        }
        
        return total;
    }
};

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        emp_map = {emp.id: emp for emp in employees}
        
        def dfs(emp_id):
            emp = emp_map[emp_id]
            total = emp.importance
            
            for sub_id in emp.subordinates:
                total += dfs(sub_id)
            
            return total
        
        return dfs(id)

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public IList<int> subordinates;
}
*/

class Solution {
    public int GetImportance(IList<Employee> employees, int id) {
        Dictionary<int, Employee> empMap = new Dictionary<int, Employee>();
        foreach (Employee emp in employees) {
            empMap[emp.id] = emp;
        }
        
        return DFS(empMap, id);
    }
    
    private int DFS(Dictionary<int, Employee> empMap, int id) {
        Employee emp = empMap[id];
        int total = emp.importance;
        
        foreach (int subId in emp.subordinates) {
            total += DFS(empMap, subId);
        }
        
        return total;
    }
}

/**
 * Definition for Employee.
 * function Employee(id, importance, subordinates) {
 *     this.id = id;
 *     this.importance = importance;
 *     this.subordinates = subordinates;
 * }
 */

/**
 * @param {Employee[]} employees
 * @param {number} id
 * @return {number}
 */
var GetImportance = function(employees, id) {
    const empMap = new Map();
    for (const emp of employees) {
        empMap.set(emp.id, emp);
    }
    
    function dfs(empId) {
        const emp = empMap.get(empId);
        let total = emp.importance;
        
        for (const subId of emp.subordinates) {
            total += dfs(subId);
        }
        
        return total;
    }
    
    return dfs(id);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为员工总数，需要遍历所有相关员工一次
空间复杂度O(n)哈希表存储员工映射关系需要O(n)空间，递归调用栈最坏情况下为O(n)

相关题目