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

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

測資限制#

• $1 \le n \le 500$
• $-10^6 \le val \le 10^6$

想法#

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

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$