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.题意：
嵌套列表加权和
Solution1： BFS(level order traversal) 是最快的
code
1 class Solution { 2 public int depthSum(List<NestedInteger> nestedList) { 3 // corner case 4 if(nestedList == null){return 0;} 5 // initialize 6 int result = 0; 7 int depth = 1; 8 // put each item of list into the queue 9 Queue<NestedInteger> queue = new LinkedList<>(nestedList); 10 while(!queue.isEmpty()){ 11 // depends on different depth, queue size is changeable 12 int size = queue.size(); 13 for(int i = 0; i < size; i++){ 14 NestedInteger n = queue.poll(); 15 if(n.isInteger()){ 16 result += n.getInteger() * depth; 17 }else{ 18 // put each item of list into the queue 19 queue.addAll(n.getList()); 20 } 21 } 22 depth++; 23 } 24 return result; 25 } 26 }注意： put each item of list into the queue 的写法有：
Queue<NestedInteger> queue = new LinkedList<>(nestedList);for（NestedInteger n :nestedList）{ queue.add(n) } queue.addAll(nestedList)
Solution2: DFS
code
1 class Solution { 2 public int depthSum(List<NestedInteger> nestedList) { 3 if(nestedList == null) return 0; 4 return dfs(nestedList, 1); 5 } 6 7 private int dfs(List<NestedInteger> nestedList, int depth){ 8 int result = 0; 9 for(NestedInteger n : nestedList ){ 10 if(n.isInteger()){ 11 result = result + n.getInteger()*depth; 12 }else{ 13 result = result + dfs(n.getList() , depth+1); 14 } 15 } 16 return result ; 17 } 18 }
转载于:https://www.cnblogs.com/liuliu5151/p/9828259.html
相关资源：数据结构—成绩单生成器