Giả sử ta có cấu trúc dữ liệu thông tin nhân viên, có id duy nhất của nhân viên, giá trị quan trọng của anh ta và id của cấp dưới trực tiếp. Ví dụ, nhân viên 1 là trưởng của nhân viên 2, và nhân viên 2 là trưởng của nhân viên 3. Giả sử giá trị quan trọng của họ lần lượt là 15, 10 và 5. Khi đó nhân viên 1 có cấu trúc dữ liệu như [1, 15, [2]], nhân viên 2 có [2, 10, [3]], và nhân viên 3 có [3, 5, []].
Vì vậy, nếu ta có thông tin nhân viên của một công ty, và một id nhân viên, ta cần tìm tổng giá trị quan trọng của nhân viên này và tất cả cấp dưới của anh ta.
Ví dụ, nếu đầu vào là [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1, thì đầu ra sẽ là 11, vì Nhân viên 1 có giá trị quan trọng 5, và có hai cấp dưới trực tiếp là Nhân viên 2 và 3. Cả hai đều có giá trị quan trọng 3. Vậy tổng giá trị quan trọng của Nhân viên 1 là 5 + 3 + 3 = 11.
Để giải quyết, ta thực hiện các bước sau:
- weight := một map mới, leader := một map mới
- Với mỗi e trong employees, thực hiện:
- weight[e[0]] := e[1]
- leader[e[0]] := e[2]
- res := 0
- res := res + weight[id]
- queue := leader[id]
- Khi queue khác rỗng, thực hiện:
- new_queue := một danh sách mới
- node := xóa phần tử cuối khỏi queue
- res := res + weight[node]
- Nếu leader[node] khác rỗng, thì:
- new_queue := new_queue + leader[kích thước leader]
- queue := queue + new_queue
- Trả về res
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution(object): def getImportance(self, employees, id): weight = {} leader = {} for e in employees: weight[e[0]] = e[1] leader[e[0]] = e[2] res = 0 res += weight[id] queue = leader[id] while queue: new_queue = [] node = queue.pop() res += weight[node] if leader[node]: new_queue += leader[node] queue += new_queue return res ob = Solution() print(ob.getImportance([[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1))Đầu vào
[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Đầu ra
11