LeetCode 339 Nested List Weight Sum

LeetCode

<div>

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:

<pre>Input: nestedList = [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1. 12 + 12 + 21 + 12 + 1*2 = 10. </pre>

Example 2:

<pre>Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 11 + 42 + 6*3 = 27.</pre>

Example 3:

<pre>Input: nestedList = [0] Output: 0 </pre>

Constraints:

• 1 <= nestedList.length <= 50
• The values of the integers in the nested list is in the range [-100, 100].
• The maximum depth of any integer is less than or equal to 50.

</div>

题目大意：

求NestedInteger的和。越深，权重越高

最后计算权重解题思路(推荐)：

BFS按层遍历

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack LeetCode 339 Nested List Weight Sum - BFS LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

N/A

注意事项：

1. Line 9中，需要将NestedInteger展开，里面的所有的NestedInteger入列。Python中，用extend来加入list中所有元素到另一个list，而不是append
2. 按层遍历模板中，不需要level变量，for可以达到。

Python代码：

def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (i + 1)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数

---

每层计算权重算法II解题思路：

Python代码：

def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	res, layer = 0, 1
	while queue:
		level_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if not node.isInteger():
				queue.extend(node.getList()) # remember
			else:
				level_sum += node.getInteger()
		res += level_sum * layer
		layer += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k)