[Leetcode] Zigzag Iterator Z形迭代器

SolomonXie 发布于2019-08-14 12:35 / 3015人阅读

摘要：用变量和取模来判断我们该取列表中的第几个迭代器。同样，由于每用完一个迭代器后都要移出一个，变量也要相应的更新为该迭代器下标的上一个下标。如果迭代器列表为空，说明没有下一个了。

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?
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].

双迭代器 复杂度

时间 O(N) 空间 O(1)

思路

该题实际上就是轮流取两个列表的下一个元素。我们存下两个列表的迭代器，然后用一个递增的turns变量和取模的方法来判断该取哪一个列表的元素。

代码

public class ZigzagIterator {
    
    Iterator it1;
    Iterator it2;
    int turns;

    public ZigzagIterator(List v1, List 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();
    }
}

后续 Follow Up

Q：如果输入是k个列表呢？
A：使用一个迭代器的列表来管理这些迭代器。用turns变量和取模来判断我们该取列表中的第几个迭代器。不同点在于，一个迭代器用完后，我们要将其从列表中移出，这样我们下次就不用再找这个空的迭代器了。同样，由于每用完一个迭代器后都要移出一个，turns变量也要相应的更新为该迭代器下标的上一个下标。如果迭代器列表为空，说明没有下一个了。

public class ZigzagIterator implements Iterator {
    
    List> itlist;
    int turns;

    public ZigzagIterator(List> list) {
        this.itlist = new LinkedList>();
        // 将非空迭代器加入列表
        for(Iterator 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 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;
    }
}

GPU云服务器云服务器 -迭代器迭代器数组迭代器迭代器对象

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64569.html

【LC总结】Iterator题目<Zigzag 1&2><BST>&

摘要：方法直接查找数组的位的迭代器，调用方法得到的整数即为要返回的元素。再写迭代器的方法返回指针元素的并让指针通过递归方法指向下一个元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

WelliJhon 2019-08-14 15:49 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
Zigzag Iterator

摘要：题目链接这道题是说有两个，来回返回两个里面的值，要求用来做。所以可以用两个来分别存这两个的值，再用一个指针来表示现在应该取哪个里面的值。这里用之后，如果一个循环结束，可以直接把它移除，然后就可以直接判断是否是空。 Zigzag Iterator 题目链接：https://leetcode.com/problems... 这道题是说有两个list，来回返回两个list里面的值，要求用it...

Meathill 2019-08-14 17:19 评论0 收藏0
LeetCode.6 Z 字形变换(zigzag-conversion)(JS)

摘要：看到这道题总觉得眼熟，做完之后恍然大悟，这不就是小学数学做的找规律一题目字形变换将一个给定字符串根据给定的行数，以从上往下从左到右进行字形排列。一当然是因为最近实在太忙了捂脸，几乎周周谁遭得住。看到这道题总觉得眼熟，做完之后恍然大悟，这不就是小学数学做的找规律一、题目 Z 字形变换：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 LEET...

cheukyin 2019-08-23 17:51 评论0 收藏0
leetcode 341 Flatten Nested List Iterator 以及其他Iter

摘要：返回的是表示是否走到了结尾。起到的就是缓存作用，因为调用之后马上就走到下一个了。如果调用，返回用得到和最初的输入相同的做相同的步骤存入不断拆开得到结果。思想就是来自括号，后面也会跟进的专题 Iterator其实就是一个单链表，无法回头看。java里很多数据结构都有这个接口，使用时需要initalize,得到一个iterator. 调用next()返回的是一个object, 指向的是下一...

chaosx110 2019-08-14 18:00 评论0 收藏0