Tổng trọng lượng danh sách lồng nhau II bằng Python

Cho một danh sách các số nguyên lồng nhau, trả về tổng của tất cả các số nguyên trong danh sách có trọng số theo độ sâu của chúng. Mỗi phần tử là một số nguyên hoặc một danh sách - các phần tử của chúng cũng có thể là số nguyên hoặc danh sách khác. Khác với câu hỏi trước đó là trọng lượng tăng dần từ gốc đến lá, bây giờ trọng lượng được xác định từ dưới lên. tức là các số nguyên cấp độ lá có trọng số 1 và các số nguyên cấp độ gốc có trọng số lớn nhất.

Vì vậy, nếu đầu vào giống như [[1,1], 2, [1,1]], thì đầu ra sẽ là 8, như bốn số 1 ở độ sâu 1, một 2 ở độ sâu 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hàm deepSumInverse (). Thao tác này sẽ có Danh sách lồng nhau

• căn hộ:=một danh sách mới

• maxd:=0

• Định nghĩa một hàm flatten (). Điều này sẽ mất nlst, dist

• dist:=dist + 1

• maxd:=tối đa của maxd, dist

• đối với mỗi nút trong nlst, thực hiện

  • nếu nút là một số nguyên khác 0, thì

    • insert (node, dist) vào cuối căn hộ

  • nếu không,

    • làm phẳng (node, dist)

• làm phẳng (Danh sách lồng nhau, 0)

• tổng:=0

• đối với mỗi v, d trong căn hộ, thực hiện

  • sum:=summ + v * (maxd + 1-d)

• trả về tổng

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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