Nested List Weight Sum II ใน Python

กำหนด nested list ของจำนวนเต็ม ต้องการหาผลรวมของทุกจำนวนถ่วงน้ำหนักตามความลึก แต่น้ำหนักนับจากใบขึ้นไปราก (bottom-up) คือ ใบมีน้ำหนัก 1 รากมีน้ำหนักมากที่สุด

ตัวอย่าง: [[1,1],2,[1,1]] ผลลัพธ์ 8 สี่ตัว 1 ที่ความลึก 1, ตัว 2 ที่ความลึก 2

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน depthSumInverse(nestedList)
2. flats = [], maxd = 0
3. ฟังก์ชัน flatten(nlst, dist):
   • dist += 1, อัปเดต maxd
   • วนแต่ละ node:
     • ถ้าเป็น int: เพิ่ม (node, dist) เข้า flats
     • มิฉะนั้น: เรียก flatten(node, dist)
4. เรียก flatten(nestedList, 0)
5. คำนวณ summ += v * (maxd + 1 - d) สำหรับทุก (v,d) ใน flats
6. คืน summ

ตัวอย่างโค้ด

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]]))

อินพุต

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

เอาต์พุต

8