Monday, September 14, 2015

Leetocode: Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
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?

Code (Java):
public class ZigzagIterator {
    private List<Integer> v1;
    private List<Integer> v2;
    private int i;
    private int j;
    private int listId;

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

    public int next() {
        int result = 0;
        if (i >= v1.size()) {
            result = v2.get(j);
            j++;
        } else if (j >= v2.size()) {
            result = v1.get(i);
            i++;
        } else {
            if (listId == 0) {
                result = v1.get(i);
                i++;
                listId = 1;
            } else {
                result = v2.get(j);
                j++;
                listId = 0;
            }
        }
        
        return result;
    }

    public boolean hasNext() {
        return i < v1.size() || j < 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(); */ Update on 5/14/19:
public class ZigzagIterator {
    /*
    * @param v1: A 1d vector
    * @param v2: A 1d vector
    */
    private Iterator<Integer> it1;
    private Iterator<Integer> it2;
    private int count = 0;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // do intialization if necessary
        it1 = v1.iterator();
        it2 = v2.iterator();
        count = 0;
    }

    /*
     * @return: An integer
     */
    public int next() {
        int ans = 0;
        // write your code here
        if (!it1.hasNext()) {
            ans = (Integer)it2.next();
        } else if (!it2.hasNext()) {
            ans = (Integer)it1.next();
        } else if (count == 0) {
            ans = (Integer) it1.next();
            count = 1;
        } else {
            ans = (Integer) it2.next();
            count = 0;
        }

        return ans;
    }

    /*
     * @return: True if has next
     */
    public boolean hasNext() {
        // write your code here
        return it1.hasNext() || it2.hasNext();
    }
}

/**
 * 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
 */

3 comments:

  1. Awsome post thank you sharing post on Nice post ! Thanks for sharing valuable information with us. Keep sharing..Ruby on Rails Online Training India

    ReplyDelete
  2. Very awesome!!! When I looked for it, I found this website at the top of all the blogs in the search engine. Indian visa for US citizen are available online. US citizens can apply for an Indian visa within 5 to 10 minutes. Firstly you can read all the document requirements for Indian visa for US citizens via our website then you can apply for your Indian visa.

    ReplyDelete
  3. Wow! I have read your article and it's so good I will share it with family and friends. I just informed the travelers that the visa to Turkey is easy to get through the online process. Travelers who wish to travel to Turkey can apply for it.

    ReplyDelete