Zigzag Iterator

Problem

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

Example

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].

Note

两个一维向量，所以建立两个Iterator。
要实现Zigzag交替迭代，可以用一个奇偶计数器count进行标记。
初始化：对两个向量v1，v2调用iterator()方法，分别初始化为it1和it2；并将计数器置0.
next()方法：每次调用时先将计数器+1，若count为奇数或it2已迭代完，返回it1.next()；若count为偶数且it1已迭代完，返回it2.next()。 default返回-1。
hasNext()方法：只要it1或it2还有未迭代的元素，则返回true。

Solution

import java.util.Iterator;
public class ZigzagIterator {
    private Iterator<Integer> it1;
    private Iterator<Integer> it2;
    private int count;
    public ZigzagIterator(List<Integer> v1, List<Integer> 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();
    }
}

Zigzag Iterator II

Problem

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".

Example

Given k = 3 1d vectors:

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

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

Note

对多个一维向量进行交叉的迭代操作，建立一个迭代器数组its和一个计位器index。
初始化：将迭代器数组初始化为ArrayList<>()，再将向量数组vecs循环使用迭代器并加入迭代器数组，然后将计位器初值设为0。
hasNext()方法：只要迭代器数组its.size()大于0，就返回true。
next()方法：直接查找its数组的index位的迭代器，调用next()方法得到的整数it即为要返回的元素。不过，找到it之后要先更新index：若当前迭代器不为空，index进行先+1后对its.size()取余的操作，指向下一个迭代器；若当前迭代器为空，从迭代器数组中remove这个迭代器，并对index进行对its.size()取余，刷新下个迭代器的位置。更新index后，返回取出的元素it。

Solution

public class ZigzagIterator2 {
    List<Iterator<Integer>> its;
    int index;
    public ZigzagIterator2(ArrayList<ArrayList<Integer>> vecs) {
        this.its = new ArrayList<Iterator<Integer>>();
        //遍历数组加入迭代器数组
        for (ArrayList<Integer> 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;
    }
}

Binary Search Tree Iterator

Problem

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.

Example

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

   10
 /    \
1      11
 \       \
  6       12

Challenge

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

Super Star: Extra memory usage O(1)

Note

用stack对BST进行初始化：查找并加入所有左子树结点。
next()方法：对stack.pop()的当前结点cur操作，存为temp，然后对cur.right进行查找左子树结点并压入stack的操作，最后返回原结点temp。
hasNext()方法：stack非空，则为true。

Solution

public class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        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;
    }
}

Flatten Nested List Iterator

Problem

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.

Example

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].

Note

建立此种数据类型的迭代器iterator，和它的指针peek（初值为null）。
首先，要进行迭代的数据类型为NestedInteger，其实是一个树状的层级结构，可以用stack+recursion来做。
先写一个迭代层级结构的递归方法iteratorNext()：
当迭代器非空--hasNext()，取出下一个元素next()，若此元素满足isInteger()，就返回它；否则将外层的迭代器存入stack，而对当前元素继续迭代和递归。
当迭代器为空--而stack非空，就pop出stack中的元素继续递归。

再写迭代器的next()方法：
返回指针元素的getInteger()；并让指针通过递归方法指向下一个元素。

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

Solution

import java.util.Iterator;
public class NestedIterator implements Iterator<Integer> {
    private NestedInteger peek = null;
    private Iterator<NestedInteger> iterator;
    private Stack<Iterator<NestedInteger>> stack = new Stack<>();
    public NestedIterator(List<NestedInteger> 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() {}
}

Peeking Iterator

Problem

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().

Example

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.

Hint

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.

Follow up

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

Note

略。

Solution

class PeekingIterator implements Iterator<Integer> {
    public Iterator<Integer> it;
    public Integer peek;
    public PeekingIterator(Iterator<Integer> 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;
    }
}