364. Nested List Weight SumII

xeblog 发布于2019-08-14 14:16 / 2689人阅读

摘要：题目解答这一题其实挺的，如果说第一道题的关键是记录层次，那么这一题的关键是把这一层的传到下一层去，代码如下关键点在于把上一层的传到下一层去，这样的话，接下来还有几层，每一层都会加上这个也就等于乘以了它的层数

题目：
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:
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; 13 + 42 + 6*1 = 17)

解答：
这一题其实挺tricky的，如果说第一道题的关键是记录层次，那么这一题的关键是把这一层的integer sum传到下一层去，代码如下：

public int DFS(List nestedList, int intSum) {
    //关键点在于把上一层的integer sum传到下一层去，这样的话，接下来还有几层，每一层都会加上这个integer sum,也就等于乘以了它的层数
    List nextLevel = new ArrayList<>();
    int listSum = 0;
    for (NestedInteger list : nestedList) {
        if (list.isInteger()) {
            intSum += list.getInteger();
        } else {
            nextLevel.addAll(list.getList());
        }
    }
    listSum = nextLevel.isEmpty() ? 0 : DFS(nextLevel, intSum);
    return listSum + intSum;
}

public int depthSumInverse(List nestedList) {
    return DFS(nestedList, 0);
}

GPU云服务器云服务器 SumII Nested Weight Nested-Loop

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64916.html

[LeetCode] 339. Nested List Weight Sum

Problem 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 othe...

骞讳护 2019-08-16 13:50 评论0 收藏0
[Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

摘要：解题思路题目要求两个数和等于，返回其题目说明不会有重复情况，所以我们一旦发现符合情况的，就可以直接结束循环并返回。特殊情况就是正好等于，那肯定是最接近的情况，直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...

EddieChan 2019-08-19 10:45 评论0 收藏0
【刘杰良】使用RPC接口新建EOS账户 - 实战

摘要：适用于最新的前言最近在研究的，但是由于官方文档的不够详尽，新建账号这一个操作就折腾了一个多星期。皇天不负有心人，终于调通了新建账号，代币转账也轻松解决。适用于最新的 EOS Dawn 4.0/4.1 前言最近在研究 EOS 的 RPC API，但是由于官方API文档的不够详尽，新建账号（new account）这一个操作就折腾了一个多星期。皇天不负有心人，终于调通了新建账号，代币转...

Little_XM 2019-06-27 18:52 评论0 收藏0
Sass 学习笔记

摘要：有利于版权等关键信息的保留。变量后加上则变为全局变量。字符串运算符根据左边的字符判断最终结构是否有引号。若使用，则两个类必须同时使用，增加维护负担。一组重用的使用引入，可携带参数。 1. 什么是Sass css预处理器，帮助你书写更简单、可维持的css。 2. Sass的特征变量（variable）帮助你存储需要重复使用的值；嵌套（nesting）让你书写更少的选择器； par...

lingdududu 2019-08-30 13:20 评论0 收藏0