/**
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
Example 1:
Input: the list [[1,1],2,[1,1]],
Output: 10.
Explanation:
four 1's at depth 2, one 2 at depth 1, 4 * 1 * 2 + 1 * 2 * 1 = 10
Example 2:
Input: the list [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
*/
// This is the interface that allows for creating 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.
public 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
public 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
public List<NestedInteger> getList();
}
public class NestedListWeightSum {
public int depthSum(List<NestedInteger> nestedList) {
int depth = 1;
int total = 0;
total = helper(nestedList, depth);
return total;
}
public int helper(List<NestedInteger> nestedList, int depth){
if(nestedList==null){
return 0;
}
int total = 0;
for(NestedInteger nint:nestedList){
if(nint.isInteger()){
total+=nint.getInteger()*depth;
}else{
total+=helper(nint.getList(), depth+1);
}
}
return total;
}
public static void main(String args[]){
//[[1,1],2,[1,1]]
}
}
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
Example 1:
Input: the list [[1,1],2,[1,1]],
Output: 10.
Explanation:
four 1's at depth 2, one 2 at depth 1, 4 * 1 * 2 + 1 * 2 * 1 = 10
Example 2:
Input: the list [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
*/
// This is the interface that allows for creating 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.
public 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
public 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
public List<NestedInteger> getList();
}
public class NestedListWeightSum {
public int depthSum(List<NestedInteger> nestedList) {
int depth = 1;
int total = 0;
total = helper(nestedList, depth);
return total;
}
public int helper(List<NestedInteger> nestedList, int depth){
if(nestedList==null){
return 0;
}
int total = 0;
for(NestedInteger nint:nestedList){
if(nint.isInteger()){
total+=nint.getInteger()*depth;
}else{
total+=helper(nint.getList(), depth+1);
}
}
return total;
}
public static void main(String args[]){
//[[1,1],2,[1,1]]
}
}
No comments:
Post a Comment