193 - 341 扁平化嵌套列表迭代器

题目

给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的项或者为一个整数，或者是另一个列表。

示例 1:

输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1] 解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2:

输入: [1,[4,[6]]] 输出: [1,4,6] 解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,4,6]。

解答

这个嵌套的列表，还不是普通的list，它是一种类型，有固定的三个api。。

 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来取

光头大佬版本

https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80146/Real-iterator-in-Python-Java-C%2B%2B

意思是说，没必要初始化的时候把所有数字都拿出来，可以自己不断迭代啊。

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.

好吧看不太懂。。。