ZigzagIterator1 [source code]

public class ZigzagIterator1 {
static
/******************************************************************************/
public class ZigzagIterator {
    Integer[][] data;
    int m;
    int idx = 0, row = 0;
    int maxLen;
    int maxRow;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        m = 2;
        data = new Integer[2][];
        data[0] = v1.toArray(new Integer[0]);
        data[1] = v2.toArray(new Integer[0]);
        if (data[0].length > data[1].length) {
            maxLen = data[0].length;
            maxRow = 0;
        } else {
            maxLen = data[1].length;
            maxRow = 1;
        }
    }

    public int next() {
        if (idx < data[row].length) {
            int res = data[row][idx];
            row = (row + 1) % m;
            if (row == 0)
                idx++;
            return res;
        }
        while (idx >= data[row].length) {
            row = (row + 1) % m;
            if (row == 0)
                idx++;
        }
        int res = data[row][idx];
        row = (row + 1) % m;
        if (row == 0)
            idx++;
        return res;
    }

    public boolean hasNext() {
        return !((idx == maxLen - 1 && row > maxRow) || idx >= maxLen);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        Integer[][] inputs = {
            {1,2}, {3,4,5,6},
            {1}, {},
            {1,2},{},
        };
        int[][] answers = {
            {1, 3, 2, 4, 5, 6},
            {1},
            {1,2},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            List<Integer> v1 = Arrays.asList(inputs[2 * i]);
            List<Integer> v2 = Arrays.asList(inputs[1 + 2 * i]);
            ZigzagIterator1.ZigzagIterator tester = new ZigzagIterator1.ZigzagIterator(v1, v2);
            String ans = Printer.array(answers[i]);
            System.out.println(Printer.seperator());
            StringBuilder sb = new StringBuilder();
            while (tester.hasNext()) {
                int next = tester.next();
                sb.append(next + " ");
            }
            String output = sb.toString();
            System.out.println(Printer.wrapColor(Printer.array(inputs[2 * i]) + " AND " + Printer.array(inputs[1 + 2 * i]), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + ans, output.equals(ans) ? "green" : "red"));
        }
    }
}

首先简单的一个人逻辑, 想想这个问题最naive的做法是什么样的.

那么这个问题的难点在哪里? 其实就在于怎么处理长度不一样的问题(这种类似lemma by lemma的development要学会说, 你真正面试的时候是要这么说话的);

总体来说是一个简单的题目, 但是还是一如既往的Google风格, 各种边界case考虑的很烦人; 尤其是hasNext到底怎么写. 刚开始写的太简单了, 导致各种出问题; 要知道在这种iterator的设计当中, 你始终记得一个前提: next和hasNext不是分开看的. 两者一定要统一起来看, especially, 你hasNext始终是next的前提, 或者说assertion. 不要想着在next里面, 循环走到头(not hasNext)的时候, 什么乱七八糟的判断; 这些判断不应该是next完成的, 而是hasNext完成的: 如果一个state代表实际上已经走到尽头(无法next了), 那么hasNext should return false in the first place, so that the next call wrapped by this hasNext call would not execute at all;

这里hasNext要判断两种情况:

• 如果idx还在最后一列(当然是最长的row的长度对应的那一列), 那么要判断是否已经走过了最后一个entry: 因为要确保这里就立刻停止, 不然假如已经过了这个entry, 然后你下一个call你还允许hasNext返回TRUE, 那么你最后next你返回什么呢? 你返回什么都不对, 唯一有可能的就是返回Null, 但是这个在题目给的API里面不可能实现(事实上也不应该实现, hasNext和next构成的iterator就不应该返回Null, 设计上就是这样的);
• 如果idx超过了最后一列: 刚开始我认为这种情况不会发生, 但是实际上是有可能的, 你最后一个entry的位置肯定hasNext应该返回TRUE, 然后next运行. 但是假如最后一个entry在最后一列的最后一行怎么办呢? 现在的这个逻辑就是, 这个entry执行完了之后, 我们直接就继续更新idx和row, 这个更新就自动把idx推到下一列了. 所以hasNext也要判断idx是否已经超范围;
• 一个另外的思路可以是这样: 直接在instance var里面设置一个flag来保存hasNext的结果, 如果我们比如在一个next call结束的时候检测一下后面还有没有有效entry了(不更新, 就是check一下), 如果还有, 我们就更新idx和row, 如果没有了, 我们就直接把这个flag给设置成FALSE; 然后在hasNext里面, 我们有限判断这个flag(相当于这个flag是一个overriding的优先级), 然后在判断其他的idx和row的结论;

注意这个循环:

        while (idx >= data[row].length) {  
            row = (row + 1) % m;  
            if (row == 0)  
                idx++;  
        }

刚开始header里面我还加了一个idx不能超出maxLen, 但是实际上只要hasNext设计的对了, 这里是不用加这个的: 我们在next里面的时候, 始终是有assertion: hasNext = true before call的. 所以现在的[row][idx]这个位置, 不可能超过最后一个有效entry, 更不可能已经超过了maxLen. 我们当前这个next call, 就不可能使得idx超出有效length(分情况讨论证明: 假如当前位置(严格定义, [row][idx] is the next position to pop)是最后一个有效entry, 那么不会进入这个while循环; 假如当前位置还不是最后一个有效位置, 那么到了最后一个有效位置这个while循环就一定会停止, 所以无论如何不会导致idx超长).

我这里的算法还是比较直接的, 这个题目实际上你处理的是一个uneven matrix, 然后iterate的时候掌握好一个cyclic iteration的技巧就行了; 因为是uneven, 所以末尾判断这个也比较重要;

最后的速度是6ms (19%), 还算不错的. 看了一下submission, 比这个快的基本都是没有办法解决Follow-Up的解法, 也就是一个list给一个指针就行了; 我这个解法是可以轻松扩展到Follow-Up这个情况的; //代码稍微简化了一下居然做到了4(68), 这个是铁的最优解了;

这个是submission里面一个也可以扩展到Follow-Up的解:

public class ZigzagIterator {  
int limit;  
Queue<Integer> queue;  
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
        queue = new LinkedList<Integer>();  
        if(v1.size() > v2.size()) limit = v2.size();  
        else limit = v1.size();  

        for(int i=0; i<limit; i++) {  
            queue.offer(v1.get(i));  
            queue.offer(v2.get(i));  
        }  
        if(v1.size() > v2.size()) {  
            for(int i=limit; i<v1.size(); i++)  
                queue.offer(v1.get(i));  
        }  
        if(v1.size() < v2.size()) {  
            for(int i=limit; i<v2.size(); i++)  
                queue.offer(v2.get(i));  
        }  
    }  

    public int next() {  
        return queue.poll();  
    }  

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

数据结构设计当中的: expensive and cheap分配

虽然最后OJ给的速度, 这个算法没有我的算法快, 但是你仔细想想, 他这个算法其实是比我的算法好的. 他的算法把所有的expensive全都分配到constructor上面; 这样后面真正使用的时候每一个access本身都非常的cheap;

不过就这个问题而言, amortized cost其实是差不多的, 因为这个题目做的其实就是一个iterate的东西; 严格来说, 我这个方法针对这个问题其实好一些; 他这种做queue的方法, constructor的时候就先整个iterate完了一遍了, 然后每个access还要给一个O(1), 所以最后实际上他的amortized是我的两倍(虽然仍然是线性关系), 所以OJ会体现出这个差别;

discussion里面有人谈到, 这个问题是设计一个iterator, 所以如果你在实现的过程中有built-in的iterator, 是有可能不被允许的, 事实上, 有人确实在真实的面试当中碰到了这个问题;

这个是discussion最优解, 有点赖皮的一个解法:

public class ZigzagIterator {  
    LinkedList<Iterator> list;  
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
        list = new LinkedList<Iterator>();  
        if(!v1.isEmpty()) list.add(v1.iterator());  
        if(!v2.isEmpty()) list.add(v2.iterator());  
    }  

    public int next() {  
        Iterator poll = list.remove();  
        int result = (Integer)poll.next();  
        if(poll.hasNext()) list.add(poll);  
        return result;  
    }  

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

这个真的很赖皮, 而且是可以扩展到Follow-Up的, 而且是O(1)的space;

不过这个解法看看就好, 我感觉我没有想出这个解法的原因一个是因为我还是更倾向于底层实现的方式来做算法题, 以及我本身对iterator的使用不够熟悉, 没有能够想到这样的思路;

不过鉴于这个是Google的题目, 我觉得这样的一个解可能是要挨喷的. 当然了, 在写出一个底层解之前, 说一下这个解是可以的, 毕竟这个解的performance也好, 而且也简单好描述; 如果面试官还是不满意, 就来底层的做法;

这个是稍微改写一下, 加上了queue的API:

public class ZigzagIterator {  

    // Better solution, 6ms  
    Queue<Iterator> q;  

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
        q = new LinkedList();  
        if (!v1.isEmpty()) q.offer(v1.iterator());  
        if (!v2.isEmpty()) q.offer(v2.iterator());  
    }  

    public int next() {  
        Iterator cur = q.poll();  
        int res = (int) cur.next();  
        if (cur.hasNext()) q.offer(cur);  
        return res;  
    }  

    public boolean hasNext() {  
        return q.peek() != null;  
    }  
}

也可以用deque;

这个是一个看似稍微底层一点的, 其实还是借用了iterator的解法:

public class ZigzagIterator {  
    Iterator<Integer>[] its;  
    int pos;  

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
        its = new Iterator[]{v1.iterator(), v2.iterator()};  
        pos = 0;  
    }  

    public int next() {  
        int next = its[pos].next();  
        pos = (pos == its.length - 1) ? 0 : pos + 1;  
        return next;  
    }  

    public boolean hasNext() {  
        if (its[pos].hasNext()) return true;  
        for (int i = pos + 1; i < its.length; i++) {  
            if (its[i].hasNext()) {  
                pos = i;  
                return true;  
            }  
        }  
        for (int i = 0; i < pos; i++) {  
            if (its[i].hasNext()) {  
                pos = i;  
                return true;  
            }  
        }  
        return false;  
    }  
}

大概看看就行了, 没什么好学的;

discussion里面也没有什么其他特别惊人的解法了, 这个题目Okay;

Problem Description

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

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

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
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". For example, given the following input:

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

It should return [1,4,8,2,5,9,3,6,7].

Difficulty:Medium
Total Accepted:26.8K
Total Submissions:53.3K
Contributor: LeetCode
Companies
google
Related Topics
design
Similar Questions
Binary Search Tree Iterator Flatten 2D Vector Peeking Iterator Flatten Nested List Iterator

/**

• Your ZigzagIterator object will be instantiated and called as such:
• ZigzagIterator i = new ZigzagIterator(v1, v2);
• while (i.hasNext()) v[f()] = i.next();
  */