class NestedInteger:
def isInteger(self) -> bool:
"""
@return True if this NestedInteger holds a single integer, rather than a nested list.
"""
def getInteger(self) -> int:
"""
@return the single integer that this NestedInteger holds, if it holds a single integer
Return None if this NestedInteger holds a nested list
"""
def getList(self) -> [NestedInteger]:
"""
@return the nested list that this NestedInteger holds, if it holds a nested list
Return None if this NestedInteger holds a single integer
"""
所以用的时候，只能用这三个api来获取数据。。
做的方法，是一进来先递归展开数据，然后next的时候一个个pop出去
class NestedIterator:
def __init__(self, nestedList):
self.data = []
def getList(nestedList):
for i in nestedList:
if i.isInteger():
self.data.append(i.getInteger())
else:
getList(i.getList())
getList(nestedList)
def next(self) -> int:
return self.data.pop(0)
def hasNext(self) -> bool:
if self.data:
return True
else:
return False
Runtime: 72 ms, faster than 43.64% of Python3 online submissions for Flatten Nested List Iterator. Memory Usage: 16.4 MB, less than 100.00% of Python3 online submissions for Flatten Nested List Iterator.
迭代器版本
class NestedIterator:
def __init__(self, nestedList):
def build(nestedList):
for i in nestedList:
if i.isInteger():
yield i.getInteger()
else:
i = i.getList()
for j in build(i):
yield j
self.g = build(nestedList)
def next(self) -> int:
return self.v
def hasNext(self) -> bool:
try:
self.v = next(self.g)
return True
except:
return False
Runtime: 64 ms, faster than 84.98% of Python3 online submissions for Flatten Nested List Iterator.
Memory Usage: 16.5 MB, less than 100.00% of Python3 online submissions for Flatten Nested List Iterator.
yield就是一个return，但是可以返回多个值。提取的时候可以用一个for循环提取。
然后就成了一个迭代器，下一个值可以直接用next来取
光头大佬版本
意思是说，没必要初始化的时候把所有数字都拿出来，可以自己不断迭代啊。
class NestedIterator:
def __init__(self, nestedList):
self.stack = [[nestedList, 0]]
def next(self) -> int:
self.hasNext()
nestedList, i = self.stack[-1]
self.stack[-1][1] += 1
return nestedList[i].getInteger()
def hasNext(self) -> bool:
s = self.stack
while s:
nestedList, i = s[-1]
if i== len(nestedList):
s.pop()
else:
x=nestedList[i]
if x.isInteger():
return True
s[-1][1]+=1
s.append([x.getList(),0])
return False
Runtime: 76 ms, faster than 28.80% of Python3 online submissions for Flatten Nested List Iterator.
Memory Usage: 16.4 MB, less than 100.00% of Python3 online submissions for Flatten Nested List Iterator.
虽然看起来很酷，但效率似乎不咋地。
不用堆栈
class NestedIterator:
def __init__(self, nestedList):
self.data = nestedList
self.cur = -1
self.inneriter = None
def next(self) -> int:
if self.inneriter:
return self.inneriter.next()
return self.data[self.cur].getInteger()
def hasNext(self) -> bool:
if self.inneriter and self.inneriter.hasNext():
return True
self.inneriter = None
if self.cur < len(self.data)-1:
self.cur += 1
if self.data[self.cur].isInteger():
return True
self.inneriter = NestedIterator(self.data[self.cur].getList())
if self.inneriter.hasNext():
return True
self.inneriter = None
return self.hasNext()
return False
Runtime: 76 ms, faster than 28.80% of Python3 online submissions for Flatten Nested List Iterator.
Memory Usage: 16.3 MB, less than 100.00% of Python3 online submissions for Flatten Nested List Iterator.