0364：加权嵌套序列和 II（★）

力扣第 364 题

题目

给你一个整数嵌套列表 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

分析

类似 0339，只是递归过程中维护最大深度 maxDepth 和所有整数之和 total 即可。

解答

1
2
3
4
5
6
7
8
9

def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
	def dfs(nest, w):
		if nest.isInteger():
			self.total += nest.getInteger()
			self.w = max(self.w, w)
			return w*nest.getInteger()
		return sum(dfs(sub, w+1) for sub in nest.getList())
	self.total, self.w = 0, 0
	return -sum(dfs(nest, 1) for nest in nestedList)+(self.w+1)*self.total