leetcode#341. 扁平化嵌套列表迭代器

Love The Way You Lie 2022-11-12 08:25 163阅读 0赞

## 题目 ##

https://leetcode-cn.com/problems/flatten-nested-list-iterator/

## 思路 ##

`nestedList`中的每一项可能是整数、也可能是另一个`nestedList`列表（里面继续嵌套）  
注意到代码区的注释部分，提供了`NestedInteger` 的几个接口，可以用于判断是否整数、获取整数、获取列表

/**
     * // 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;
     * };
     */

可以使用一个vector来存放结果。  
在构造阶段`NestedIterator i(nestedList)`就遍历传入的`NestedInteger`类型的`nestedList`列表，如果是整数，直接放入vector，如果是`nestedList`列表，递归进入`nestedList`列表进行遍历。

最后通过index来遍历输出vector即可。

## 代码 ##

class NestedIterator {
        
    private:
        vector<int> v; // 用于存放最后结果
        int index=0;   // 数组下标
    
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
        
        	// 遍历nestedList
            for(auto it=nestedList.begin();it!=nestedList.end();it++){
        
                parseData(*it);
            }
        }
    
    	// 读取当前元素，判断是整数还是列表
        void parseData(NestedInteger item){
        
            // 是整数
            if(item.isInteger()){
        
                v.push_back(item.getInteger());  // 放入vector
            }else{
        
            // 是列表
                auto list=item.getList();
                // 遍历这个列表
                for(auto it=list.begin();it!=list.end();it++){
        
                	// 递归进入这个列表
                    parseData(*it);
                }
            }
        }
        //输出当前index指向的值，然后index+1
        int next() {
        
            return v[index++];
        }
        //返回vector中是否还有下一位
        bool hasNext() {
        
            if(index < v.size()) return true;
            else return false;
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);  构造函数
     * while (i.hasNext()) cout << i.next(); 判断是否还有下一位，有则输出
     */

## 提交结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

## 总结 ##

这种方法是在构造阶段就递归进入每一个列表，属于DFS

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20221022/0f18431b4a7c4806a99477cd7b6398ff.png