lintcode528. 摊平嵌套的列表

快来打我* 2023-07-24 13:06 14阅读 0赞

给你一个嵌套的列表，实现一个迭代器将其摊平。  
一个列表的每个元素可能是整数或者一个列表。

样例
    样例1
    
    输入: list = [[1,1],2,[1,1]]
    输出: [1,1,2,1,1]
    样例2
    
    输入: list = [1,[4,[6]]]
    输出: [1,4,6]
    注意事项
    你不需要实现删除方法

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * class NestedInteger {
     *   public:
     *     // Return true if this NestedInteger holds a single integer,
     *     // rather than a nested list.
     *     bool isInteger() const;
     *
     *     // Return the single integer that this NestedInteger holds,
     *     // if it holds a single integer
     *     // The result is undefined if this NestedInteger holds a nested list
     *     int getInteger() const;
     *
     *     // Return the nested list that this NestedInteger holds,
     *     // if it holds a nested list
     *     // The result is undefined if this NestedInteger holds a single integer
     *     const vector<NestedInteger> &getList() const;
     * };
     */
    class NestedIterator {
        
    public:
        vector<int> v;
        int cnt;
        int size;
        NestedIterator(vector<NestedInteger> &nestedList) {
        
            // Initialize your data structure here.
            v.clear();
            cnt=0;
            dfs(nestedList);
            size=v.size();
        }
    
        // @return {int} the next element in the iteration
        int next() {
        
            // Write your code here
            return v[cnt++];
        }
    
        // @return {boolean} true if the iteration has more element or false
        bool hasNext() {
        
            // Write your code here
            if(size)
            {
        
                size--;
                return true;
            }
            else return false;
        }
        void dfs(vector<NestedInteger> nestedList)
        {
        
            for (int i = 0; i < nestedList.size(); i++) {
        
                if(nestedList[i].isInteger()) v.push_back(nestedList[i].getInteger());
                else dfs(nestedList[i].getList());
            }
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) v.push_back(i.next());
     */