【MEDIUM】Nested List Weight Sum II

发布于: 2019-03-01 18:18
阅读: 15
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/nested-list-weight-sum-ii/

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.

分析过程

  • 输入:一个嵌套的数组
  • 输出:加权和,权值是该层离叶子节点的层数
  • 思路:由于遍历时不知道自己离叶节点有多远,因此不知道权值,没法直接加。因此需要遍历时把每一层的数字都累加起来放到一个数组,遍历完成以后就能确定每一层的权值了,最后加权求和。

解决方法

class Solution {
    func _depthSumInverse(_ nestedList: [NestedInteger], level: Int, output: inout [Int]) {
        for i in nestedList {
            if i.isInteger() {
                while output.count <= level {
                    output.append(0)
                }
                output[level] += i.getInteger()
            } else {
                _depthSumInverse(i.getList(), level: level + 1, output: &output)
            }
        }
    }
    
    func depthSumInverse(_ nestedList: [NestedInteger]) -> Int {
        var levelSum = [Int]()
        
        _depthSumInverse(nestedList, level: 0, output: &levelSum)
        
        var sum = 0
        
        for (i, value) in levelSum.enumerated() {
            sum += value * (levelSum.count - i)
        }
        
        return sum
    }
}

Thanks for reading.

All the best wishes for you! 💕