摘要：方法直接查找數(shù)組的位的迭代器，調(diào)用方法得到的整數(shù)即為要返回的元素。再寫迭代器的方法返回指針元素的并讓指針通過遞歸方法指向下一個元素。

Given two 1d vectors, implement an iterator to return their elements alternately.

Given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

兩個一維向量，所以建立兩個Iterator。
要實現(xiàn)Zigzag交替迭代，可以用一個奇偶計數(shù)器count進行標(biāo)記。
初始化：對兩個向量v1，v2調(diào)用iterator()方法，分別初始化為it1和it2；并將計數(shù)器置0.
next()方法：每次調(diào)用時先將計數(shù)器+1，若count為奇數(shù)或it2已迭代完，返回it1.next()；若count為偶數(shù)且it1已迭代完，返回it2.next()。 default返回-1。
hasNext()方法：只要it1或it2還有未迭代的元素，則返回true。

import java.util.Iterator;
public class ZigzagIterator {
    private Iterator it1;
    private Iterator it2;
    private int count;
    public ZigzagIterator(List v1, List v2) {
        this.it1 = v1.iterator();
        this.it2 = v2.iterator();
        count = 0;
    }

    public int next() {
        count++;
        if ((count % 2 == 1 && it1.hasNext()) || !it2.hasNext()) return it1.next();
        else if ((count % 2 == 0 && it2.hasNext()) || !it1.hasNext()) return it2.next();
        return -1;
    }

    public boolean hasNext() {
        return it1.hasNext() || it2.hasNext();
    }
}

Follow up Zigzag Iterator: What if you are given k 1d vectors? How well can your code be extended to such cases? The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic".

Given k = 3 1d vectors:

[1,2,3]
[4,5,6,7]
[8,9]

Return [1,4,8,2,5,9,3,6,7].

對多個一維向量進行交叉的迭代操作，建立一個迭代器數(shù)組its和一個計位器index。
初始化：將迭代器數(shù)組初始化為ArrayList<>()，再將向量數(shù)組vecs循環(huán)使用迭代器并加入迭代器數(shù)組，然后將計位器初值設(shè)為0。
hasNext()方法：只要迭代器數(shù)組its.size()大于0，就返回true。
next()方法：直接查找its數(shù)組的index位的迭代器，調(diào)用next()方法得到的整數(shù)it即為要返回的元素。不過，找到it之后要先更新index：若當(dāng)前迭代器不為空，index進行先+1后對its.size()取余的操作，指向下一個迭代器；若當(dāng)前迭代器為空，從迭代器數(shù)組中remove這個迭代器，并對index進行對its.size()取余，刷新下個迭代器的位置。更新index后，返回取出的元素it。

public class ZigzagIterator2 {
    List> its;
    int index;
    public ZigzagIterator2(ArrayList> vecs) {
        this.its = new ArrayList>();
        //遍歷數(shù)組加入迭代器數(shù)組
        for (ArrayList vec: vecs) {
            if (vec.size() > 0) its.add(vec.iterator());
        }
        index = 0;
    }

    public int next() {
        int it = its.get(index).next();
        //刷新指針位置
        if (its.get(index).hasNext()) index = (index+1) % its.size();
        else {
            its.remove(index);
            if (its.size() > 0) index = index % its.size(); //注意這里要判斷its.size()不為0，才能取模
        }
        
        return it;
    }

    public boolean hasNext() {
        return its.size() > 0;
    }
}

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)
next() and hasNext() queries run in O(1) time in average.

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    
1      11
        
  6       12

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

用stack對BST進行初始化：查找并加入所有左子樹結(jié)點。
next()方法：對stack.pop()的當(dāng)前結(jié)點cur操作，存為temp，然后對cur.right進行查找左子樹結(jié)點并壓入stack的操作，最后返回原結(jié)點temp。
hasNext()方法：stack非空，則為true。

public class BSTIterator {
    Stack stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    public TreeNode next() {
        TreeNode cur = stack.pop();
        TreeNode temp = cur;
        if (cur.right != null) {
            cur = cur.right;
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
        }
        return temp;
    }
}

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

建立此種數(shù)據(jù)類型的迭代器iterator，和它的指針peek（初值為null）。
首先，要進行迭代的數(shù)據(jù)類型為NestedInteger，其實是一個樹狀的層級結(jié)構(gòu)，可以用stack+recursion來做。
先寫一個迭代層級結(jié)構(gòu)的遞歸方法iteratorNext()：
當(dāng)?shù)鞣强?-hasNext()，取出下一個元素next()，若此元素滿足isInteger()，就返回它；否則將外層的迭代器存入stack，而對當(dāng)前元素繼續(xù)迭代和遞歸。
當(dāng)?shù)鳛榭?-而stack非空，就pop出stack中的元素繼續(xù)遞歸。

再寫迭代器的next()方法：
返回指針元素的getInteger()；并讓指針通過遞歸方法指向下一個元素。

hasNext()方法：
指針元素不為空，就返回true。

import java.util.Iterator;
public class NestedIterator implements Iterator {
    private NestedInteger peek = null;
    private Iterator iterator;
    private Stack> stack = new Stack<>();
    public NestedIterator(List nestedList) {
        iterator = nestedList.iterator();
        peek = iteratorNext();
    }
    public NestedInteger iteratorNext() {
        if (iterator.hasNext()) {
            NestedInteger i = iterator.next();
            if (i.isInteger()) return i;
            else {
                stack.add(iterator);
                iterator = i.getList().iterator();
                return iteratorNext();
            }
        }
        else if (!stack.isEmpty()) {
            iterator = stack.pop();
            return iteratorNext();
        }
        else return null;
    }
    
    @Override
    public Integer next() {
        Integer next = peek.getInteger();
        peek = iteratorNext();
        return next;
    }
    
    @Override
    public boolean hasNext() {
        return peek != null;
    }
    
    @Override
    public void remove() {}
}

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Think of "looking ahead". You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google"s guava library source code.

How would you extend your design to be generic and work with all types, not just integer?

略。

class PeekingIterator implements Iterator {
    public Iterator it;
    public Integer peek;
    public PeekingIterator(Iterator iterator) {
        // initialize any member here.
        this.it = iterator;
        if (it.hasNext()) peek = it.next();
        
    }

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

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

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