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

九章算法 | 亚马逊面试题:嵌套列表的加权和II

程序员文章站 2022-07-14 12:29:20
...

描述

给一个嵌套的整数列表, 返回列表中所有整数由它们的深度加权后的总和. 每一个元素可能是一个整数或一个列表(其元素也可能是整数或列表)。

注意,在之前的题目嵌套列表的加权和中,从根结点到叶子结点,深度权重是递增的。在嵌套列表的加权和II中,深度权重的定义是自下而上的,也就是说,最底层叶子结点的深度权重是1 ,根结点的深度权重最大。

在线评测地址

样例1

输入: nestedList = [[1,1],2,[1,1]]
输出: 8
解释:
四个深度为1的1,一个深度为2的2

样例2

输入: nestedList = [1,[4,[6]]]
输出: 17
解释:
一个深度为3的1, 一个深度为2的4,和一个深度为3的6。1*3 + 4*2 + 6*1 = 17

题解:

bfs遍历列表每一层,如果是数字,则加到当前这一层的和当中,反之,是列表,则进入队列,每一层遍历完,才进入下一层,最后将每一层的数值加到结果当中即可。

public class Solution {
    /**
     * @param nestedList: a list of NestedInteger
     * @return: the sum
     */
    public int depthSumInverse(List<NestedInteger> nestedList) {
         // corner case
         if(nestedList == null || nestedList.size() == 0) {
             return 0;
         }
          // initialize
         int preSum = 0;
         int result = 0;
         // put each item of list into the queue
         Queue<NestedInteger> queue = new LinkedList<>(nestedList);
         while(!queue.isEmpty()){
             //depends on different depth, queue size is changeable
             int size = queue.size();
             int levelSum = 0;
             for(int i = 0; i < size; i++){
                 NestedInteger n = queue.poll();
                 if(n.isInteger()){
                     levelSum += n.getInteger();
                 }
                 else{
                     // depends on different depth, queue size is changeable
                     queue.addAll(n.getList());
                 }
             }
             preSum += levelSum;
             result += preSum;
         }
         return result;
    }

}

更多题解参考