Leetcode: Nested List Weight Sum II
2024-09-26 15:53:20
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; 1*3 + 4*2 + 6*1 = 17)
Inspired by: https://discuss.leetcode.com/topic/49041/no-depth-variable-no-multiplication
Instead of multiplying by depth, add integers multiple times
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public 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
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
int weightedSum = 0, levelSum = 0;
while (!nestedList.isEmpty()) {
List<NestedInteger> nextLvl = new ArrayList<>();
for (NestedInteger ni : nestedList) {
if (ni.isInteger()) levelSum += ni.getInteger();
else nextLvl.addAll(ni.getList());
}
weightedSum += levelSum;
nestedList = nextLvl;
}
return weightedSum;
}
}
最新文章
- maven webapp栽坑录
- 及其简短的Splay代码
- STL中容器的push()或者push_back()函数的一点说明
- 【Aaronyang原创】用linq取出一个集合中重复的数据
- C++多态公有继承
- Jfinal中定时器的初步探索(二)
- iOS异常捕获
- Windows命令行(DOS命令)教程-4(转载)http://arch.pconline.com.cn//pcedu/rookie/basic/10111/15325_3.html
- 为何visua studio看不到C++项目的LOG?
- Java Servlet 笔记4
- 在虚拟机中搭建qduoj(一)——准备工作
- C++中int与string的转化
- install mysql from source and troubleshooting example
- spy++使用指南
- [Windows Azure] .NET Multi-Tier Application Using Storage Tables, Queues, and Blobs - 1 of 5
- glide从入门到精通使用
- 【Java】 剑指offer(49) 丑数
- jquery 获取 tagName(JQuery如何得到tagName?)
- 20155213 第十二周课堂作业MySort
- CSS3的新属性