Nested List Weight Sum(Easy)
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)
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();
}
class NestedIntegerImpl implements NestedInteger {
int num;
List<NestedInteger> list = new ArrayList<NestedInteger>();
public NestedIntegerImpl(int number) {
num = number;
list = null;
}
public NestedIntegerImpl(List<NestedInteger> inputList) {
num = -1;
list = inputList;
}
@Override
public boolean isInteger() {
return list == null;
}
@Override
public Integer getInteger() {
if (isInteger()) {
return num;
}
return -1;
}
@Override
public List<NestedInteger> getList() {
return list;
}
}
public int depthSum(List<NestedInteger> nestedList) {
Queue<NestedInteger> queue = new LinkedList<>();
int sum = 0, level = 0;
for(NestedInteger nit : nestedList)
queue.offer(nit);
while(!queue.isEmpty()){
level++;
int size = queue.size();
for(int i=0; i<size; i++){
NestedInteger nit = queue.poll();
if(nit.isInteger()){
sum = sum + nit.getInteger() * level;
}else{
for(NestedInteger nestedNit : nit.getList())
queue.offer(nestedNit);
}
}
}
return sum;
}