LC 0341 [M] Flatten Nested List Iterator - ALawliet/algorithms GitHub Wiki

# """
# 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](/ALawliet/algorithms/wiki/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](/ALawliet/algorithms/wiki/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