NestedList

NestedList问题

/**
 * // 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 empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */

339. Nested List Weight Sum

DFS:

public int depthSum(List<NestedInteger> nestedList) {
     return dfs(nestedList,1);
 }

 int dfs(List<NestedInteger> nestedList, int depth){
     int res=0;
     for(NestedInteger i: nestedList){
         if(i.isInteger()){
             res+=i.getInteger()*depth;
         }else{
             res+=dfs(i.getList(),depth+1);
         }
     }
     return res;
 }

BFS:

public int depthSum(List<NestedInteger> nestedList) {
    int res=0;
    Deque<NestedInteger> q=new LinkedList<>();
    for(NestedInteger i : nestedList){
        q.offer(i);
    }
    int depth=1;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            NestedInteger i=q.poll();
            if(i.isInteger()){
                res+=i.getInteger()*depth;
            }else{
                for(NestedInteger j: i.getList()){
                    q.offer(j);
                }
            }
        }
        depth++;
    }
    return res;
}

364. Nested List Weight Sum II

int maxDepth=1;
public int depthSumInverse(List<NestedInteger> nestedList) {
    for(NestedInteger i : nestedList){
        maxDepth=Math.max(maxDepth,getMax(i));
    }
    return dfs(nestedList,maxDepth);
}

int dfs(List<NestedInteger> nestedList, int depth){
    int res=0;
    for(NestedInteger i : nestedList){
        if(i.isInteger()){
            res+=i.getInteger()*depth;
        }else{
            res+=dfs(i.getList(),depth-1);
        }
    }
    return res;
}




int getMax(NestedInteger i){
    if(i.isInteger()){
        return 1;
    }
    int depth=1;
    for(NestedInteger next : i.getList()){
        depth=Math.max(depth,getMax(next)+1);
    }
    return depth;
}

341. Flatten Nested List Iterator

public class NestedIterator implements Iterator<Integer> {

    List<Integer> list;
    Iterator<Integer> iterator;
    public NestedIterator(List<NestedInteger> nestedList) {
        list=new ArrayList<>();
        parse(nestedList);
        iterator=list.iterator();
    }

    private void parse(List<NestedInteger> nestedList){
        for (NestedInteger n : nestedList) {
            if(n.isInteger()){
                list.add(n.getInteger());
            }else{
                parse(n.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }
}