โครงสร้างพนักงาน: [id, importance, [subordinates]] ได้รายการพนักงานทั้งหมดและ id หนึ่ง ต้องการผลรวมความสำคัญของพนักงานคนนั้นและลูกน้องทุกระดับ (BFS/DFS)
ตัวอย่าง
employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id=1 → 5 + 3 + 3 = 11
ขั้นตอนการแก้ปัญหา (BFS)
- สร้าง dict
weight[id] = importance,leader[id] = subordinates - เริ่มจาก
idที่กำหนด ใช้คิว BFS - สะสม
importanceของแต่ละโหนดที่เยี่ยมชม - คืนผลรวม
การติดตั้งใน Python
class Solution:
def getImportance(self, employees, id):
weight = {e[0]: e[1] for e in employees}
subs = {e[0]: e[2] for e in employees}
total = 0
queue = [id]
while queue:
cur = queue.pop()
total += weight[cur]
queue.extend(subs[cur])
return total
ob = Solution()
print(ob.getImportance([[1,5,[2,3]],[2,3,[]],[3,3,[]]], 1)) # 11
อินพุต / เอาต์พุต
Input: [[1,5,[2,3]],[2,3,[]],[3,3,[]]], 1 Output: 11
