問題描述
英文版太長就不貼了。大意是給出一組iterator，要求設(shè)計(jì)一個(gè)新的iterator臂聋，來按照順序每次從一個(gè)iterator中取出一個(gè)元素，空的則跳過或南。
例如孩等，A=[1,2,3],B=[a,b,c],C=[f,7]，結(jié)果應(yīng)該是[1,a,f,2,b,7,3,c]采够。
詢問補(bǔ)充
思路分析
簡單思路
直白的思路就是肄方，先把元素按順序取出來，然后再生成一個(gè)新的iterator蹬癌。
改進(jìn)
前一個(gè)解法的改進(jìn)就是权她，不取出來，直接造iterator逝薪。
基本想法就是每次提取元素之后調(diào)整里面的一組iterator隅要。
關(guān)鍵就在于維持順序。
假如以list為順序董济，每次到末尾再從頭開始步清，也不是不行，但是對(duì)于空的iterator，不移除的話影響效率廓啊，移除也有相對(duì)較高的時(shí)間復(fù)雜度欢搜。
更好的數(shù)據(jù)結(jié)構(gòu)是deque。一個(gè)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())
因?yàn)镻ython的iter天生沒有hasnext()，所以搞了一個(gè)替代類雌续。時(shí)間復(fù)雜度O(n)斩个，空間復(fù)雜度O(n)。
之所以時(shí)間復(fù)雜度是O(n)驯杜，是因?yàn)殚_始把元素放入deque里面了。那么可不可以在獲得值的時(shí)候再放呢做个？
其實(shí)沒必要鸽心，因?yàn)橄鹊煤Y選一遍，把沒有next的剔除掉居暖，不然的話中間一個(gè)沒有next的混進(jìn)來就會(huì)造成后面的就算有next也出不來顽频。
總結(jié)
難度：easy~medium
