Screenshot from 2016-02-17 22:03:02.png
My code:
public class ZigzagIterator {
private int i1 = 0;
private int i2 = 0;
private boolean first = true;
private List<Integer> l1;
private List<Integer> l2;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
this.l1 = v1;
this.l2 = v2;
}
public int next() {
if (first) {
if (i1 < l1.size()) {
first = false;
return l1.get(i1++);
}
else {
return l2.get(i2++);
}
}
else {
if (i2 < l2.size()) {
first = true;
return l2.get(i2++);
}
else {
return l1.get(i1++);
}
}
}
public boolean hasNext() {
if (i1 >= l1.size() && i2 >= l2.size())
return false;
else
return true;
}
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/
这个题目没什么意思。
要么改进难度。如果是 k 个list呢？
我自己写了下，并且测试了下，应该基本没问题。
My code:
public class Solution{
private List<List<Integer>> l;
private int counter = 0; // index of list
private int[] index; // index of element in every list
private int k;
public Solution(List<List<Integer>> v) {
this.l = v;
k = v.size();
index = new int[k];
}
public int next() {
int lNum = counter % k;
if (index[lNum] < l.get(lNum).size()) {
counter++;
index[lNum]++;
return l.get(lNum).get(index[lNum] - 1);
}
counter++;
while (counter % k != lNum) {
if (index[counter % k] < l.get(counter % k).size()) {
index[counter % k]++;
counter++;
return l.get((counter - 1) % k).get(index[(counter - 1) % k] - 1);
}
else
counter++;
}
return -1;
}
public boolean hasNext() {
for (int i = 0; i < k; i++) {
if (index[i] < l.get(i).size())
return true;
}
return false;
}
public static void main(String[] args) {
ArrayList<Integer> l1 = new ArrayList<Integer>();
l1.add(1);
l1.add(2);
l1.add(3);
ArrayList<Integer> l2 = new ArrayList<Integer>();
l2.add(4);
l2.add(5);
l2.add(6);
l2.add(7);
ArrayList<Integer> l3 = new ArrayList<Integer>();
l3.add(8);
ArrayList<List<Integer>> l = new ArrayList<List<Integer>>();
l.add(l1);
l.add(l2);
l.add(l3);
Solution test = new Solution(l);
while (test.hasNext()) {
System.out.println(test.next());
}
}
}
就是使用一个counter进行轮询， round-robin，找到某个list还没有完全遍历完。下次从他下一个开始轮询。
Anyway, Good luck, Richardo!
这道题目并不难。自己写了下。
My code:
public class ZigzagIterator {
List<Iterator<Integer>> iters = new ArrayList<Iterator<Integer>>();
int counter = 0;
private int total = 2;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
iters.add(v1.iterator());
iters.add(v2.iterator());
}
public int next() {
for (int i = 0; i < total; i++) {
if (iters.get((counter + i) % total).hasNext()) {
int ret = iters.get((counter + i) % total).next();
counter++;
return ret;
}
}
return -1;
}
public boolean hasNext() {
for (int i = 0; i < total; i++) {
if (iters.get((counter + i) % total).hasNext()) {
return true;
}
}
return false;
}
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/
我是以，k个list，做zigzag iterator的角度来做这道题目的。
然后之前做过一道题目，叫做
Flatten Nested List Iterator
做完那道题目，这个题目的思路就很清晰了。
的确，遍历的时候要学会多用Java自带的 Iterator,就对是神器。
Anyway, Good luck, Richardo! -- 09/11/2016
