EmployeeImportance [source code]

public class EmployeeImportance {
static
/******************************************************************************/
// 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 Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> lookupMap = preprocess (employees);
        return getImportance (id, lookupMap);
    }

    int getImportance (int id, Map<Integer, Employee> lookupMap) {
        int res = 0;
        if (lookupMap.containsKey (id)) {
            Employee e = lookupMap.get (id);
            res += e.importance;
            for (int idIter : e.subordinates)
                res += getImportance (idIter, lookupMap);
        }
        return res;
    }

    Map<Integer, Employee> preprocess (List<Employee> employees) {
        Map<Integer, Employee> resMap = new HashMap<>();
        for (Employee e : employees) {
            resMap.put (e.id, e);
        }
        return resMap;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        EmployeeImportance.Solution tester = new EmployeeImportance.Solution();
    }

    static 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;

        public Employee (int id, int importance, int[] subs) {
            this.id = id;
            this.importance = importance;
            this.subordinates = new ArrayList<> ();
            for (int i : subs)
                this.subordinates.add (i);
        }
    };
}

题目大概扫了一眼, 又是一个DFS的题目, 总体意思很简单, 而且题目还给了提示: 总数不超过2000, 意思是你用recursion来做的话, 不会爆栈;

犯了一点低级错误, 不过最后还是按时做出来了: 15ms (51%); 速度好像不怎么样, 不知道其他人是怎么做的;

editorial:

class Solution {  
    Map<Integer, Employee> emap;  
    public int getImportance(List<Employee> employees, int queryid) {  
        emap = new HashMap();  
        for (Employee e: employees) emap.put(e.id, e);  
        return dfs(queryid);  
    }  
    public int dfs(int eid) {  
        Employee employee = emap.get(eid);  
        int ans = employee.importance;  
        for (Integer subid: employee.subordinates)  
            ans += dfs(subid);  
        return ans;  
    }  
}

基本是一样的做法;

discussion里面的BFS做法, 反正还是要依赖于Map:

class Solution {  
    public int getImportance(List<Employee> employees, int id) {  
        int total = 0;  
        Map<Integer, Employee> map = new HashMap<>();  
        for (Employee employee : employees) {  
            map.put(employee.id, employee);  
        }  
        Queue<Employee> queue = new LinkedList<>();  
        queue.offer(map.get(id));  
        while (!queue.isEmpty()) {  
            Employee current = queue.poll();  
            total += current.importance;  
            for (int subordinate : current.subordinates) {  
                queue.offer(map.get(subordinate));  
            }  
        }  
        return total;  
    }  
}

discussion里面一个java8的做法:

class Solution {  
    int total = 0;  
    public int getImportance(List<Employee> employees, int id) {  
        Employee manager = employees.stream().filter(e -> e.id == id).collect(Collectors.toList()).get(0);  
        total += manager.importance;  
        manager.subordinates.forEach(subId -> getImportance(employees, subId));  
        return total;  
    }  
}

慢城狗, 有时间再看;

基本没了, submission的最优解基本也都是波动;

Problem Description

You are given a data structure of employee information, which includes the employee's unique id, his importance value and his direct subordinates' id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1  
Output: 11  
Explanation:  
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

• One employee has at most one direct leader and may have several subordinates.
• The maximum number of employees won't exceed 2000.

Difficulty:Easy
Total Accepted:13.1K
Total Submissions:25K
Contributor:fallcreek
Companies
uber
Related Topics
hash tabledepth-first searchbreadth-first search
Similar Questions
Nested List Weight Sum