LintCode 541. Zigzag Iterator II 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/zigzag-iterator-ii/

Follow up Zigzag Iterator: What if you are given k 1d vectors? How well can your code be extended to such cases? 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”.

Example

Given k = 3 1d vectors:

[1,2,3]
[4,5,6,7]
[8,9]

Return [1,4,8,2,5,9,3,6,7].

解题思路

Zigzag Iterator的follow up问题,当input是k个list的情况,如何构造穿梭于数组的iterator。

关键点:两个list的时候,只要建两个list对应的iterator。k个list的时候,拓展为建一个装有各list的iterator的list。以这个装有所有iterator的list来操作,如果当前iterator所在的list还有next(),那么turns = (turns + 1) % list的size()。如果没有了,那么先remove这个iterator,再模运算turns = turns % list的size(),即跳入到下一个相邻的list的iterator。

参考代码

public class ZigzagIterator2 { 
    /** 
     * @param vecs a list of 1d vectors 
     */ 
      
    public List<Iterator<Integer>> iterators; 
    public int turns; 
     
    public ZigzagIterator2(ArrayList<ArrayList<Integer>> vecs) { 
        // initialize your data structure here. 
        iterators = new ArrayList<Iterator<Integer>>(); 
        for (ArrayList<Integer> vec : vecs) { 
            if (vec.size() > 0) { 
                iterators.add(vec.iterator()); 
            } 
        } 
        turns = 0; 
    } 
 
    public int next() { 
        int element = iterators.get(turns).next(); 
        if (iterators.get(turns).hasNext()) { 
            turns = (turns + 1) % iterators.size(); 
        } else { 
            iterators.remove(turns); 
            if (iterators.size() > 0) { 
                turns = turns % iterators.size(); 
            } 
        } 
        return element; 
    } 
     
    public boolean hasNext() { 
        return iterators.size() > 0; 
    } 
} 
 
/** 
 * Your ZigzagIterator2 object will be instantiated and called as such: 
 * ZigzagIterator2 solution = new ZigzagIterator2(vecs); 
 * while (solution.hasNext()) result.add(solution.next()); 
 * Output result 
 */
 

相关题目

LintCode All in One 原创题目讲解汇总

LintCode 540. Zigzag Iterator 原创Java参考解答

发表评论

您的电子邮箱地址不会被公开。