labuladong题目不让我干什么，我偏要干什么
341. 扁平化嵌套列表迭代器
示例 ：
输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。
NestedInteger相当于一棵N叉树，叶子节点是int类型，其他节点是vector
- 用递归实现展平
- 如果是整数，则加到结果中
- 如果是NestedInteger，则递归展开该NestedInteger，直到不能展开为止
- 由于每次的for循环是有限的，因此不用显式地写递归出口，循环结束就是隐式的出口
- 因为需要用next得到当前元素，并弹出当前元素，然后得到下一个元素，然后弹出下一个元素…，所以用队列存储结果
- 也可以用向量存储结果。这时要记录当前位置的索引
各函数功能：
NestedIterator(vector <NestedInteger> &nestedList)函数实现全部展开int next()队列中，函数得到当前元素，并弹出当前元素 （向量中，得到当前元素后，索引向后移动）bool hasNext()： 队列中，通过NestedInteger的size()判断是否hasNext()，如果size>=1,则说明hasNext （向量中，索引值小于size()，则说明hasNext()）
方法1:递归
第一种：队列实现
/**
* // 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 {
private:
queue<int> q;
public:
void dfs(vector <NestedInteger> &nestedList) {
for (NestedInteger &i:nestedList){
if (i.isInteger()){
q.push(i.getInteger());
}
else{
dfs(i.getList());
}
}
}
NestedIterator(vector <NestedInteger> &nestedList) {
dfs(nestedList);
}
int next() {
int tmp=q.front();
q.pop();
return tmp;
}
bool hasNext() {
return q.size();
}
};
/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
*/
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger(object):
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class NestedIterator(object):
def helper(self,nestedList):
for i in nestedList:
if i.isInteger():
self.dq.append(i.getInteger())
else:
self.helper(i.getList())
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
from collections import deque
self.dq=deque()
self.helper(nestedList)
def next(self):
"""
:rtype: int
"""
return self.dq.popleft()
def hasNext(self):
"""
:rtype: bool
"""
return len(self.dq)
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
第二种：向量实现
class NestedIterator {
private:
vector<int> v;
int idx = 0; // 加一个索引记录当前位置
public:
void dfs(vector <NestedInteger> &nestedList) {
for (NestedInteger &i:nestedList) {
if (i.isInteger()) {
v.push_back(i.getInteger());
} else {
dfs(i.getList());
}
}
}
NestedIterator(vector <NestedInteger> &nestedList) {
dfs(nestedList);
}
int next() {
// 也就是 return v[idx++];
int tmp = v[idx];
idx++;
return tmp;
}
bool hasNext() {
// return v.size(); // 这里不可以再用size()判断。
// 因为idx++，可能使idx越出v,导致内存溢出。ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6030000000c0
return v.size() > idx;
}
};
方法2:迭代
处理流程分为两步：
在构造函数中应该初始化，把当前列表的各个元素（不用摊平）逆序放入栈中。
在 hasNext() 方法中，访问（不弹出）栈顶元素，判断是否为 int：
如果是 int 那么说明有下一个元素，返回 true；然后 next() 就会被调用，把栈顶的 int 弹出；
如果是 list 需要把当前列表的各个元素（不用摊平）逆序放入栈中。
如果栈为空，那么说明原始的嵌套列表已经访问结束了，返回 false。
算法整体的流程，通过举例说明。假如输入 [1, [2,3]] 。
- 在构造函数中：栈里面放的应该是 stack = [[2, 3], 1]
- 在调用 hasNext() 方法时，访问栈顶元素是 1，为 int，那么直接返回 true;
- 然后调用 next() 方法，弹出栈顶元素 1；
- 再调用 hasNext() 方法时，访问栈顶元素是 [2,3]，为 list，那么需要摊平，继续放到栈中。
当前的栈是 stack = [3, 2]- 然后调用 next() 方法，弹出栈顶元素 2；
- 然后调用 next() 方法，弹出栈顶元素 3；
注意：
while i.hasNext(): v.append(i.next())中，是while，所以当stack中是[3,2]时，会持续调用next（）函数- 再调用 hasNext() 方法时，栈为空，因此返回 false，迭代器运行结束。
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.stack = nestedList[::-1]# 逆序放入stack中
def next(self):
"""
:rtype: int
"""
return self.stack.pop().getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while self.stack:
top = self.stack[-1]
if top.isInteger():# 如果是整数，则返回True
return True
self.stack = self.stack[:-1] + top.getList()[::-1] # 如果是nestList，则把stack顶的元素逆序，再反向拼接
return False
#####其他写法
class NestedIterator(object):
def __init__(self, nestedList):
self.stack = []
for i in range(len(nestedList) - 1, -1, -1):
self.stack.append(nestedList[i])
def next(self):
cur = self.stack.pop()
return cur.getInteger()
def hasNext(self):
while self.stack:
cur = self.stack[-1]
if cur.isInteger():
return True
self.stack.pop()
for i in range(len(cur.getList()) - 1, -1, -1):
self.stack.append(cur.getList()[i])
return Falseclass NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.queue = collections.deque(nestedList)
def next(self):
"""
:rtype: int
"""
return self.queue.popleft().getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while self.queue:
if self.queue[0].isInteger():
return True
first = self.queue.popleft()
self.queue.extendleft(first.getList()[::-1])
return False
