題目

難度：★★☆☆☆
類型：樹結(jié)構(gòu)，智力題

給定一個(gè)保存員工信息的數(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的一個(gè)下屬，但是由于并不是直系下屬，因此沒有體現(xiàn)在員工1的數(shù)據(jù)結(jié)構(gòu)中。

現(xiàn)在輸入一個(gè)公司的所有員工信息，以及單個(gè)員工id，返回這個(gè)員工和他所有下屬的重要度之和。

注意
一個(gè)員工最多有一個(gè)直系領(lǐng)導(dǎo)，但是可以有多個(gè)直系下屬
員工數(shù)量不超過2000。

示例

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

解答

為了便于編碼，我們首先構(gòu)建了重要性字典和下屬字典，每一個(gè)員工的重要性及下屬都可以通過這兩個(gè)字典快速查看。此外，我們使用隊(duì)列結(jié)構(gòu)（這在樹的層次遍歷中非常常見）構(gòu)建函數(shù)，獲得某一個(gè)員工的所有下屬的id。最后，通過將所有下屬的重要性進(jìn)行求和，我們就可以快速尋找到某一個(gè)員工及其下屬的總重要性。

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]                            # 申請隊(duì)列
            while queue:                            # 只要隊(duì)列不為空
                staff = queue.pop(0)                # 隊(duì)尾元素出隊(duì)
                all_staff.append(staff)             # 結(jié)果加入到結(jié)果列表中
                queue.extend(subordinates[staff])   # 該員工的下屬批量入隊(duì)
            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ū)留言~