数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
LeetCode | 力扣 | 难度 |
---|---|---|
341. Flatten Nested List Iterator | 341. 扁平化嵌套列表迭代器 | 🟠 |
———–
刷题插件 集成了手把手刷二叉树功能,按照公式和套路讲解了 150 道二叉树题目,可手把手带你刷完二叉树分类的题目,迅速掌握递归思维。
这是力扣第 341 题「 扁平化嵌套列表迭代器」,我来描述一下题目:
首先,现在有一种数据结构 NestedInteger
,这个结构中存的数据可能是一个 Integer
整数,也可能是一个 NestedInteger
列表。注意,这个列表里面装着的是 NestedInteger
,也就是说这个列表中的每一个元素可能是个整数,可能又是个列表,这样无限递归嵌套下去……
NestedInteger
有如下 API:
public class NestedInteger {
// 如果其中存的是一个整数,则返回 true,否则返回 false
public boolean isInteger();
// 如果其中存的是一个整数,则返回这个整数,否则返回 null
public Integer getInteger();
// 如果其中存的是一个列表,则返回这个列表,否则返回 null
public List<NestedInteger> getList();
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NestedInteger {
public:
// 如果其中存的是一个整数,则返回 true,否则返回 false
bool isInteger();
// 如果其中存的是一个整数,则返回这个整数,否则返回 null
int getInteger();
// 如果其中存的是一个列表,则返回这个列表,否则返回 null
vector<NestedInteger> getList();
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NestedInteger:
def isInteger(self) -> bool:
"""
如果其中存的是一个整数,则返回 True,否则返回 False
"""
pass
def getInteger(self) -> int:
"""
如果其中存的是一个整数,则返回这个整数,否则返回 None
"""
pass
def getList(self) -> List['NestedInteger']:
"""
如果其中存的是一个列表,则返回这个列表,否则返回 None
"""
pass
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NestedInteger struct {}
// 如果其中存的是一个整数,则返回 true,否则返回 false
func (ni NestedInteger) isInteger() bool {}
// 如果其中存的是一个整数,则返回这个整数,否则返回 null
func (ni NestedInteger) getInteger() int {}
// 如果其中存的是一个列表,则返回这个列表,否则返回 null
func (ni NestedInteger) getList() []NestedInteger {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NestedInteger = {
// 如果其中存的是一个整数,则返回 true,否则返回 false
isInteger: function () {},
// 如果其中存的是一个整数,则返回这个整数,否则返回 null
getInteger: function () {},
// 如果其中存的是一个列表,则返回这个列表,否则返回 null
getList: function () {}
};
我们的算法会被输入一个 NestedInteger
列表,我们需要做的就是写一个迭代器类,将这个带有嵌套结构 NestedInteger
的列表「拍平」:
public class NestedIterator implements Iterator<Integer> {
// 构造器输入一个 NestedInteger 列表
public NestedIterator(List<NestedInteger> nestedList) {}
// 返回下一个整数
public Integer next() {}
// 是否还有下一个元素?
public boolean hasNext() {}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NestedIterator: public Iterator<int> {
public:
// 构造器输入一个 NestedInteger 列表
NestedIterator(vector<NestedInteger> &nestedList) {}
// 返回下一个整数
int next() {}
// 是否还有下一个元素?
bool hasNext() {}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NestedIterator:
def __init__(self, nestedList: List[NestedInteger]):
# 构造器输入一个 NestedInteger 列表
pass
# 返回下一个整数
def next(self) -> int:
pass
# 是否还有下一个元素?
def hasNext(self) -> bool:
pass
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NestedInteger struct{}
type NestedIterator struct{}
// 构造器输入一个 NestedInteger 列表
func Constructor(nestedList []*NestedInteger) *NestedIterator {}
// 返回下一个整数
func (iter *NestedIterator) Next() int {}
// 是否还有下一个元素?
func (iter *NestedIterator) HasNext() bool {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NestedIterator = function(nestedList) {
// 构造器输入一个 NestedInteger 列表
}
// 返回下一个整数
NestedIterator.prototype.next = function() {}
// 是否还有下一个元素?
NestedIterator.prototype.hasNext = function() {}
我们写的这个类会被这样调用,先调用 hasNext
方法,后调用 next
方法:
NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
print(i.next());
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
NestedIterator i(nestedList);
while (i.hasNext())
print(i.next());
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
i = NestedIterator(nestedList)
while i.hasNext():
print(i.next())
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
i := &NestedIterator{nestedList}
for i.hasNext() {
fmt.Println(i.next())
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var i = new NestedIterator(nestedList);
while (i.hasNext())
print(i.next());
比如示例 1,输入的列表里有三个 NestedInteger
,两个列表型的 NestedInteger
和一个整数型的 NestedInteger
。
学过设计模式的朋友应该知道,迭代器也是设计模式的一种,目的就是为调用者屏蔽底层数据结构的细节,简单地通过 hasNext
和 next
方法有序地进行遍历。
为什么说这个题目很有启发性呢?因为我最近在用一款类似印象笔记的软件,叫做 Notion(挺有名的)。这个软件的一个亮点就是「万物皆 block」,比如说标题、页面、表格都是 block。有的 block 甚至可以无限嵌套,这就打破了传统笔记本「文件夹」->「笔记本」->「笔记」的三层结构。
回想这个算法问题,NestedInteger
结构实际上也是一种支持无限嵌套的结构,而且可以同时表示整数和列表两种不同类型,我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。
那么话说回来,对于这个算法问题,我们怎么解决呢?NestedInteger
结构可以无限嵌套,怎么把这个结构「打平」,为迭代器的调用者屏蔽底层细节,得到扁平化的输出呢?
_____________
应合作方要求,本文不便在此发布,请扫码关注回复关键词「迭代器」或 点这里 查看:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释