-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0341 [M] Flatten Nested List Iterator
Code with Senpai edited this page Apr 5, 2021
·
1 revision
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#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
# """
class NestedIterator:
def flatten(self, nestedList):
if not nestedList:
return
else:
for i, x in enumerate(nestedList):
if x.isInteger():
self.Q.append(x)
else:
self.flatten(x.getList())
def __init__(self, nestedList: [NestedInteger]):
self.Q = deque()
self.flatten(nestedList)
def next(self) -> int:
return self.Q.popleft()
def hasNext(self) -> bool:
return len(self.Q)
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
without preprocessing:
class NestedIterator(object):
def __init__(self, nestedList):
self.stack = [[nestedList, 0]]
def next(self):
self.hasNext()
nestedList, i = self.stack[-1]
self.stack[-1][1] += 1
return nestedList[i].getInteger()
def hasNext(self):
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
class NestedIterator(object):
def __init__(self, nestedList):
self.st = [iter(nestedList)]
## tmp storage for next element, when initializing we move the first element into it.
self.nextEle = None
self.next()
def next(self):
if self.nextEle is not None:
ret = self.nextEle
self.nextEle = None
self.next()
return ret
ele = None
## take top iter and advance it to the next element, while iter reach None, pop it.
while self.st and ele is None:
it = self.st[-1]
ele = next(it, None)
if ele is None:
self.st.pop()
## reach empty st.
if not ele:
return
if ele.isInteger():
self.nextEle = ele.getInteger()
## when element is a list, append another layer of iter to stack, call next() again.
else:
self.st.append(iter(ele.getList()))
self.next()
def hasNext(self):
return self.nextEle is not None
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stack = [[nestedList, 0]]
def make_stack_top_an_integer(self):
while self.stack:
# Essential for readability :)
current_list = self.stack[-1][0]
current_index = self.stack[-1][1]
# If the top list is used up, pop it and its index.
if len(current_list) == current_index:
self.stack.pop()
continue
# Otherwise, if it's already an integer, we don't need
# to do anything.
if current_list[current_index].isInteger():
break
# Otherwise, it must be a list. We need to increment the index
# on the previous list, and add the new list.
new_list = current_list[current_index].getList()
self.stack[-1][1] += 1 # Increment old.
self.stack.append([new_list, 0])
def next(self) -> int:
self.make_stack_top_an_integer()
current_list = self.stack[-1][0]
current_index = self.stack[-1][1]
self.stack[-1][1] += 1
return current_list[current_index].getInteger()
def hasNext(self) -> bool:
self.make_stack_top_an_integer()
return len(self.stack) > 0
footer