Given two 1d vectors, implement an iterator to return their elements alternately.
Example:
Input: v1 = [1,2] v2 = [3,4,5,6] Output:[1,3,2,4,5,6] Explanation:
By calling next repeatedly until hasNext returnsfalse
, 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
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:Input:
[1,2,3]
[4,5,6,7]
[8,9]
Output: [1,4,8,2,5,9,3,6,7]
.
Solution #1, 通用方法
public class ZigzagIterator { private boolean v1True = true; private List<Integer> v1; private List<Integer> v2; private int i1; private int i2; public ZigzagIterator(List<Integer> v1, List<Integer> v2) { this.v1 = v1; this.v2 = v2; i1 = 0; i2 = 0; } public int next() { int rt; if (v1True) { if (i1 < v1.size()) { rt = v1.get(i1); i1++; v1True = false; }else { rt = v2.get(i2); i2++; } } else { if (i2 < v2.size()) { rt = v2.get(i2); i2++; v1True = true; }else { rt = v1.get(i1); i1++; } } return rt; } public boolean hasNext() { return i1 < v1.size() || i2 < v2.size(); } } /** * Your ZigzagIterator object will be instantiated and called as such: * ZigzagIterator i = new ZigzagIterator(v1, v2); * while (i.hasNext()) v[f()] = i.next(); */
Solution #2, Java Iterator
public class ZigzagIterator { private Queue<Iterator> que; private List<Integer> v1; private List<Integer> v2; public ZigzagIterator(List<Integer> v1, List<Integer> v2) { que = new LinkedList<Iterator>(); this.v1 = v1; this.v2 = v2; if (!v1.isEmpty()) que.add(v1.iterator()); if (!v2.isEmpty()) que.add(v2.iterator()); } public int next() { Iterator i = que.poll(); int next = (Integer)i.next(); if (i.hasNext()) que.add(i); return next; } public boolean hasNext() { return !que.isEmpty(); } } /** * Your ZigzagIterator object will be instantiated and called as such: * ZigzagIterator i = new ZigzagIterator(v1, v2); * while (i.hasNext()) v[f()] = i.next(); */
No comments:
Post a Comment