题目描述

题目链接：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]

解题思路

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

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