Reversed Nested Integer - Linkedin

* 这道题我加了个变形，reversed的
* 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 1, one 2 at depth 2)
* Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 3, one 4 at depth 2, one 6 at depth 1)
*/
/**
* 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 this 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 getList();
}

解答

int calWeightedSum(MyNestedInteger ni) {
    if(ni == null) {
        return 0;
    }
    else {
        if(ni.isInteger()) {
            return ni.getInteger()
        } else {
            int depth = ni.getDepth(ni.getList())；
            return getListSum(ni.getList(), depth);
        }
    }
}

int getListSum(List<MyNestedInteger> li, int curDepth) {
    int ret = 0;
    for(MyNestedInteger ni : li) {
        if(ni.isInteger()) {
            ret += ni.getInteger() * curDepth;
        } else {
            ret += getListSum(ni.getList(), curDepth-1);
        }
    }
    return ret;
}

int getDepth(List<MyNestedInteger> li) {
    int greatestDepth = 0;
    for(MyNestedInteger ni : li) {
        if(ni.isInteger()) {
            if(greatestDepth < 1) {
                greatestDepth = 1;
            } 
        } else {
            int d = getDepth(li.getList());
            if(greatestDepth < d){
                greatestDepth = d;
            }
        }
    }
    return greatestDepth;
}

http://yuanhsh.iteye.com/blog/2192549

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

1. public int sumOfReversedWeight(NestedInteger ni) {  
2.     if(ni.isInteger()) {  
3.         return ni.getInteger();  
4.     }  
5.     int prev = 0, sum = 0;  
6.     List<NestedInteger> cur = ni.getList();  
7.     List<NestedInteger> next = new ArrayList<>();  
8.     while(!cur.isEmpty()) {  
9.         for(NestedInteger item:cur) {  
10.             if(item.isInteger()) {  
11.                 prev += item.getInteger();  
12.             } else {  
13.                 next.addAll(item.getList());  
14.             }  
15.             sum += prev;  
16.             cur = next;  
17.             next = new ArrayList<>();  
18.         }  
19.     }  
20.     return sum;  
21. } 

http://www.mitbbs.com/article_t1/JobHunting/32850869_0_1.html
List<NestedInteger> next=new ArrayList<>();

int prev=0,sum=0;
while(curr!=null&&!curr.isEmpty()){
   for (NestedInteger ni:curr){
   
     if (ni.isInteger())
         prev+=ni.getInteger();
     else
         next.addAll(ni.getList());  
   }
   
   curr=next;
   next=new ArrayList<>();
   sum+=prev;
}
return sum;
http://www.mitbbs.com/article_t1/JobHunting/32850869_0_2.html
把所有的数无权加一遍*（n+1) 
n 是最深层数
然后减去原题的结果。

Related
http://shirleyisnotageek.blogspot.com/2014/12/sum-of-nested-integers.html
http://yuanhsh.iteye.com/blog/2192549
/** 
* 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, and one 6 at depth 3) 
*/ 
public int depthSum (List<NestedInteger> input) 
{ // ur implementation here} 


** 
* This is the interface that represents nested lists. 
* You should not implement it, or speculate about its implementation. 
*/ 
public interface NestedInteger 
{ 
/** @return true if this NestedInteger holds a single integer, rather than a nested list */ 
boolean isInteger(); 

/** @return the single integer that this NestedInteger holds, if it holds a single integer 
* Return null if this NestedInteger holds a nested list */ 
Integer getInteger(); 

/** @return the nested list that this NestedInteger holds, if it holds a nested list 
* Return null if this NestedInteger holds a single integer */ 
List<NestedInteger> getList(); 
}

A Linkedin interview question. The original problem can be found on Careercup.

Just use recursion. Return the integer * level if the NestedInteger is a single integer, otherwise recursively check all the lists in the NestedInteger.

Apparently the warning that I "should not implement it, or speculate about its implementation" is correct. Yet I am still curious...

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public class SumofNestedIntegers {  public int depthSum(List<nestedinteger> input) {   if (input == null)    return 0;   return getSum(input, 1);  }  private int getSum(List <nestedinteger> input, int depth) {    int sum = 0;    for (NestedInteger nested : input) {     if (nested.isInteger()) {      sum += nested.getInteger() * depth;     }     else {      sum += getSum(nested.getList(), depth++);     }   }    return sum;  } }