问题描述
http://www.lintcode.com/en/problem/zigzag-iterator-ii/
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].
解题思路
Zigzag Iterator的follow up问题，当input是k个list的情况，如何构造穿梭于数组的iterator。
关键点：两个list的时候，只要建两个list对应的iterator。k个list的时候，拓展为建一个装有各list的iterator的list。以这个装有所有iterator的list来操作，如果当前iterator所在的list还有next()，那么turns = (turns + 1) % list的size()。如果没有了，那么先remove这个iterator，再模运算turns = turns % list的size()，即跳入到下一个相邻的list的iterator。
参考代码
public class ZigzagIterator2 {
/**
* @param vecs a list of 1d vectors
*/
public List<Iterator<Integer>> iterators;
public int turns;
public ZigzagIterator2(ArrayList<ArrayList<Integer>> vecs) {
// initialize your data structure here.
iterators = new ArrayList<Iterator<Integer>>();
for (ArrayList<Integer> vec : vecs) {
if (vec.size() > 0) {
iterators.add(vec.iterator());
}
}
turns = 0;
}
public int next() {
int element = iterators.get(turns).next();
if (iterators.get(turns).hasNext()) {
turns = (turns + 1) % iterators.size();
} else {
iterators.remove(turns);
if (iterators.size() > 0) {
turns = turns % iterators.size();
}
}
return element;
}
public boolean hasNext() {
return iterators.size() > 0;
}
}
/**
* Your ZigzagIterator2 object will be instantiated and called as such:
* ZigzagIterator2 solution = new ZigzagIterator2(vecs);
* while (solution.hasNext()) result.add(solution.next());
* Output result
*/