Zigzag Iterator II

Description

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

Example1

Input: k = 3
vecs = [
    [1,2,3],
    [4,5,6,7],
    [8,9],
]
Output: [1,4,8,2,5,9,3,6,7]

Example2

Input: k = 3
vecs = [
    [1,1,1]
    [2,2,2]
    [3,3,3]
]
Output: [1,2,3,1,2,3,1,2,3]
思路:

用k个指针维护每个数组的当前最靠前的元素,循环枚举这k个指针,每次枚举到就在答案序列中将该数加入,如果指针到了该数组的尾部,那么就不作处理

 
public class ZigzagIterator2 {
    
    public List<Iterator<Integer>> its;
    public int turns;

    /**
     * @param vecs a list of 1d vectors
     */
    public ZigzagIterator2(List<List<Integer>> vecs) {
        // initialize your data structure here.
        this.its = new ArrayList<Iterator<Integer>>();
        for (List<Integer> vec : vecs) {
            if (vec.size() > 0)
                its.add(vec.iterator());
        }
        turns = 0;
    }

    public int next() {
        // Write your code here
        int elem = its.get(turns).next();
        if (its.get(turns).hasNext())
            turns = (turns + 1) % its.size();
        else {
            its.remove(turns);
            if (its.size() > 0) 
                turns %= its.size();
        }
        return elem;
    }

    public boolean hasNext() {
        // Write your code here
        return its.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
 */

  

上一篇:LeetCode每日一题(一)


下一篇:美语初级 L041:Going Camping 解析