Processing math: 100%

Leetcode 341 - Flatten Nested List Iterator

題目

Problem#

給你一個介面 NestedInteger 裡頭可以是單個整數、或是另一堆 NextedInteger ,要你實作 NestedIterator 提供方法可以遍歷 NestedInteger

NestedIterator 共有三個 member function:

  1. NestedIterator(List<NestedInteger> nestedList) 初始化
  2. int next() 回傳下個數字
  3. boolean hasNext() 是否到盡頭了

會以以下方式評測你寫的 NestedIterator

1
2
3
4
5
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

測資限制#

  • 1n500
  • 106val106

想法#

dfs 遍歷一次存到陣列,接著遍歷

AC Code#

Copy
class NestedIterator {
public:
vector<int> v;
int cur = 0;
void flatten(vector<NestedInteger> &list)
{
for(auto i : list)
{
if(i.isInteger())
{
v.push_back(i.getInteger());
}
else
{
flatten(i.getList());
}
}
}
NestedIterator(vector<NestedInteger> &nestedList)
{
flatten(nestedList);
}
int next()
{
return v[cur++];
}
bool hasNext()
{
return cur < v.size();
}
};
view raw leetcode/341.cpp delivered with ❤ by emgithub
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)