Simple Java solution for K-vector


  • 141
    K

    Uses a linkedlist to store the iterators in different vectors. Every time we call next(), we pop an element from the list, and re-add it to the end to cycle through the lists.

    public class ZigzagIterator {
        LinkedList<Iterator> list;
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            list = new LinkedList<Iterator>();
            if(!v1.isEmpty()) list.add(v1.iterator());
            if(!v2.isEmpty()) list.add(v2.iterator());
        }
    
        public int next() {
            Iterator poll = list.remove();
            int result = (Integer)poll.next();
            if(poll.hasNext()) list.add(poll);
            return result;
        }
    
        public boolean hasNext() {
            return !list.isEmpty();
        }
    }

  • 0
    A

    Iterator poll = list.remove(0);


  • 12

    Very nice solution, for better, list can be declared as Queue<Iterator> list; and use Queue's interface function (poll & offer)


  • 1
    V

    Use Deque.

    Deque<Iterator> queue;


  • 11
    O

    Great solution. This is so easy to extend to k-list case. Here I use a Queue interface taking @pinkfloyda's suggestion.

    public class ZigzagIterator {
        
        // Better solution, 6ms
        Queue<Iterator> q;
    
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            q = new LinkedList();
            if (!v1.isEmpty()) q.offer(v1.iterator());
            if (!v2.isEmpty()) q.offer(v2.iterator());
        }
    
        public int next() {
            Iterator cur = q.poll();
            int res = (int) cur.next();
            if (cur.hasNext()) q.offer(cur);
            return res;
        }
    
        public boolean hasNext() {
            return q.peek() != null;
        }
    }
    
    /* Previous Solution 4ms 72%
    
    public class ZigzagIterator {
        int i;
        boolean odd;
        List<Integer> l1, l2;
        
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            i = 0;
            odd = false;
            l1 = v1; l2 = v2;
        }
    
        public int next() {
            odd ^= true;
            if (odd && i < l1.size()) {
                if (i < l2.size()) 
                    return l1.get(i);
                else {
                    odd ^= true;
                    return l1.get(i++);
                }
                
            }
            if (i < l2.size()) return l2.get(i++);
            return next();
        }
    
        public boolean hasNext() {
            return i < l1.size() || i < l2.size();
        }
    }
    */
    
    /**
     * Your ZigzagIterator object will be instantiated and called as such:
     * ZigzagIterator i = new ZigzagIterator(v1, v2);
     * while (i.hasNext()) v[f()] = i.next();
     */

  • 0

    Like your code.


  • 1
    L

    Very nice BFS like solution. It can be easily extended to k-vector input.


  • 0
    H

    Great Solution. I prefer Deque.

    public class ZigzagIterator {
        Deque<Iterator<Integer>> queue = new LinkedList<>();
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            if (!v1.isEmpty()) {
                queue.offer(v1.iterator());
            }
            if (!v2.isEmpty()) {
                queue.offer(v2.iterator());
            }
        }
    
        public int next() {
            Iterator<Integer> i = queue.poll();
            int ans = i.next();
            if (i.hasNext()) {
                queue.offer(i);
            }
            return ans;
        }
    
        public boolean hasNext() {
            return !queue.isEmpty();
        }
    }
    

  • 0

    @kevinhsu sorry to bother you, i have a stupid question.
    when we use list.add(poll), poll will not contain the element "result"?
    Does it means that iterator will remove the element when we use poll.next()?


  • 0

    Share:

    Iterator<Integer> iter1;
    Iterator<Integer> iter2;
    int iterIdx = 1;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        iter1 = v1.iterator();
        iter2 = v2.iterator();
    }
    
    public int next() {
        if(iterIdx == 1){
            iterIdx = 2;
            return iter1.next();
        } else {
            iterIdx = 1;
            return iter2.next();
        }
    }
    
    public boolean hasNext() {
        if(iterIdx == 1){
            if(iter1.hasNext()) return true;
            else {
                iterIdx = 2;
                return iter2.hasNext();
            }
        } else {
            if(iter2.hasNext()) return true;
            else {
                iterIdx = 1;
                return iter1.hasNext();
            }
        }
    }

  • 0

    Very nice! Much easier than mine. Thanks for sharing!


  • 0

    One simple question, why do we need to cast the output to (int) after calling .next()? From my opinion, the type of iterator we use are all Integer.


  • 0
    C

    @al9 no need. refer to api


  • 0
    C

    You must be an experienced coder.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.