Leaky Cauldron
0%

锯齿迭代器

Posted on Edited on

题目(LeetCode #281)

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

Example:

1
2
3
4
5
6
7
8
Input:
v1 = [1,2]
v2 = [3,4,5,6]

Output: [1,3,2,4,5,6]

Explanation: 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:

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:

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

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

题解

k 为 2 的基础情况时，可使用两个索引 i 和 j 分别标记移动位置，hasNext() 判断两索引是否到达列表尾即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class ZigzagIterator {
    private List<Integer> v1;
    private List<Integer> v2;
    int i = 0, j = 0;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

    public int next() {
        return i > j ? v2.get(j++) : v1.get(i++);
    }

    public boolean hasNext() {
        if (i >= v1.size()) i = Integer.MAX_VALUE;
        if (j >= v2.size()) j = Integer.MAX_VALUE;
        return i < v1.size() || j < v2.size();
    }
}

Follow up 中 k > 2 时，可使用队列保存各个列表的迭代器。调用 next() 时，依次取出队首迭代器的值，并判断该迭代器是否还有后续元素，若仍有后续元素则将该迭代器重新加入队列中，重复该操作直到队列为空为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class ZigzagIterator {

    private Queue<Iterator<Integer>> queue;

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

    public int next() {
        Iterator<Integer> cur = queue.poll();
        int result = cur.next();
        if (cur.hasNext()) queue.add(cur);

        return result;
    }

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