扁平化嵌套列表迭代器
一、题目描述
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
}
int next() {
}
bool hasNext() {
}
};
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
*/
二、分析
- 首先，现在有一种数据结构NestedInteger，这个结构中存的数据可能是一个Integer整数，也可能是一个NestedInteger列表。
-
注意，这个列表里面装着的是NestedInteger，也就是说这个列表中的每一个元素可能是个整数，可能又是个列表，这样无限递归嵌套下去…… - NestedInteger有如下 API：
public class NestedInteger {
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger();
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger();
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList();
}
- 我们的算法会被输入一个NestedInteger列表，我们需要做的就是
写一个迭代器类，将这个带有嵌套结构NestedInteger的列表「拍平」：
public class NestedIterator implements Iterator<Integer> {
// 构造器输入一个 NestedInteger 列表
public NestedIterator(List<NestedInteger> nestedList) {}
// 返回下一个整数
public Integer next() {}
// 是否还有下一个整数？
public boolean hasNext() {}
}
方法一：
- 学过设计模式的朋友应该知道，迭代器也是设计模式的一种，
目的就是为调用者屏蔽底层数据结构的细节，简单地通过hasNext和next方法有序地进行遍历。 - NestedInteger结构实际上也是一种支持无限嵌套的结构，而且可以同时表示整数和列表两种不同类型，我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。
- 那么话说回来，对于这个算法问题，我们怎么解决呢？NestedInteger结构可以无限嵌套，怎么把这个结构「打平」，为迭代器的调用者屏蔽底层细节，扁平化地输出所有整数元素呢？
- 显然，NestedInteger这个神奇的数据结构是问题的关键，不过题目专门提醒我们：
You should not implement it, or speculate about its implementation.
我不应该去尝试实现NestedInteger这个结构，也不应该去猜测它的实现？为什么？凭什么？是不是题目在误导我？是不是我进行推测之后，这道题就不攻自破了？
- 你看，我可不是什么好孩子，你不让推测，我就偏偏要去推测！我反手就把NestedInteger这个结构给实现出来：
public class NestedInteger {
private Integer val;
private List<NestedInteger> list;
public NestedInteger(Integer val) {
this.val = val;
this.list = null;
}
public NestedInteger(List<NestedInteger> list) {
this.list = list;
this.val = null;
}
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger() {
return val != null;
}
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger() {
return this.val;
}
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList() {
return this.list;
}
}
- 嗯，其实这个实现也不难嘛，写出来之后，发现这玩意儿竟然……
class NestedInteger {
Integer val;
List<NestedInteger> list;
}
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
- 这玩意儿不就是棵 N 叉树吗？叶子节点是Integer类型，其val字段非空；其他节点都是
List<NestedInteger>类型，其val字段为空，但是list字段非空，装着孩子节点。 - 比如说输入是[[1,1],2,[1,1]]，其实就是如下树状结构：
- 好的，刚才题目说什么来着？把一个NestedInteger扁平化对吧？这不就
等价于遍历一棵 N叉树的所有「叶子节点」吗？我把所有叶子节点都拿出来，不就可以作为迭代器进行遍历了吗？ - N 叉树的遍历怎么整？
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child);
- 这个框架可以遍历所有节点，而我们只对整数型的NestedInteger感兴趣，也就是我们只想要「
叶子节点」，所以traverse函数只要在到达叶子节点的时候把val加入结果列表即可
代码一：
class NestedIterator implements Iterator<Integer> {
private Iterator<Integer> it;
public NestedIterator(List<NestedInteger> nestedList) {
// 存放将 nestedList 打平的结果
List<Integer> result = new LinkedList<>();
for (NestedInteger node : nestedList) {
// 以每个节点为根遍历
traverse(node, result);
}
// 得到 result 列表的迭代器
this.it = result.iterator();
}
public Integer next() {
return it.next();
}
public boolean hasNext() {
return it.hasNext();
}
// 遍历以 root 为根的多叉树，将叶子节点的值加入 result 列表
private void traverse(NestedInteger root, List<Integer> result) {
if (root.isInteger()) {
// 到达叶子节点
result.add(root.getInteger());
return;
}
// 遍历框架
for (NestedInteger child : root.getList()) {
traverse(child, result);
}
}
}
这样，我们就把原问题巧妙转化成了一个 N 叉树的遍历问题，并且得到了解法。
方法二：
- 以上解法虽然可以通过，但是在面试中，也许是有瑕疵的。
- 我们的解法中，一次性算出了所有叶子节点的值，全部装到result列表，也就是内存中，
next和hasNext方法只是在对result列表做迭代。如果输入的规模非常大，构造函数中的计算就会很慢，而且很占用内存。 - 一般的迭代器求值应该是「惰性的」，也就是说，如果你要一个结果，我就算一个（或是一小部分）结果出来，而不是一次把所有结果都算出来。
- 如果想做到这一点，使用递归函数进行 DFS 遍历肯定是不行的，而且我们其实只关心「叶子节点」，所以传统的 BFS 算法也不行。实际的思路很简单：
-
调用hasNext时，如果nestedList的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型。 -
由于调用next方法之前一定会调用hasNext方法，这就可以保证每次调用next方法的时候第一个元素是整数型，直接返回并删除第一个元素即可。
代码二：
public class NestedIterator implements Iterator<Integer> {
private LinkedList<NestedInteger> list;
public NestedIterator(List<NestedInteger> nestedList) {
// 不直接用 nestedList 的引用，是因为不能确定它的底层实现
// 必须保证是 LinkedList，否则下面的 addFirst 会很低效
list = new LinkedList<>(nestedList);
}
public Integer next() {
// hasNext 方法保证了第一个元素一定是整数类型
return list.remove(0).getInteger();
}
public boolean hasNext() {
// 循环拆分列表元素，直到列表第一个元素是整数类型
while (!list.isEmpty() && !list.get(0).isInteger()) {
// 当列表开头第一个元素是列表类型时，进入循环
List<NestedInteger> first = list.remove(0).getList();
// 将第一个列表打平并按顺序添加到开头
for (int i = first.size() - 1; i >= 0; i--) {
list.addFirst(first.get(i));
}
}
return !list.isEmpty();
}
}
C++代码：
-
时间均衡的栈 - 构造时仅仅扒一层皮就
逆向 堆入栈中，在用户调用 hasNext 时才做深入扒皮搜索。 - 这种做法比较时间均衡，如果用户搞了一个很长的列表，然后就取前边几个元素就不用了，那这种实现要高效的多。
class NestedIterator {
private:
stack<NestedInteger> st;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto iter = nestedList.rbegin(); iter != nestedList.rend(); iter++) {
st.push(*iter);
}
}
int next() {
auto t = st.top();
st.pop();
return t.getInteger();
}
bool hasNext() {
while (!st.empty()) {
auto cur = st.top();
if (cur.isInteger()) return true;
st.pop();
auto curList = cur.getList();
for (auto iter = curList.rbegin(); iter != curList.rend(); iter++) {
st.push(*iter);
}
}
return false;
}
};
-
头重脚轻的栈 - 构造时
扒皮抽骨到单个数字再 push 到栈里。这样预处理很慢，但是调用时很快。有点头重脚轻。
class NestedIterator {
private:
stack<NestedInteger> st;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto iter = nestedList.rbegin(); iter != nestedList.rend(); iter++) {
parseData(*iter);
}
}
void parseData(NestedInteger item) {
if (item.isInteger()) {
st.push(item);
} else {
auto list = item.getList();
for (auto iter = list.rbegin(); iter != list.rend(); iter++) {
parseData(*iter);
}
}
}
int next() {
auto t = st.top();
st.pop();
return t.getInteger();
}
bool hasNext() {
if (st.empty()) return false;
return true;
}
};
-
头重脚轻的 vector - 不用栈，用 vector 来做也可以。只是存储的时候不再是从尾到头而是从头到尾啦。
class NestedIterator {
private:
vector<int> v;
int ind = 0;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto iter = nestedList.begin(); iter != nestedList.end(); iter++) {
parseData(*iter);
}
}
void parseData(NestedInteger item) {
if (item.isInteger()) {
v.push_back(item.getInteger());
} else {
auto list = item.getList();
for (auto iter = list.begin(); iter != list.end(); iter++) {
parseData(*iter);
}
}
}
int next() {
return v[ind++];
}
bool hasNext() {
if (ind >= v.size()) return false;
return true;
}
};
转载：https://blog.csdn.net/wolfGuiDao/article/details/106873969
查看评论