364.加权嵌套序列和II

364.加权嵌套序列和II

题目大意:与339. Nested List Weight Sum反过来,求嵌套数组的加权和,只不过权重是和深度反过来,最深一层权重为1.

Example 1:
Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)

Example 2:
Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)

解法一：

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        vector<int> record;  //记录表
        for (auto nl : nestedList) {
            dfs(nl, 0, record);
        }
        int sum = 0;
        //反向遍历求加权
        for (int i = record.size()-1, level = 1; i >= 0; i--, level++) {
            sum += level * record[i];
        }
        return sum;
    }
    void dfs(NestedInteger &nestedList, int depth, vector<int>& record) {
        if (record.size() < depth+1) record.resize(depth+1);  //record按需扩张
        if (nestedList.isInteger()) {
            record[depth] += nestedList.getInteger();  //递归出口,记录该层数之和
        } else {
            for (auto nl : nestedList.getList()) {
               dfs(nl, depth+1, record); 
            }  
        }
    }
};

解法二：两遍dfs（暂时没想到直接递归的写法）

第一遍求出最大深度，第二遍dfs求加权和

# """
# 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:
        sum = 0
        maxDepth = self.depth(nestedList)    #求最大深度
        for n in nestedList:
            sum += self.dfs(n, maxDepth)
        return sum
    
    def depth(self, nestedList):
        total = 1   #记录最大深度，初始为1
        for l in nestedList:
            if not l.isInteger():   #若还有下一层
                total = max(total, self.depth(l.getList()) + 1)
        return total
    
    def dfs(self, nestedInt, depth):  #nestedInt为嵌套结构体，depth为当前深度
        if nestedInt.isInteger():   #递归出口
            return nestedInt.getInteger() * depth
        sum = 0
        for l in nestedInt.getList():
            sum += self.dfs(l, depth-1)
        return sum