540.Zigzag Iterator

1.Description(Medium)

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

Example

Given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returnsfalse, the order of elements returned by next should be:[1, 3, 2, 4, 5, 6].

2.Code

public class ZigzagIterator {
    /**
     * @param v1 v2 two 1d vectors
     */
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // initialize your data structure here.
    }

    public int next() {
        // Write your code here
    }

    public boolean hasNext() {
        // Write your code here  
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator solution = new ZigzagIterator(v1, v2);
 * while (solution.hasNext()) result.add(solution.next());
 * Output result
 */

Version 1:数组法：跟Solution 601 Flatten 2D Vector解法几乎一模一样

注意交叉把元素放进类变量数组counter里面，哪个数组还剩下元素在一起放进去

public class Solution_540 {
     /**
     * @param v1 v2 two 1d vectors
     */
    private int[] counter;
    private int cnt;

    public Solution_540(List<Integer> v1, List<Integer> v2) {
        if(v1==null && v2==null){
            counter=new int[0];
        }else{
            int sum=v1.size()+v2.size();
            counter=new int[sum];
            //recount as index
            sum=0;
            int i=0;
            int j=0;
            while(i<v1.size() && j<v2.size()){
                counter[sum]=v1.get(i);
                sum++;
                i++;
                counter[sum]=v2.get(j);
                sum++;
                j++;
            }
            while(i<v1.size()){
                counter[sum]=v1.get(i);
                sum++;
                i++;
            }
            while(j<v2.size()){
                counter[sum]=v2.get(j);
                sum++;
                j++;
            }
        }
    }

    public int next() {
        int value=0;
        if(cnt<counter.length){
            value=counter[cnt];
        }
        cnt++;
        return value;
    }

    public boolean hasNext() {
        return cnt<counter.length; 
    }
}

Version 2: Iterator法：

public class Solution_540_2 {
    /**
    * @param v1 v2 two 1d vectors
    */

    private Iterator<Integer> it1;
    private Iterator<Integer> it2;
    private int count;
    public Solution_540_2(List<Integer> v1, List<Integer> v2) {
        it1=v1.iterator();
        it2=v2.iterator();
        count=0;
    }

    public int next() {
        count++;
        if((count%2==1 && it1.hasNext()) || !it2.hasNext() ){
            return it1.next();
        }
        else if((count%2==0 && it2.hasNext()) || !it1.hasNext()){
            return it2.next();
        }
        return -1;
    }

    public boolean hasNext() {
        return it1.hasNext() || it2.hasNext();
    }
}