DFS:先算height 在从上往下走
public class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
if(nestedList == null || nestedList.size() == 0) return 0;
int h = helper(nestedList);
int res = getSum(nestedList, h);
return res;
}
private int getSum(List<NestedInteger> l, int layer) {
int sum = 0;
if(l == null || l.size() == 0) return sum;
for(NestedInteger n : l) {
if(n.isInteger()) sum += n.getInteger() * layer;
else sum += getSum(n.getList(), layer - 1);
}
return sum;
}
private int helper(List<NestedInteger> l) {
if(l == null || l.size() == 0) return 0;
int max = 0;
for(NestedInteger n : l) {
if(n.isInteger()) max = Math.max(max, 1);
else max = Math.max(max, helper(n.getList()) + 1);
}
BFS 保存一个从上到下的不带乘法的和(每个数字前边的param是1)
那么每次下一层时候,除了本层的和,在加上 unweighted的值(可以把本层和直接加到unweighted里边)
public int depthSumInverse(List<NestedInteger> nestedList) {
//bfs, add preresult to next level
int sum = 0, unweighted = 0;
while(!nestedList.isEmpty()){
List<NestedInteger> next = new ArrayList<>();
for(NestedInteger ni:nestedList){
if(ni.isInteger()){
unweighted+=ni.getInteger();
}else{
next.addAll(ni.getList());
}
}
sum += unweighted;
nestedList = next;
}
return sum;
}
没有评论:
发表评论