LeetCode 第 690 号問題：員工的重要性

公衆号「五分鐘學算法」

​

題目來源于 LeetCode 第 690 号問題：員工的重要性。

題目描述

給定一個儲存員工資訊的資料結構，它包含了員工唯一的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:

輸入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
輸出: 11
解釋:
員工 1 自身的重要度是 5，他有兩個直系下屬 2 和 3 ，而且 2 和 3 的重要度均為 3 。是以員工 1 的總重要度是 5 + 3 + 3 = 11。      

注意:

1. 一個員工最多有一個直系上司，但是可以有多個直系下屬
2. 員工數量不超過 2000。

題目解析

利用哈希表來存儲員工的資訊，找到指定 id 的員工後，采用廣度優先周遊算法來周遊編号為 id 的員工及其下屬員工。

動畫描述

待補充

代碼實作

public int getImportance(List<Employee> employees, int id) {
        Employee emp = null;
        //重要度
        int sum = 0;   
        //存儲員工資訊
        HashMap<Integer,Employee> map=new HashMap<Integer,Employee>();  /
        for(Employee e:employees) {
            map.put(e.id, e);
        }
        //使用廣度優先周遊員工
        ArrayDeque<Employee> queue=new ArrayDeque<Employee>();
        queue.addLast(map.get(id));
        while(!queue.isEmpty()) {
            emp=queue.removeFirst();
            sum+=emp.importance;
            for(int i:emp.subordinates) {
                queue.addLast(map.get(i));
            }
        }
        return sum;

    }