0%

[Leetcode]341. Flatten Nested List Iterator(C++)

题目描述

题目链接:341. Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  • NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
  • int next() Returns the next integer in the nested list.
  • boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

例子

例子 1

Input:nestedList = [[1,1],2,[1,1]]
Output:[1,1,2,1,1]
Explanation:By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

例子 2

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints

  • 1 <= nestedList.length <= 500
  • The values of the integers in the nested list is in the range [-10^6, 10^6]

解题思路

在初始化对象时候进行展平压入到常规的数组中,判断以及返回下一个则用一个下标即可。展平过程可以用递归实现,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NestedIterator {
public:
NestedIterator(vector<NestedInteger>& nestedList) { flattern(nestedList); }

void flattern(const vector<NestedInteger>& nestedList) {
for (auto ni : nestedList) {
if (ni.isInteger()) {
vec_.push_back(ni.getInteger());
} else {
flattern(ni.getList());
}
}
}

int next() { return vec_[idx++]; }

bool hasNext() { return idx < vec_.size(); }

private:
vector<int> vec_;
int idx = 0;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 341.FlattenNestedListIterator.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions