LeetCode_数据结构设计_中等_341. 扁平化嵌套列表迭代器

系统管理员 2023-10-06 22:39 4阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。**请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。**

实现扁平迭代器类 NestedIterator ：

NestedIterator(List<NestedInteger> nestedList) 		用嵌套列表 nestedList 初始化迭代器。
    int next() 											返回嵌套列表的下一个整数。
    boolean hasNext() 									如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。
    你的代码将会用下述伪代码检测：
    initialize iterator with nestedList
    res = []
    while iterator.hasNext()
        append iterator.next() to the end of res
    return res
    如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

**示例 1：**  
输入：nestedList = \[\[1,1\],2,\[1,1\]\]  
输出：\[1,1,2,1,1\]  
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: \[1,1,2,1,1\]。

**示例 2：**  
输入：nestedList = \[1,\[4,\[6\]\]\]  
输出：\[1,4,6\]  
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: \[1,4,6\]。

**提示：**  
1 <= nestedList.length <= 500  
嵌套列表中的整数值在范围 \[-106, 106\] 内

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/flatten-nested-list-iterator

## 2.思路 ##

（1）数据结构设计  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————数据结构设计
    /**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public interface NestedInteger {
     *
     *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
     *     public boolean isInteger();
     *
     *     // @return the single integer that this NestedInteger holds, if it holds a single integer
     *     // Return null if this NestedInteger holds a nested list
     *     public Integer getInteger();
     *
     *     // @return the nested list that this NestedInteger holds, if it holds a nested list
     *     // Return empty list if this NestedInteger holds a single integer
     *     public List<NestedInteger> getList();
     * }
     */
    public class NestedIterator implements Iterator<Integer> {
        
    
        private List<Integer> vals;
        private Iterator<Integer> cur;
    
        public NestedIterator(List<NestedInteger> nestedList) {
        
            vals = new ArrayList<Integer>();
            dfs(nestedList);
            cur = vals.iterator();
        }
    
        @Override
        public Integer next() {
        
            return cur.next();
        }
    
        @Override
        public boolean hasNext() {
        
            return cur.hasNext();
        }
    
        public void dfs(List<NestedInteger> nestedList) {
        
            for (NestedInteger nest : nestedList) {
        
                if (nest.isInteger()) {
        
                    //当前元素是一个整数，则将其加入到 vals 中
                    vals.add(nest.getInteger());
                } else {
        
                    //当前元素是一个列表，则遍历该列表中的所有整数
                    dfs(nest.getList());
                }
            }
        }
    }
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i = new NestedIterator(nestedList);
     * while (i.hasNext()) v[f()] = i.next();
     */

[Link 1]: https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/bian-ping-hua-qian-tao-lie-biao-die-dai-ipjzq/