341. 扁平化嵌套列表迭代器

发表于 分类于 阅读次数： 本文字数： 754 阅读时长 ≈ 3 分钟

这是今天的打卡题，说实在做得我实在是心态崩坏，先来看看题目，我再来细说：

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

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 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]。

  1. 扁平化嵌套列表迭代器 <– 传送门 力扣（LeetCode）

这个题目，最核心的麻烦，在于这个嵌套的列表是递归结构，我一开始没意识到这一点，随便写了个算法，只能处理一层链表，测试给出的两个用例，就被教育了。才意识到不能简单处理。

晚上睡了一觉，一醒来想起来题目，觉得应该用栈去解题。方法也很简单，遇到更深的嵌套，就是把当前遍历的列表和当前下标给压栈，如果下标越界了，就出栈。我犯的错误在哪里呢？就是我没想清楚，到底是在 next() 方法里进行入栈出栈操作，还是在 hasNext() 方法里操作。

一开始，我以为只在 next() 方法里进行入栈出栈操作就好了，然后分分钟被教育了，原来空链表也可以作为一个元素的，但是在 hasNext() 里，要返回 False 的，显然，hasNext() 也是要解包的。然后，我又犯了一个更致命的错误，我尝试在原来写好的代码上补救，除了之前在 next() 里写好的入栈出栈操作，我在 hasNext() 里又写了一遍。然后，就开始怎么都写不对，心态崩坏了，连续提交了 7 次都没过。

其实，这道题，思路清楚的话，就知道，有两个地方可以写入栈出栈的逻辑，一个是在构造的时候，一口气给解包了，后面就直接遍历单列表就行了。或者在 hasNext() 里解包，因为还有个已知条件，在代码模板里给出来的，就是每次必然会先调用 hasNext() 然后再调用 next()，所以，显然应该在 hasNext() 里准备好下标，然后 next() 很简短，无脑返回就好。

这都是我无数次失败才想明白的东西。最后，我贴个我最后一版提交过的代码吧，前面的那些垃圾，我就不放出来了，因为根本 AC 不了。

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 NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.nl = nestedList
        self.i, self.l, self.s = 0, len(self.nl), []
    
    def next(self) -> int:
        ele = self.nl[self.i].getInteger()
        self.i += 1
        return ele
    
    def hasNext(self) -> bool:
        while self.i < self.l or self.s:
            if self.i < self.l:
                ele = self.nl[self.i]
                if ele.isInteger():
                    return True
                else:
                    self.s.append((self.i, self.l, self.nl))
                    self.i, self.nl = 0, ele.getList()
                    self.l = len(self.nl)
            else:
                self.i, self.l, self.nl = self.s.pop()
                self.i += 1
        return Fals

代码里看到，我把列表长度也给加到栈里了。其实也不是很有必要，因为可以随时求出。就当我秀逗了吧。