Nested List Weight Sum II trong Python

Mô tả bài toán

Cho danh sách lồng nhau các số nguyên. Tính tổng có trọng số của tất cả số nguyên, trong đó trọng số được xác định từ dưới lên (bottom-up): các số ở độ sâu lá có trọng số 1, gốc có trọng số lớn nhất.

Ví dụ: [[1,1],2,[1,1]] → đầu ra 8 (bốn số 1 ở độ sâu 1, một số 2 ở độ sâu 2).

Giải thuật (Làm phẳng + Tính độ sâu tối đa)

1. Định nghĩa hàm flatten(nlst, dist):
   • Tăng dist, cập nhật maxd.
   • Duyệt qua các phần tử: nếu là số nguyên, lưu cặp (giá trị, dist) vào danh sách flats; nếu là danh sách, gọi đệ quy.
2. Gọi flatten(nestedList, 0).
3. Tính tổng: summ += v * (maxd + 1 - d) cho mỗi cặp (v, d) trong flats.
4. Trả về summ.

Ví dụ mã Python

class Solution(object):
    def depthSumInverse(self, nestedList):
        flats = []
        self.maxd = 0
        def flatten(nlst, dist):
            if isinstance(nlst, list):
                nlst = nlst
            dist += 1
            self.maxd = max(self.maxd, dist)
            for node in nlst:
                if isinstance(node, int):
                    flats.append((node, dist))
                else:
                    flatten(node, dist)
        flatten(nestedList, 0)
        summ = 0
        for v, d in flats:
            summ += v * (self.maxd + 1 - d)
        return summ

ob = Solution()
print(ob.depthSumInverse([[1,1],2,[1,1]]))

Đầu vào

[[1,1],2,[1,1]]

Đầu ra

8