LeetCode演算法題-Employee Importance(Java實現)
這是悅樂書的第291 次更新,第309 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第159題(順位題號是690)。定義員工資訊的資料結構,其中包括員工的唯一ID,他的重要性值以及他的直接下屬ID。例如,員工1是員工2的領導者,員工2是員工3的領導者。他們的重要性值分別為15,10和5。然後,員工1具有[1,15,[2]]等資料結構,員工2具有[2,10,[3]],員工3具有[3,5,[]]。請注意,雖然員工3也是員工1的下屬,但該關係不是直接的。現在,根據公司的員工資訊和員工ID,您需要返回該員工及其所有下屬的總重要性值。
輸入:[[1,5,[2,3]],[2,3,[]],[3,3,[]]],1
輸出:11
說明:員工1具有重要性值5,他有兩個直接下屬:員工2和員工3.他們都具有重要性值3.因此員工1的總重要性值是5 + 3 + 3 = 11。
注意:
-
一名員工最多隻有一名直接領導,但是可以有多名下屬。
-
最多員工人數不超過2000人。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
題目的意思是找到所給id員工的重要性以及所有下屬員工重要性之和,如果其下屬員工本身也有下屬,也要算進去,也就是說該問題的子問題還是問題本身。因此我們可以使用遞迴的方法。
先找到當前id所在的員工資訊和其下屬員工的id集合,我們將其下屬員工id放入HashSet中,然後再去遍歷所有員工集合,如果HashSet中包含當前員工的id,就累加上其重要值,然後對其下屬員工進行再處理,呼叫遞迴方法,最後返回sum。
/* // 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) { return helper(employees, id); } public int helper(List<Employee> employees, int id){ List<Integer> sub = null; int sum = 0; for (Employee em : employees) { if (em.id == id) { sub = em.subordinates; sum += em.importance; break; } } Set<Integer> set = new HashSet<Integer>(); for (Integer num : sub) { set.add(num); } for (Employee em : employees) { if (set.contains(em.id)) { sum += helper(employees, em.id); } } return sum; } }
03 第二種解法
我們可以對第一種解法再優化下,依舊使用遞迴,但是使用HashMap對初始員工資料進行處理,以id為key,以員工資訊為value。遞迴方法中,以id為引數,查詢當前id在HashMap中對應的員工資訊,定義一個sum變數,初始值為當前員工的重要性,遍歷當前員工的下屬員工id集合,呼叫遞迴方法本身,最後返回sum。
/* // 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 Map<Integer, Employee> map ; public int getImportance(List<Employee> employees, int id) { map = new HashMap<Integer, Employee>(); for (Employee em : employees) { map.put(em.id, em); } return helper(id); } public int helper(int id){ Employee em = map.get(id); int sum = em.importance; for (Integer num : em.subordinates) { sum += helper(num); } return sum; } }
04 第三種解法
我們也可以使用迭代的方式來處理,藉助佇列來實現,當然你也可以使用棧。依舊是將所有的員工資訊遍歷放入HashMap中,以id為key,以員工資訊為value。然後建立一個佇列,將引數id作為初始元素入佇列,接著對佇列中的資料進行處理,出佇列,然後使用id在HashMap中查詢對應的value,找到後,累加上其重要值,然後遍歷該員工的下屬,將下屬的id加入到佇列中去,一直迴圈處理,直到佇列為空。最後返回sum。
/* // 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> map = new HashMap<Integer, Employee>(); for (Employee em : employees) { map.put(em.id, em); } int sum = 0; Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(id); while (!queue.isEmpty()) { int temp = queue.poll(); Employee e = map.get(temp); sum += e.importance; for (Integer num : e.subordinates) { queue.offer(num); } } return sum; } }
05 小結
演算法專題目前已日更超過四個月 ,演算法題文章159 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!