首页 > itarticle > 算法笔记: 力扣#690 员工的重要性

算法笔记: 力扣#690 员工的重要性

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

"""
# Employee info
class Employee:
    def __init__(self, id, importance, subordinates):
        # It's the unique id of each node.
        # unique id of this employee
        self.id = id
        # the importance value of this employee
        self.importance = importance
        # the id of direct subordinates
        self.subordinates = subordinates
"""
class :
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        id2employee = {e.id : e for e in employees}
        def dfs(i):
            employee = id2employee[i]
            return employee.importance + sum(dfs(s_id) for s_id in employee.subordinates)
        return dfs(id)

Java 实现

// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class  {
    private Map<Integer, Employee> id2employee = new HashMap<>();
    
    private int dfs(int id){
        Employee employee = id2employee.get(id);
        int ans = employee.importance;
        for(int i : employee.subordinates){
            ans += dfs(i);
        }
        return ans;
    }
    
    public int getImportance(List<Employee> employees, int id) {
        for(Employee e : employees){
            id2employee.put(e.id, e);
        }
        return dfs(id);
    }
}

时间复杂度

O(n).

空间复杂度

O(n).

链接

690. Employee Importance
690. 员工的重要性
 (English version) Algorithm Notes: Leetcode#690 Employee Importance