Pythonのネストされたリストの重みの合計II

整数のネストされたリストが与えられた場合、それらの深さで重み付けされたリスト内のすべての整数の合計を返します。各要素は整数またはリストのいずれかです。その要素は整数または他のリストでもかまいません。重みが根から葉へと増加している前の質問とは異なり、重みは下から上に定義されます。つまり、リーフレベルの整数の重みは1で、ルートレベルの整数の重みは最大です。

したがって、入力が[[1,1]、2、[1,1]]の場合、出力は8になり、深さ1に4つの1があり、深さ2に1つの2があります。

これを解決するには、次の手順に従います-

• 関数depthSumInverse（）を定義します。これにはnestedListが必要です

• フラット：=新しいリスト

• maxd：=0

• 関数flatten（）を定義します。これにはnlst、distが必要です

• dist：=dist + 1

• maxd：=maxd、distの最大値

• nlstのノードごとに、実行します

  • ノードが整数の場合、ゼロ以外の場合、

    • フラットの端に（node、dist）を挿入します

  • それ以外の場合

    • flatten（node、dist）

• flatten（nestedList、0）

• summ：=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