[LeetCode] 339. Nested List Weight Sum

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:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

Example 3:

Input: nestedList = [0]
Output: 0

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.

嵌套列表的权重和。

题意跟690题很类似，但是这个题不是在操作图的边，而是给你了一个嵌套列表，请你输出他们的权重和。

思路还是两种，BFS和DFS。建议可以先做一下690题，这道题也就可以迎刃而解了。

BFS

时间O(n) - list的长度

空间O(n) - queue

Java实现

 1 class Solution {
 2     public int depthSum(List<NestedInteger> nestedList) {
 3         // corner case
 4         if (nestedList == null) {
 5             return 0;
 6         }
 7 
 8         // normal case
 9         int depth = 1;
10         int res = 0;
11         Queue<NestedInteger> queue = new LinkedList<>();
12         queue.addAll(nestedList);
13         while (!queue.isEmpty()) {
14             int size = queue.size();
15             for (int i = 0; i < size; i++) {
16                 NestedInteger cur = queue.poll();
17                 if (cur.isInteger()) {
18                     res += cur.getInteger() * depth;
19                 } else {
20                     queue.addAll(cur.getList());
21                 }
22             }
23             depth++;
24         }
25         return res;
26     }
27 }

DFS

时间O(n) - list的长度

空间O(n)

Java实现

 1 class Solution {
 2     public int depthSum(List<NestedInteger> nestedList) {
 3         // corner case
 4         if (nestedList == null) {
 5             return 0;
 6         }
 7         // 既然list不为空，那么深度起码为1
 8         return helper(nestedList, 1);
 9     }
10 
11     private int helper(List<NestedInteger> list, int depth) {
12         int res = 0;
13         for (NestedInteger each : list) {
14             if (each.isInteger()) {
15                 res += each.getInteger() * depth;
16             } else {
17                 res += helper(each.getList(), depth + 1);
18             }
19         }
20         return res;
21     }
22 }