*Sum of NestedInteger

Given a nested list of integers, returns the sum of all integers in the list weighted by their depth 

For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1) 

Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, one 6 at depth2) 

/** * This is the interface that represents nested lists. * You should not implement it, or speculate about its implementation. */ public interface NestedInteger { //Returns true if this NestedInteger holds a single integer, rather than a nested list public boolean isInteger(); //Returns the single integer that the NestedInteger holds, if it holds a single integer //Returns null if this NestedInteger holds a nested list public Integer getInteger(); //Returns the nested list that this NestedInteger holds, if it holds a nested list //Returns null if this NestedInteger holds a single integer public List<NestedInteger> getList(); } public int sumOfNestedInteger(NestedInteger nest) { if(nest.isInteger()) { return nest.getInteger(); } return sumList(nest.getList(), 1); } private int sumList(List<NestedInteger> list, int depth) { int sum = 0; for(NestedInteger item: list) { if(item.isInteger()) { sum += item.getInteger()*depth; } else { sum += sumList(item.getList(), depth+1); } } return sum; }

Follow Up:

followup说改成return the sum of all integers in the list weighted by their “reversed depth”.

也就是说{{1,1},2,{1,1}}的结果是(1+1+1+1)*1+2*2=8

 

思路：

需要两个变量计数，sum 与 prev

例子 {{2,2,{3}},1,{2,2}}

一共三层

第一层 prev = 1 sum=1

第二层 prev =prev+2+2+2+2  最后prev =9， sum = 10

第三层 prev =prev +3 prev = 12        sum =22

理论结果   3+2*2*4+1*3 =22

prev每次都加自身，相当于第1个数在第n层的时候已经加了n次，第2个数n-1次，一次类推……

public int sumOfReversedWeight(NestedInteger ni) { if(ni.isInteger()) { return ni.getInteger(); } int prev = 0, sum = 0; List<NestedInteger> cur = ni.getList(); List<NestedInteger> next = new ArrayList<>(); while(!cur.isEmpty()) { for(NestedInteger item:cur) { if(item.isInteger()) { prev += item.getInteger(); } else { next.addAll(item.getList()); } sum += prev; cur = next; next = new ArrayList<>(); } } return sum; }

mitbbs上的牛人说：

把所有的数无权加一遍*（n+1) n 是最深层数然后减去原题的结果。这题故意绕人吧。。。。

 

reference：

http://www.careercup.com/question?id=5139875124740096

http://www.mitbbs.com/article_t1/JobHunting/32850869_0_1.html

转载于:https://www.cnblogs.com/hygeia/p/5135370.html

相关资源：JAVA上百实例源码以及开源项目