Python 中的巢狀列表權重和 II

給定一個整數的巢狀列表，返回列表中所有整數的和，其權重由其深度加權。每個元素要麼是一個整數，要麼是一個列表——其元素也可能是整數或其他列表。與權重從根到葉不斷增加的前一個問題不同，現在的權重是從下向上定義的。即葉級整數的權重為 1，而根級整數的權重最大。

因此，如果輸入類似於 [[1,1],2,[1,1]]，那麼輸出將為 8，因為四個 1 的深度為 1，一個 2 的深度為 2。

為了解決這個問題，我們將按照以下步驟進行 −

  • 定義一個函式 depthSumInverse()。這將採用 nestedList

  • flats: 新列表

  • maxd: 0

  • 定義一個函式 flatten()。這將採用 nlst,dist

  • dist := dist + 1

  • maxd: maxd 的最大值，dist

  • 對於 nlst 中的每個節點，執行

    • 如果節點是一個非零的整數，則

      • 在 flats 的末尾插入 (node,dist)

    • 否則

      • flatten(node, dist)

  • flatten(nestedList, 0)

  • summ: 0

  • 對於 flats 中的每個 v,d，執行

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

  • 返回 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

更新時間： 19-11-2020

243 次瀏覽

開啟您的 職業生涯

完成課程即可獲得認證

開始
廣告