ให้แสดงรายการจำนวนเต็มที่ซ้อนกัน ให้ส่งคืนผลรวมของจำนวนเต็มทั้งหมดในรายการที่ถ่วงน้ำหนักตามความลึก แต่ละองค์ประกอบอาจเป็นจำนวนเต็มหรือรายการ ซึ่งองค์ประกอบอาจเป็นจำนวนเต็มหรือรายการอื่นๆ ด้วย ต่างจากคำถามก่อนหน้านี้ที่น้ำหนักเพิ่มขึ้นจากรากสู่ใบ ตอนนี้น้ำหนักถูกกำหนดจากล่างขึ้นบน กล่าวคือ จำนวนเต็มระดับใบมีน้ำหนัก 1 และจำนวนเต็มระดับรากจะมีน้ำหนักมากที่สุด
ดังนั้น หากอินพุตเป็นเหมือน [[1,1],2,[1,1]] เอาต์พุตจะเป็น 8 เช่นเดียวกับ 4 ตัวที่ความลึก 1 ตัวที่ 2 ที่ความลึก 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน deepSumInverse() นี่จะใช้ nestedList
-
แฟลต:=รายการใหม่
-
maxd:=0
-
กำหนดฟังก์ชัน flatten() นี่จะใช้เวลา nlst,dist
-
dist :=dist + 1
-
maxd:=สูงสุดของ maxd, dist
-
สำหรับแต่ละโหนดใน nlst ให้ทำ
-
ถ้าโหนดเป็นจำนวนเต็มไม่เป็นศูนย์ ดังนั้น
-
แทรก (node,dist) ที่ส่วนท้ายของแฟลต
-
-
มิฉะนั้น
-
แผ่(โหนด, dist)
-
-
-
แบน (nestedList, 0)
-
ผลรวม:=0
-
สำหรับแต่ละ v,d ในแฟลต ทำ
-
summ :=summ + v*(maxd+1-d)
-
-
ผลตอบแทนรวม
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
