2016年10月21日星期五

364. Nested List Weight Sum II



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;  
   }  

没有评论:

发表评论