【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,求带权和,权值为该节点的高度,叶子节点高度算。由于一个节点的高度是无法事先知道的,所以用BFS做会方便些。这里有一个技巧,每次计算本层数字的和的时候,不要把之前算的和清空,而要累加上去(有一点前缀和的意味)。
举个例子,如果第一层遍历的数字是,那么第一层的和是,接下来遍历第二层,比如第二层数字是,此时算和的时候,要把之前的和带着一起累加,累加出”前两层的和“,也就是,最后的答案就是算完每层后,所有的前缀和的累加。很显然叶子节点只加了一次,倒数第二层累加了两次,以此类推。这样就能算出来了。
代码如下:
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();
}
时间复杂度,空间。为节点总数。