题目描述

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

样例

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

算法1

(DFS) $O(n)$

对数组里每个元素进行dfs，将数值累加值记录在arr数组的i序号中，如果该元素不是单个数值，对其list的每个元素进行下一层（i+1）dfs. 最后对arr中各元素累加层数权重值得到输出答案。

时间，空间复杂度

每个元素遍历一次，所以时间复杂度为O（n）
用arr记录每层数组的累加值，空间复杂度最坏情况为O（n）

参考文献

C++ 代码

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        vector<int> arr;
        for(auto node:nestedList)
            dfs(node, 0, arr);

        int res=0, n=arr.size();
        for(int i=n-1, level=1; i>=0; i--, level++)
        {
            res+=arr[i]*level;
        }
        return res;
    }

    void dfs(NestedInteger& node,int i, vector<int> &arr )
    {
        if(arr.size()<i+1) arr.resize(i+1);

        if(node.isInteger())
        {
            arr[i]+=node.getInteger();
        }
        else
        {
            for(auto l: node.getList())
                dfs(l, i+1, arr);
        }                

    }
};

算法2

(BFS) $O(n)$

层序遍历，将当前层的数累加至subsum，嵌套的数放入tmp数组，在while循环的最后将subsum累加到sum，并用tmp update原数组，直到数组为空终止循环。

时间，空间复杂度

每个元素遍历一次，所以时间复杂度为O（n）
用tmp记录每个嵌套数，空间复杂度最坏情况为O（n）

参考文献

C++ 代码

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int sum=0, subsum=0;
        while(!nestedList.empty())
        {
            vector<NestedInteger> tmp;
            for(auto node: nestedList)
            {                
                if(node.isInteger())
                    subsum+=node.getInteger();
                else
                {
                    for(auto list: node.getList())
                        tmp.push_back(list);
                }
            }
            sum+=subsum;
            nestedList=tmp;
        }
        return sum;
    }
};