欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Lintcode】905. Nested List Weight Sum II

程序员文章站 2022-05-23 21:46:54
...

题目地址:

https://www.lintcode.com/problem/nested-list-weight-sum-ii/description

给定一个NestedInteger的类,定义可以参照https://blog.csdn.net/qq_46105170/article/details/104337870。现在给定一个NestedInteger的list,求带权和,权值为该节点的高度,叶子节点高度算11。由于一个节点的高度是无法事先知道的,所以用BFS做会方便些。这里有一个技巧,每次计算本层数字的和的时候,不要把之前算的和清空,而要累加上去(有一点前缀和的意味)。

举个例子,如果第一层遍历的数字是(1,2)(1,2),那么第一层的和是33,接下来遍历第二层,比如第二层数字是(3,4,5)(3,4,5),此时算和的时候,要把之前的和33带着一起累加,累加出”前两层的和“,也就是1515,最后的答案就是算完每层后,所有的前缀和的累加。很显然叶子节点只加了一次,倒数第二层累加了两次,以此类推。这样就能算出来了。

代码如下:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    /**
     * @param nestedList: a list of NestedInteger
     * @return: the sum
     */
    public int depthSumInverse(List<NestedInteger> nestedList) {
        // Write your code here.
        // 判空
        if (nestedList == null || nestedList.isEmpty()) {
            return 0;
        }
        // 开一个队列,存储每一层的NestedInteger
        Queue<NestedInteger> queue = new LinkedList<>();
        // 先存储第0层的所有节点
        for (NestedInteger nestedInteger : nestedList) {
            queue.offer(nestedInteger);
        }
        
        int res = 0, prefSum = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                NestedInteger integer = queue.poll();
                // 如果遇到数,就累加前缀和,否则把该nestedInteger的List里的所有节点入队
                if (integer.isInteger()) {
                    prefSum += integer.getInteger();
                } else {
                    for (NestedInteger nestedInteger : integer.getList()) {
                        queue.offer(nestedInteger);
                    }
                }
            }
            // 累加前缀和
            res += prefSum;
        }
        
        return res;
    }
}

interface NestedInteger {
    // @return true if this NestedInteger holds a single integer,
    // rather than a nested list.
    boolean isInteger();
    
    // @return the single integer that this NestedInteger holds,
    // if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    Integer getInteger();
    
    // @return the nested list that this NestedInteger holds,
    // if it holds a nested list
    // Return null if this NestedInteger holds a single integer
    List<NestedInteger> getList();
    
}

时间复杂度O(n)O(n),空间O(n)O(n)nn为节点总数。