2022.02.15_ Daily question leetcode six hundred and ninety

Title Description

690. The importance of employees

Given a data structure to store employee information , It includes employees Unique id , Importance and Direct subordinates id .

such as , staff 1 It's the employees 2 Leadership of , staff 2 It's the employees 3 Leadership of . Their corresponding importance is 15 , 10 , 5 . So employees 1 The data structure is [1, 15, [2]] , staff 2 Of The data structure is [2, 10, [3]] , staff 3 The data structure is [3, 5, []] . Note that although employees 3 It's also employees 1 One of my subordinates , But because of Not directly subordinate , So it's not reflected in the employees 1 In the data structure of .

Now enter all the employee information of a company , And individual employees id , Return the sum of the importance of this employee and all his subordinates .

Example ：

Input ：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output ：11
explain ：
staff 1 The importance of oneself is 5 , He has two direct subordinates 2 and 3 , and 2 and 3 The importance of the two is 3 . So employees 1 The total importance of is 5 + 3 + 3 = 11 .

Tips ：

 An employee can have at most one   Directly   Leader , But there can be multiple   Directly   subordinate 
 No more than  2000 .

Ideas

Using recursion , Each time I traverse the set to find the corresponding id Equal employees ( have access to map For storage , It can reduce the time of traversing the array ), Accumulate their importance , And then on its Direct reports Continue accumulation again

【PS :】 You can also use breadth first search , Not yet ……（ Later learning ）

Code

class Solution {
    
    public int getImportance(List<Employee> employees, int id) {
    
       return f(employees, id, 0);
    }

    private int f(List<Employee> employees, int id, int res) {
    
        for (Employee employee : employees) {
    
            if (employee.id == id) {
    
                int len = employee.subordinates.size();
                res += employee.importance;
                for (int i = 0; i < len; i++) {
    
                    res += f(employees, employee.subordinates.get(i),0);
                }
                break;
            }
        }
        return res;
    }
}

---

class Solution {
    
     public int getImportance(List<Employee> employees, int id) {
    
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
    
            map.put(e.id,e);
        }
        return f(map, id, 0);
    }

    private int f(Map<Integer, Employee> map, int id, int res) {
    
        Employee e = map.get(id);
        res += e.importance;
        for (int i = 0; i < e.subordinates.size(); i++) {
    
            res += f(map, e.subordinates.get(i), 0);
        }
        return res;
    }
}

Running results