Flatten Nested List Iterator

Posted on | Edited on | In | | Views:

341. Flatten Nested List

Given a nested List of Integers, implement an iterator to flatten it.

给一个嵌套数组, 要求做一个迭代器去把这个嵌套的数组压平

Example 1:
[[1, 1], 2, [1, 1]] 压平后 [1, 1, 2, 1, 1]

Example 2:
[1, [4, [6]]] 压平后 [1, 4, 6]

思路

迭代器, 就是需要我们去完成两个函数, 一个是next(), 另外一个是hasNext(). 对于这一题, 初始化的时候应该把给输入的数组存在栈里面. 由于栈的FILO的特性, 我们需要从后往前压.

对于hasNext()函数, 我们需要判断

  1. 栈是否为空, 如果为空, 则返回False
  2. 栈顶是否是Integer, 如果是, 则返回True
  3. 把栈顶的NestedList取出, 从后往前压入栈, 然后重复第一步

对于next()函数, 由于hasNext()保证了栈顶一定是Integer, 所以直接返回就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#class NestedInteger(object):
#    def isInteger(self):
#    def getInteger(self):
#    def getList(self):
class NestedIterator(object):
    def __init__(self, nestedList):
        self.stack = list()
        for i in reversed(range(len(nestedList))):
            self.stack.append(nestedList[i])
    
    def next(self):
        a = self.stack[-1].getInteger()
        self.stack.pop()
        return a
    
    def hasNext(self):
        while len(self.stack) != 0:
            if self.stack[-1].isInteger():
                return True
            cur = self.stack[-1].getList()
            self.stack.pop()
            for i in reversed(range(len(cur))):
                self.stack.append(cur[i])
        return False

EOF