Iterator 类

Zigzag Iterator

所谓的 Zigzag 其实等价于 circular ~ 实现 circular 的常见办法有两个：

• 建 array / arraylist，靠取 mod 的 index trick;
• 直接用内置的 deque 库，每次头尾操作就可以

public class ZigzagIterator {
    Deque<Iterator<Integer>> deque;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        deque = new LinkedList<Iterator<Integer>>();
        if(v1.size()!=0) deque.offerFirst(v1.iterator());
        if(v2.size()!=0) deque.offerFirst(v2.iterator());
    }

    public int next() {
        Iterator<Integer> cur = deque.pollLast();
        int num = cur.next();
        if(cur.hasNext()) deque.offerFirst(cur);
        return num;
    }

    public boolean hasNext() {
        return deque.size()!=0;
    }
}

Peeking Iterator

可以用Integer来储存peek, null来判断.

class PeekingIterator implements Iterator<Integer> {
    Integer peek;
    Iterator<Integer> cur;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        cur = iterator;
        if(cur.hasNext()) peek = cur.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() {
        int tmp = peek;
        if(cur.hasNext()) peek = cur.next();
        else peek = null;
        return tmp;
    }

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

Design Compressed String Iterator

这两天连着写hard，有点恶心。写个水题压压惊。1次AC，beats 96.86%

public class StringIterator {

    StringBuilder remain;
    char c;
    int count;
    public StringIterator(String compressedString) {
        remain = new StringBuilder(compressedString);
        c=' ';
        count = 0;
    }

    public char next() {
        if(!hasNext()) {
            return ' ';
        }
        count--;
        return c;
    }

    public boolean hasNext() {
        if(count!=0)
            return true;
        if(remain.length()!=0){
            c = remain.charAt(0);
            count = 0;
            int i=1;
            for(;i<remain.length()&&remain.charAt(i)<='9'&&remain.charAt(i)>='0';i++){
                count*=10;
                count+=(int)(remain.charAt(i)-'0');
            }
            remain = new StringBuilder(remain.substring(i)); 
        }
        return count!=0;
    }
}