LC-Employee Importance

#coding:utf-8 # Employee info class Employee(object): 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(object): def getImportance(self, employees, id): """ :type employees: Employee :type id: int :rtype: int """ emap = {e.id: e for e in employees} #字典的运用 def dfs(eid): #深度优先搜索 employee = emap[eid] return (employee.importance + sum(dfs(eid) for eid in employee.subordinates)) return dfs(id) e1 = Employee(1, 5, [2, 3]) e2 = Employee(2, 3, []) e3 = Employee(3, 3, []) employee = [e1,e2,e3] Sol = Solution() print Sol.getImportance(employee, 1)

0，算法是官方给出的算法。 1，首先，是利用hashmap的方法，创建了一个字典。这个字典中，每一个id对应着一个对象，也就是： {employee.id -> employee}。构建的方式值得注意。 2，其次，就是dfs的使用。这里用到的深度优先搜索的方法，递归地得到所有的雇员的important值的和。在处理此类问题是，可以直接在函数里写一个dfs函数，方便进行迭代。