mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
120 lines
4.1 KiB
Markdown
120 lines
4.1 KiB
Markdown
# [341. Flatten Nested List Iterator](https://leetcode.com/problems/flatten-nested-list-iterator/)
|
||
|
||
# 思路
|
||
|
||
这道题让我们将嵌套链表压平。
|
||
|
||
## 思路一
|
||
|
||
思路很简单，因为链表的元素可能还是链表，所以是个递归（或者用栈转成非递归），我们先创建一个记录压平后所有元素的全局数组nums，
|
||
然后定义helper递归函数，传入一个`NestedInteger`记为`nest`:
|
||
* 若`nest.isInteger() == True`，即`nest`是个数，将`nest.getInteger()`push进nums即可；
|
||
* 否则，即`nest`是个列表，那么对`nest.getList()`的每个元素递归调用helper。
|
||
|
||
NestedIterator构造函数里面，我们对nestedList每个元素调用一下`helper`以建立nums，建立好nums后，`hasNext()`和`next()`就好写了。
|
||
|
||
## 思路二
|
||
|
||
思路一是提前将链表压平，用一个数组存放压平后的元素。这样对空间复杂度要求比较高，如果能在每次调用`next()`的过程中进行压平，就不需要用一个数组来存放压平后的元素了。
|
||
|
||
总体思路是用一个栈，栈里的元素是一个pair: `pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator>`，表示尚未访问的某个`NestedInteger`数组的始末迭代器；然后还需要用两个迭代器变量`start`和`end`记录当前正在访问的位置即终点位置，在访问每个元素的过程中：
|
||
* 如果`start == end`，说明正在访问的位置到达了终点，应该将其更新为栈顶的元素，然后递归访问；
|
||
* 否则，若`start -> isInteger() == True`，即是个数，则返回这个数即可，然后迭代器`start`后移一个位置；
|
||
* 否则，即是个列表，那么需要把当前的`start`和`end`入栈，然后将`start`和`end`更新为这个列表的`begin()`和`end()`，再递归进行访问；
|
||
|
||
需要注意的是，为了处理`[[]]`这种情况，我们采用提前用一个变量`next_val`记录下一个应该访问的值，还要用一个bool变量`valid_next`标记`next_val`所记录的值是否是有效的。那么`hasNext()`只需返回`valid_next`即可。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class NestedIterator {
|
||
private:
|
||
int cur_index, size;
|
||
vector<int>nums;
|
||
void helper(NestedInteger &nest){
|
||
if(nest.isInteger())
|
||
nums.push_back(nest.getInteger());
|
||
else{
|
||
auto &list = nest.getList();
|
||
for(auto &a: list)
|
||
helper(a);
|
||
}
|
||
}
|
||
|
||
public:
|
||
NestedIterator(vector<NestedInteger> &nestedList) {
|
||
cur_index = 0;
|
||
for(auto & a: nestedList)
|
||
helper(a);
|
||
size = nums.size();
|
||
}
|
||
|
||
int next() {
|
||
return nums[cur_index++];
|
||
}
|
||
|
||
bool hasNext() {
|
||
return cur_index < size;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class NestedIterator {
|
||
private:
|
||
stack< pair<vector<NestedInteger>::iterator, vector<NestedInteger>::iterator> >stk;
|
||
vector<NestedInteger>::iterator start;
|
||
vector<NestedInteger>::iterator end;
|
||
int next_val; // 存放了调用next()应该返回的值
|
||
bool valid_next; // next_val中存放的值是否是有效的
|
||
|
||
public:
|
||
NestedIterator(vector<NestedInteger> &nestedList) {
|
||
start = nestedList.begin();
|
||
end = nestedList.end();
|
||
valid_next = true;
|
||
next_val = DFS();
|
||
}
|
||
|
||
int DFS() {
|
||
if(start == end){
|
||
if(stk.empty()) {
|
||
valid_next = false;
|
||
return -1; // 无效的next_val
|
||
}
|
||
start = stk.top().first; end = stk.top().second;
|
||
stk.pop();
|
||
return DFS();
|
||
}
|
||
|
||
if(start -> isInteger()){
|
||
int res = start -> getInteger();
|
||
start++;
|
||
return res;
|
||
}
|
||
else{
|
||
auto new_start = (start -> getList()).begin();
|
||
auto new_end = (start -> getList()).end();
|
||
|
||
start++;
|
||
if(start != end) stk.push({start, end});
|
||
start = new_start;
|
||
end = new_end;
|
||
return DFS();
|
||
}
|
||
}
|
||
|
||
int next(){
|
||
int tmp = next_val;
|
||
next_val = DFS();
|
||
return tmp;
|
||
}
|
||
|
||
bool hasNext() {
|
||
return valid_next;
|
||
}
|
||
};
|
||
|
||
```
|