題目:
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.
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
Example 1:
Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)
Example 2:
Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17)
解答:
這一題其實挺tricky的,如果說第一道題的關鍵是記錄層次,那么這一題的關鍵是把這一層的integer sum傳到下一層去,代碼如下:
public int DFS(List<NestedInteger> nestedList, int intSum) {//關鍵點在于把上一層的integer sum傳到下一層去,這樣的話,接下來還有幾層,每一層都會加上這個integer sum,也就等于乘以了它的層數List<NestedInteger> nextLevel = new ArrayList<>();int listSum = 0;for (NestedInteger list : nestedList) {if (list.isInteger()) {intSum += list.getInteger();} else {nextLevel.addAll(list.getList());}}listSum = nextLevel.isEmpty() ? 0 : DFS(nextLevel, intSum);return listSum + intSum;
}public int depthSumInverse(List<NestedInteger> nestedList) {return DFS(nestedList, 0);
}