LeetCode 281 - Zigzag Iterator


http://blog.csdn.net/jmspan/article/details/51148390
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?
Clarification for the follow up question - Update (2015-09-18):
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". For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].
X.
https://discuss.leetcode.com/topic/24231/short-java-o-1-space
Two iterators, one for each list. Switching them before reading the next number instead of afterwards saves a bit of code, I think.
    private Iterator<Integer> i, j, tmp;

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

    public int next() {
        if (j.hasNext()) { tmp = j; j = i; i = tmp; }
        return i.next();
    }

    public boolean hasNext() {
        return i.hasNext() || j.hasNext();
    }
http://www.cnblogs.com/airwindow/p/4805995.html
    Iterator<Integer> cur_iterator;
    Iterator<Integer> iterator1;
    Iterator<Integer> iterator2;
    
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.iterator1 = v1.iterator();
        this.iterator2 = v2.iterator();
        this.cur_iterator = (this.iterator1.hasNext() ? this.iterator1 : this.iterator2);
    }

    public int next() {
        int ret = cur_iterator.next();
        if (cur_iterator == iterator1) {
            if (iterator2.hasNext()) {
                cur_iterator = iterator2;
            }
        } else{
            if (iterator1.hasNext()) {
                cur_iterator = iterator1;
            }
        }
        return ret;
    }

    public boolean hasNext() {
        return cur_iterator.hasNext();
    }
X.
https://discuss.leetcode.com/topic/26654/simple-java-solution-for-k-vector
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.
    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();
    }
https://discuss.leetcode.com/topic/30615/clean-java-solution-works-for-k-lists
    List<Iterator<Integer>> itrs;
    int idx;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        itrs = new ArrayList<Iterator<Integer>>();
        itrs.add(v1.iterator());
        itrs.add(v2.iterator());
        idx = 0;
    }

    public int next() {
        hasNext();
        int val = itrs.get(idx).next();
        idx = (idx + 1) % itrs.size();
        return val;
    }

    public boolean hasNext() {
     if(itrs.size()==0)
         return false;
     else if(itrs.get(idx).hasNext())
         return true;
     else {
            do {
             itrs.remove(idx);
             if(itrs.size()==0)
              return false;
             idx = (idx+1)%itrs.size();
         } while(!itrs.get(idx).hasNext());
         return true;
     }
    }
https://discuss.leetcode.com/topic/24193/java-o-n-solution-for-k-vector
    Iterator<Integer>[] its;
    int pos;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        its = new Iterator[]{v1.iterator(), v2.iterator()};
        pos = 0;
    }

    public int next() {
        int next = its[pos].next();
        pos = (pos == its.length - 1) ? 0 : pos + 1;
        return next;
    }

    public boolean hasNext() {
        if (its[pos].hasNext()) return true;
        for (int i = pos + 1; i < its.length; i++) {
            if (its[i].hasNext()) {
                pos = i;
                return true;
            }
        }
        for (int i = 0; i < pos; i++) {
            if (its[i].hasNext()) {
                pos = i;
                return true;
            }
        }
        return false;
    }
https://discuss.leetcode.com/topic/26654/simple-java-solution-for-k-vector
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.
    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();
    }
https://discuss.leetcode.com/topic/24201/java-clean-solution-for-k-lists

https://tenderleo.gitbooks.io/leetcode-solutions-/content/GoogleMedium/281.html
     List<List<Integer>> lists = new ArrayList<>();                                 
      int p = 0; // which list                 
      int q = 0; // current index in current list;                                   
      int[] indices = new int[2];                                    
      public ZigzagIterator(List<Integer> v1, List<Integer> v2) {                    
       lists.add(v1);   
       lists.add(v2);                  
       indices[0] = indices[1] = 0;                    
      }                                                                              

      public int next() {                                                            
          int val = lists.get(p).get(q);                                             
          indices[p] = q+1;                                                          
          p = 1-p;                                                                   
          q = indices[p];                                                            
          return val;                                                                
      }                                                                              

      public boolean hasNext() {                                                     
          if(lists.get(p).size() > indices[p]) return true;                          
          else{                                                                      
              p = 1-p;                                                               
              q = indices[p];                                                        
              return lists.get(p).size() > q;                                        
          }                                                                          
      }

Zigzag Iterator | tech::interview
Suppose you have a Iterator class with has_next() and get_next() methods.
Please design and implement a ZigzagIterator class as a wrapper of two iterators.
For example, given two iterators:
i0 = [1,2,3,4]
i1 = [5,6]
ZigzagIterator it(i0, i1);

while(it.has_next()) {
    print(it.get_next());
}
The output of the above pseudocode would be [1,5,2,6,3,4].
写一个变形的iterator，给定两个iterator，让两个iterator进行交互输出。
例子：
A: 1234
B: abcd
则输出为：1a2b3c4d，如果一个读完了那就读没读完那个直到两个都读完为止。
http://shibaili.blogspot.com/2015/08/notes-from-others.html
class ZigZagIterator() {
    ZigZagIterator(vector<Iterator> &itrs) {
        this->itrs = itrs;
        pointer = 0;
        if (!itrs[pointer].hasNext()) setNextAvailable();
    } 
    void setNextAvailable() {
        int old = pointer;
        while (true) {
            pointer++;
            pointer %= itrs.size();
            if (itrs[pointer].hasNext()) {
                return;   
            }    
            if (pointer == old) {
                pointer = -1;
                return;
            }
        }
    }
    bool hasNext() {
        return pointer == -1;   
    }
     
    int next() {
        int ret = itrs[pointer];
        setNextAvailable();
        return ret;
    }
     
private:
    vector<Iterator> itrs;
    int pointer;
};



class ZigzagIterator {



public:



ZigzagIterator(Iterator& a, Iterator& b) :_its{a,b} {



_pointer = a.has_next() ? 0 : 1;



}







int get_next() {



int ret = _its[_pointer].get_next(), old = _pointer;



do {



if(++_pointer >= 2) _pointer = 0;



} while(!_its[_pointer].has_next() && _pointer != old);



return ret;



}







bool has_next() { return _its[_pointer].has_next(); }



private:



Iterator _its[2];



int _pointer;



};
http://yuanhsh.iteye.com/blog/2228675
  1. public class ZigzagIterator {  
  2.     Iterator i0, i1;  
  3.     Iterator it;  
  4.     public ZigzagIterator(Iterator i0, Iterator i1) {  
  5.         this.i0 = i0; this.i1 = i1;  
  6.         this.it = i0.hasNext()? i0:i1;  
  7.     }  
  8.       
  9.     public boolean has_next() {  
  10.         return it.hasNext();  
  11.     }  
  12.       
  13.     public int get_next() {  
  14.         int val = (Integer)it.next();  
  15.         if(it == i0 && i1.hasNext())  
  16.             it = i1;  
  17.         else if(it == i1 && i0.hasNext())  
  18.             it = i0;  
  19.         return val;  
  20.     }  
  21. }  
第二种解法，这个方便解有多个Iterator的情况，也就是followup的问题：
  1. class ZigzagIterator {  
  2. private:  
  3.     vector<Iterator> vec;  
  4.     vector<Iterator>::iterator it;  
  5. public:  
  6.     ZigzagIterator(Iterator& i0, Iterator& i1) {  
  7.         vec = {i0, i1};  
  8.         it = vec.begin();  
  9.         while(!(*it).has_next()) it++;  
  10.     }  
  11.   
  12.     bool has_next() {  
  13.         return (*it).has_next();  
  14.     }  
  15.       
  16.     int get_next() {  
  17.         auto prev = it;  
  18.         int val = (*it).get_next();  
  19.         do {  
  20.             if(++it == vec.end())  
  21.                 it = vec.begin();  
  22.         } while(!(*it).has_next() && it != prev);  
  23.         return val;  
  24.     }  
  25. };  
http://segmentfault.com/a/1190000003786218
该题实际上就是轮流取两个列表的下一个元素。我们存下两个列表的迭代器，然后用一个递增的turns变量和取模的方法来判断该取哪一个列表的元素。
public class ZigzagIterator {
    
    Iterator<Integer> it1;
    Iterator<Integer> it2;
    int turns;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.it1 = v1.iterator();
        this.it2 = v2.iterator();
        turns = 0;
    }

    public int next() {
        // 如果没有下一个则返回0
        if(!hasNext()){
            return 0;
        }
        turns++;
        // 如果是第奇数个，且第一个列表也有下一个元素时，返回第一个列表的下一个
        // 如果第二个列表已经没有，返回第一个列表的下一个
        if((turns % 2 == 1 && it1.hasNext()) || (!it2.hasNext())){
            return it1.next();
        // 如果是第偶数个，且第二个列表也有下一个元素时，返回第二个列表的下一个
        // 如果第一个列表已经没有，返回第二个列表的下一个
        } else if((turns % 2 == 0 && it2.hasNext()) || (!it1.hasNext())){
            return it2.next();
        }
        return 0;
    }

    public boolean hasNext() {
        return it1.hasNext() || it2.hasNext();
    }
}
Q：如果输入是k个列表呢？
A：使用一个迭代器的列表来管理这些迭代器。用turns变量和取模来判断我们该取列表中的第几个迭代器。不同点在于，一个迭代器用完后，我们要将其从列表中移出，这样我们下次就不用再找这个空的迭代器了。同样，由于每用完一个迭代器后都要移出一个，turns变量也要相应的更新为该迭代器下标的上一个下标。如果迭代器列表为空，说明没有下一个了。
public class ZigzagIterator implements Iterator<Integer> {
    
    List<Iterator<Integer>> itlist;
    int turns;

    public ZigzagIterator(List<Iterator<Integer>> list) {
        this.itlist = new LinkedList<Iterator<Integer>>(); // use ArrayList
        // 将非空迭代器加入列表
        for(Iterator<Integer> it : list){
            if(it.hasNext()){
                itlist.add(it);
            }
        }
        turns = 0;
    }

    public Integer next() {
        if(!hasNext()){
            return 0;
        }
        Integer res = 0;
        // 算出本次使用的迭代器的下标
        int pos = turns % itlist.size();
        Iterator<Integer> curr = itlist.get(pos);
        res = curr.next();
        // 如果这个迭代器用完，就将其从列表中移出
        if(!curr.hasNext()){
            itlist.remove(turns % itlist.size());
            // turns变量更新为上一个下标
            turns = pos - 1;
        }
        turns++;
        return res;
    }

    public boolean hasNext() {
        return itlist.size() > 0;
    }
}
http://blog.csdn.net/xudli/article/details/48749219

http://www.codescream.com/ContentDisplay?targetContent=RoundRobinIterator
The three biggest things to watch out for are:
  • Making next() and hasNext() work together - hasNext() must be able to locate the next element to know one exists, and next() should defer to hasNext() to ensure that a next element does exist before trying to return one.
  • Ensuring that you correctly reset the iterator which moves over the sub-list iterators each time it reaches the end of the iterator list. You will move over the list of iterators many times as you are only taking one item from each sub-list on each pass.
  • Remove sub-lists using the Iterator.remove() method once you determine they have no elements left. This lets you track your "finished" condition easily; you are finished once no iterators remain in your list of iterators.
  1.     //Define the iterator position in the overall list of iterators
  2.     //and the list of iterators itself.
  3.     private Iterator<Iterator<Integer>> iter;
  4.     private List<Iterator<Integer>> iterators;

  6.     //The next value to be returned.  If null, the next value has
  7.     //not been located yet.
  8.     private Integer nextValue;

  10.     public RoundRobinIterator(List<Iterator<Integer>> iterators) {

  12.         //Gets an iterator over a list of iterators.
  13.         iter = iterators.iterator();
  14.         this.nextValue = null;
  15.         this.iterators = iterators;
  16.     }

  18.     @Override
  19.     public Integer next() {
  20.         if (!hasNext())
  21.             throw new NoSuchElementException();
  22.         Integer n = nextValue;
  23.         nextValue = null;
  24.         return n;
  25.     }

  27.     @Override
  28.     public boolean hasNext() {
  29.         return nextValue != null || setNext();
  30.     }

  32.     private boolean setNext() {

  34.         //If we've already found the next element, do nothing.
  35.         if (nextValue != null) return true;

  37.         //Loop until we determine the next element or that no elements remain.
  38.         while (true) {

  40.             //If we're at the end of the list of iterators, restart at the beginning, assuming
  41.             //any of the contained lists have remaining elements.
  42.             if (!iter.hasNext()) {
  43.                 if (!iterators.isEmpty()) iter = iterators.iterator();
  44.                 else return false;
  45.             }

  47.             //Get the next iterator from the list of iterators, assuming we're
  48.             //not at the last one already.
  49.             if (iter.hasNext()) {
  50.                 Iterator<Integer> currentIter = iter.next();

  52.                 //If the iterator we are positioned at has more elements left in its
  53.                 //sub-list, then take the next element and return it.  If no elements remain
  54.                 //then remove the iterator from the round-robin iterator list for good.
  55.                 if (currentIter.hasNext()) {
  56.                     nextValue = currentIter.next();
  57.                     return true;
  58.                 }
  59.                 else {
  60.                     iter.remove();
  61.                 }
  62.             }
  63.         }
  64.     }
Related: http://buttercola.blogspot.com/2015/11/zenefits-zigzag-iterator-column-major.html
  public static class ZigZagIterator {
    private List<Iterator<Integer>> iterators;
    private Queue<Iterator<Integer>> queue;
     
    public ZigZagIterator(List<Iterator<Integer>> iterators) {
      this.iterators = iterators;
      queue = new LinkedList<>();
       
      for (Iterator<Integer> iterator : iterators) {
        if (iterator.hasNext()) {
          queue.add(iterator);
        }
      }
       
    }
     
    public boolean hasNext() {
      return !queue.isEmpty();
    }
     
    public Integer next() {
      Iterator<Integer> currIterator = queue.poll();
      Integer result = currIterator.next();
      if (currIterator.hasNext()) {
        queue.offer(currIterator);
      }
       
      return result;
    }
  }
Read full article from Zigzag Iterator | tech::interview
at
Labels: , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts