leetcode 341 Flatten Nested List Iterator 以及其他Iter

chaosx110 發(fā)布于2019-08-14 18:00 / 995人閱讀

摘要：返回的是表示是否走到了結(jié)尾。起到的就是緩存作用，因為調(diào)用之后馬上就走到下一個了。如果調(diào)用，返回用得到和最初的輸入相同的做相同的步驟存入不斷拆開得到結(jié)果。思想就是來自括號，后面也會跟進的專題

Iterator其實就是一個單鏈表，無法回頭看。java里很多數(shù)據(jù)結(jié)構(gòu)都有這個接口，使用時需要initalize,得到一個iterator.
調(diào)用next()返回的是一個object, 指向的是下一個未訪問過的部分。
hasnext()返回的是boolean, 表示是否走到了結(jié)尾。

284 Peeking Iterator

class PeekingIterator implements Iterator {
    Iterator iter;
    Integer next = null;    // 起到的就是緩存作用，因為next()調(diào)用之后馬上就走到下一個object了。
    
    public PeekingIterator(Iterator iterator) {
        // initialize any member here.
        iter = iterator;
        if(iter.hasNext()){
            next = iter.next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer res = next;
        next = iter.hasNext() ? iter.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }
}

281 Zigzag Iterator

public class ZigzagIterator {
    Queue list;
    
    public ZigzagIterator(List v1, List v2) {
        list = new LinkedList();
        if(!v1.isEmpty()) list.add(v1.iterator());
        if(!v2.isEmpty()) list.add(v2.iterator());
        // 如果給的是k個list, List> vs, 只需要把所有v1,v1...vk生成iterator放到q里
        // for(List v: List>) if(!v.isEmpty()) list.add(v.iterator());
    }

    public int next() {
        Iterator iter = list.poll();
        int res = (Integer) iter.next();
        if(iter.hasNext()) list.offer(iter);
        return res;
    }

    public boolean hasNext() {
        return !list.isEmpty();
    }
}

Zigzag Iterator這個題目和merge k sorted list很像，design twitter用到的就是merge k sorted list的思想加上OOD，會另寫一篇。

173 BST Iterator

戳這里，BST inorder小專題。
bst iterator

341 Flatten Nested List Iterator

題目的意思定義了一個特殊的數(shù)據(jù)結(jié)構(gòu)，用括號形成很多層，按從左到右的順序輸出。
括號是個強提示，要把括號里的東西拆開還保持原來的順序，就需要用stack處理。
[1,[4,[6]]] 存到stack里，變成|[4,[6]], [1]|
棧頂調(diào)用isInteger()，返回true, 就要getInteger()輸出。
如果調(diào)用isInteger()，返回false, 用getList()得到和最初的輸入相同的list,做相同的步驟存入stack.
不斷拆開NestedInteger, 得到結(jié)果。
這題就是給的API有點多，需要讀懂題意，然后再拆開得到結(jié)果。stack思想就是來自括號，后面也會跟進stack的專題.

/**
 * // 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 getList();
 * }
 */
public class NestedIterator implements Iterator {
    ArrayDeque stk;
    
    public NestedIterator(List nestedList) {
        stk = new ArrayDeque();
        for(int i = nestedList.size()-1; i >= 0; i--){
            stk.addLast(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stk.pollLast().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!stk.isEmpty()){
            NestedInteger cur = stk.peekLast();
            if(cur.isInteger()){
                return true;
            }
            List list = stk.pollLast().getList();
            for(int i=list.size()-1; i>=0; i--){
                stk.addLast(list.get(i));
            }
        }
        return false;
    }
}```