No.0022-CareerCup

问题描述

英文版太长就不贴了。大意是给出一组iterator，要求设计一个新的iterator，来按照顺序每次从一个iterator中取出一个元素，空的则跳过。
例如，A=[1,2,3],B=[a,b,c],C=[f,7]，结果应该是[1,a,f,2,b,7,3,c]。

询问补充

思路分析

简单思路

直白的思路就是，先把元素按顺序取出来，然后再生成一个新的iterator。

改进

前一个解法的改进就是，不取出来，直接造iterator。
基本想法就是每次提取元素之后调整里面的一组iterator。
关键就在于维持顺序。
假如以list为顺序，每次到末尾再从头开始，也不是不行，但是对于空的iterator，不移除的话影响效率，移除也有相对较高的时间复杂度。
更好的数据结构是deque。一个iterator取出元素之后，pop掉，假如非空append到末尾，空的话就扔掉。这样的话基本就没有什么额外的开销。

代码

from collections import deque

class Solution:
    def __init__(self, L):
        self.dq = deque()
        for i in L:
            if i.hasnext()
                self.dq.append(i)

    def hasnext(self):
        return len(self.dq) > 0 and self.dq[0].hasnext()

    def next(self):
        t = self.dq.popleft()
        v = t.next()
        if t.hasnext():
            self.dq.append(t)
        return v


class hn_wrapper(object):
    def __init__(self, it):
        self.it = iter(it)
        self._hasnext = None

    def __iter__(self):
        return self

    def next(self):
        if self._hasnext:
            result = self._thenext
        else:
            result = next(self.it)
        self._hasnext = None
        return result

    def hasnext(self):
        if self._hasnext is None:
            try:
                self._thenext = next(self.it)
            except StopIteration:
                self._hasnext = False
            else:
                self._hasnext = True
        return self._hasnext


if __name__ == "__main__":
    a = Solution([hn_wrapper([1, 2, 3]), hn_wrapper(['a', 'b', 'c']), hn_wrapper(['f', 7])])
    while a.hasnext():
        print(a.next())

因为Python的iter天生没有hasnext()，所以搞了一个替代类。时间复杂度O(n)，空间复杂度O(n)。
之所以时间复杂度是O(n)，是因为开始把元素放入deque里面了。那么可不可以在获得值的时候再放呢？
其实没必要，因为先得筛选一遍，把没有next的剔除掉，不然的话中间一个没有next的混进来就会造成后面的就算有next也出不来。

总结

难度：easy~medium