LeetCode 341题 “Flatten Nested List Iterator” 是一个中等难度的题目，主要考察的是设计数据结构和迭代器的概念。题目要求你设计一个迭代器来扁平化一个嵌套的列表。
题目描述
给你一个嵌套的整型列表 nestedList，实现一个迭代器将其扁平化。
示例：
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
解题思路
- 理解嵌套列表：嵌套列表可以包含整数或其他的嵌套列表。
- 迭代器设计：需要实现两个方法
next()和hasNext()。 - 栈的使用：使用栈来存储待处理的嵌套列表，这样可以方便地进行回溯。
具体实现
我们可以使用一个栈来存储待处理的元素，每次调用 next() 时，从栈顶取出一个元素。如果这个元素是整数，直接返回；如果是列表，将其展开并逆序压入栈中。
Python代码实现
# """
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 init(self, nestedList: [NestedInteger]): self.stack = []
初始化时，将nestedList逆序压入栈中
for item in reversed(nestedList):
self.stack.append(item)
def next(self) -> int:
# next()方法返回栈顶的整数
return self.stack.pop().getInteger()
def hasNext(self) -> bool:
# hasNext()方法检查栈顶元素是否为整数，如果不是，则展开
while self.stack:
top = self.stack[-1]
if top.isInteger():
return True
self.stack.pop()
# 将列表中的元素逆序压入栈中
for item in reversed(top.getList()):
self.stack.append(item)
return FalseYour NestedIterator object will be instantiated and called as such:
i, v = NestedIterator(nestedList), []
while i.hasNext(): v.append(i.next())
解释
- 初始化：在
__init__方法中，我们将输入的nestedList逆序压入栈中。 - next() 方法：直接从栈顶取出一个整数并返回。
- hasNext() 方法：检查栈顶元素，如果是整数，返回
True；如果是列表，将其展开并逆序压入栈中，继续检查。
复杂度分析
- 时间复杂度：
next()和hasNext()方法的时间复杂度均为 O(1) 平摊。 - 空间复杂度：O(N)，其中 N 是嵌套列表的最大深度。
通过这种方式，我们可以高效地扁平化嵌套列表并进行迭代。希望这个解释对你理解并解决这个题目有所帮助！如果有更多问题，欢迎继续提问。
发表回复