requirements

NestedList gives you a nestedList of integers, where each element is either an integer or a list (and each element in the list is also an integer or a list).

The depth of an integer depends on how many lists it is inside. For example, the value of each integer in the nested list [1,[2,2],[[3],2],1] is equal to its depth. Let maxDepth be the maximum depth of any integer.

The weight of the integer is maxDepth – (the depth of the integer) + 1.

Return the weighted sum by multiplying and summing each integer in the nestedList list.

Example 1:

Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1s at depth 1 and one 2 at depth 2. 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8Copy the code

Example 2:

Input: nestedList = [1,[4,[6]] Output: 17 Explanation: a 1 at depth 3, a 4 at depth 2, and a 6 at depth 1. 1 times 3 plus 4 times 2 plus 6 times 1 is 17Copy the code

The core code

# "" "
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# "" "
#class NestedInteger:
# def __init__(self, value=None):
# "" "
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# "" "
#
# def isInteger(self):
# "" "
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# "" "
#
# def add(self, elem):
# "" "
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# "" "
#
# def setInteger(self, value):
# "" "
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# "" "
#
# def getInteger(self):
# "" "
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# "" "
#
# def getList(self):
# "" "
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# "" "
class Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) - >int:
        record = [0 for _ in range(10000)]
        res = 0
        self.max_weight = 0
        def work(weight,l) :
            self.max_weight = max(weight,self.max_weight)
            if l.isInteger():
                record[weight] += l.getInteger()
            else:
                for item in l.getList():
                    work(weight + 1,item)
        
        for item in nestedList:
            work(1,item)
        
        for i in range(1,self.max_weight+1):
            res += (self.max_weight + 1 -i ) * record[i]
        return res
Copy the code

Answer: This problem is similar to our 339 questions, have the same problem solving technique, it is but we need our own maintenance a weight and number of dictionary, pay attention to the work function of the two, first, get the deepest level, depth and value, the second is to make a dictionary, met, added directly, meet the list, We can directly recursive cycle processing, and finally pay attention to the formula of weight calculation, the data can be calculated.