给你一个整数嵌套列表 nestedList ，每一个元素要么是一个整数，要么是一个列表（这个列表中的每个元素也同样是整数或列表）。
整数的 深度 取决于它位于多少个列表内部。例如，嵌套列表 [1,[2,2],[[3],2],1] 的每个整数的值都等于它的 深度 。令 maxDepth 是任意整数的 最大深度 。
整数的 权重 为 maxDepth - (整数的深度) + 1 。
将 nestedList 列表中每个整数先乘权重再求和，返回该加权和。
示例 1：
输入：nestedList = [[1,1],2,[1,1]] 输出：8 解释：4 个 1 在深度为 1 的位置， 一个 2 在深度为 2 的位置。 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
示例 2：
输入：nestedList = [1,[4,[6]]] 输出：17 解释：一个 1 在深度为 3 的位置， 一个 4 在深度为 2 的位置，一个 6 在深度为 1 的位置。 1*3 + 4*2 + 6*1 = 17
提示：
1 <= nestedList.length <= 50- 嵌套列表中整数的值在范围
[-100, 100] - 任意整数的最大 深度 小于等于
50
先求序列的最大深度 depth，然后利用 DFS 累加求和。
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
def max_depth(nestedList):
depth = 1
for item in nestedList:
if item.isInteger():
continue
depth = max(depth, max_depth(item.getList()) + 1)
return depth
def dfs(nestedList, max_depth):
depth_sum = 0
for item in nestedList:
if item.isInteger():
depth_sum += item.getInteger() * max_depth
else:
depth_sum += dfs(item.getList(), max_depth - 1)
return depth_sum
depth = max_depth(nestedList)
return dfs(nestedList, depth)/**
* // 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 empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
int depth = maxDepth(nestedList);
return dfs(nestedList, depth);
}
private int maxDepth(List<NestedInteger> nestedList) {
int depth = 1;
for (NestedInteger item : nestedList) {
if (item.isInteger()) {
continue;
}
depth = Math.max(depth, 1 + maxDepth(item.getList()));
}
return depth;
}
private int dfs(List<NestedInteger> nestedList, int depth) {
int depthSum = 0;
for (NestedInteger item : nestedList) {
if (item.isInteger()) {
depthSum += item.getInteger() * depth;
} else {
depthSum += dfs(item.getList(), depth - 1);
}
}
return depthSum;
}
}/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* @return {boolean}
* this.isInteger = function() {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* @return {integer}
* this.getInteger = function() {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* @return {void}
* this.setInteger = function(value) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* @return {void}
* this.add = function(elem) {
* ...
* };
*
* Return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
* @return {NestedInteger[]}
* this.getList = function() {
* ...
* };
* };
*/
/**
* @param {NestedInteger[]} nestedList
* @return {number}
*/
var depthSumInverse = function (nestedList) {
const maxDepth = nestedList => {
let depth = 1;
for (const item of nestedList) {
if (item.isInteger()) {
continue;
}
depth = Math.max(depth, 1 + maxDepth(item.getList()));
}
return depth;
};
const dfs = (nestedList, depth) => {
let depthSum = 0;
for (const item of nestedList) {
if (item.isInteger()) {
depthSum += item.getInteger() * depth;
} else {
depthSum += dfs(item.getList(), depth - 1);
}
}
return depthSum;
};
const depth = maxDepth(nestedList);
return dfs(nestedList, depth);
};