Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Input: [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1.Example 2:
Input: [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.
嵌套列表的权重和。
题意跟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 }
相关题目