題目
難度：★★☆☆☆
類型：樹結(jié)構(gòu)，智力題
給定一個保存員工信息的數(shù)據(jù)結(jié)構(gòu)严就，它包含了員工唯一的id，重要度 和 直系下屬的id泉粉。
比如卵慰，員工1是員工2的領(lǐng)導(dǎo)沙郭，員工2是員工3的領(lǐng)導(dǎo)。他們相應(yīng)的重要度為15, 10, 5呵燕。那么員工1的數(shù)據(jù)結(jié)構(gòu)是[1, 15, [2]]棠绘，員工2的數(shù)據(jù)結(jié)構(gòu)是[2, 10, [3]]件相，員工3的數(shù)據(jù)結(jié)構(gòu)是[3, 5, []]再扭。注意雖然員工3也是員工1的一個下屬氧苍，但是由于并不是直系下屬，因此沒有體現(xiàn)在員工1的數(shù)據(jù)結(jié)構(gòu)中泛范。
現(xiàn)在輸入一個公司的所有員工信息让虐，以及單個員工id，返回這個員工和他所有下屬的重要度之和罢荡。
注意
一個員工最多有一個直系領(lǐng)導(dǎo)赡突，但是可以有多個直系下屬
員工數(shù)量不超過2000。
示例
輸入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
輸出: 11
解釋:
員工1自身的重要度是5区赵，他有兩個直系下屬2和3惭缰，而且2和3的重要度均為3。因此員工1的總重要度是 5 + 3 + 3 = 11笼才。
解答
為了便于編碼漱受，我們首先構(gòu)建了重要性字典和下屬字典，每一個員工的重要性及下屬都可以通過這兩個字典快速查看骡送。此外昂羡，我們使用隊列結(jié)構(gòu)（這在樹的層次遍歷中非常常見）構(gòu)建函數(shù)，獲得某一個員工的所有下屬的id摔踱。最后虐先，通過將所有下屬的重要性進行求和，我們就可以快速尋找到某一個員工及其下屬的總重要性派敷。
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 Solution:
def getImportance(self, employees, id):
"""
:type employees:
:type id: int
:rtype: int
"""
importance = {e.id: e.importance for e in employees} # 重要性字典{員工: 重要性}
subordinates = {e.id: e.subordinates for e in employees} # 下屬字典{員工: 下屬列表}
def get_subordinates(id): # 獲得員工的直接與間接下屬
all_staff = [] # 結(jié)果列表
queue = [id] # 申請隊列
while queue: # 只要隊列不為空
staff = queue.pop(0) # 隊尾元素出隊
all_staff.append(staff) # 結(jié)果加入到結(jié)果列表中
queue.extend(subordinates[staff]) # 該員工的下屬批量入隊
return all_staff # 返回最終員工數(shù)量
return sum([importance[staff] for staff in get_subordinates(id)]) # 將所有下屬的重要性求和
if __name__ == "__main__":
employees_data = [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]]
employees = [Employee(e[0], e[1], e[2]) for e in employees_data]
s = Solution()
print(s.getImportance(employees, 1))
如有疑問或建議蛹批，歡迎評論區(qū)留言~
