LeetCode题练习与总结：扁平化嵌套列表迭代器--341

一、题目描述

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

实现扁平迭代器类 NestedIterator ：

• NestedIterator(List 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
• 嵌套列表中的整数值在范围 [-10^6, 10^6] 内

二、解题思路

为了实现一个能够扁平化嵌套整数列表的迭代器，我们需要在构造函数中预处理整个嵌套列表，将其转换为扁平化的整数列表。然后，在 next() 方法中返回下一个整数，在 hasNext() 方法中检查是否还有未遍历的整数。

以下是具体的步骤：

1. 在构造函数中，使用一个队列（Queue）来存储扁平化后的整数。队列能够保证我们按照迭代顺序来处理元素。
2. 使用深度优先搜索（DFS）遍历嵌套列表，每遇到一个整数就将其加入队列中。
3. 在 next() 方法中，从队列中取出并返回下一个整数。
4. 在 hasNext() 方法中，检查队列是否为空，如果不为空则说明还有未遍历的整数。

三、具体代码

import java.util.*;
 
public class NestedIterator implements Iterator {
    private Queue queue;
 
    public NestedIterator(List nestedList) {
        queue = new LinkedList<>();
        flattenList(nestedList);
    }
 
    private void flattenList(List nestedList) {
        for (NestedInteger nestedInt : nestedList) {
            if (nestedInt.isInteger()) {
                queue.offer(nestedInt.getInteger());
            } else {
                flattenList(nestedInt.getList());
            }
        }
    }
 
    @Override
    public Integer next() {
        return queue.poll();
    }
 
    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

在这个实现中，我们首先在构造函数中初始化一个队列，并调用 flattenList 方法来处理整个嵌套列表。在 flattenList 方法中，我们递归地处理每个元素，如果是整数则直接加入队列，如果是列表则继续递归处理。next() 和 hasNext() 方法则直接操作队列，返回下一个整数和检查是否还有未遍历的整数。这样，我们就能通过迭代器来遍历整个扁平化的列表。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 在构造函数中，我们调用了 flattenList 方法来处理整个嵌套列表。这个方法会遍历嵌套列表中的每一个元素。
• 对于每个元素，如果是整数，我们将其加入队列中，这是一个 O(1) 的操作。
• 如果是列表，我们递归调用 flattenList 方法。这意味着我们需要遍历这个子列表中的每一个元素。
• 因此，我们对于每个元素，无论它是整数还是列表，都至少进行一次处理。
• 假设嵌套列表中的元素总数为 N（这包括所有整数和列表中的整数），那么 flattenList 方法将处理每个元素一次，因此时间复杂度为 O(N)。

2. 空间复杂度

• 队列用于存储扁平化后的整数，在最坏情况下，如果嵌套列表中的所有元素都是整数，则队列将存储所有 N 个整数。
• 在递归调用 flattenList 方法时，可能会产生额外的调用栈空间。最坏情况下，如果嵌套列表完全不平衡（例如，每个列表只有一个元素），则递归的深度将达到 N。
• 因此，空间复杂度主要由队列和递归调用栈组成。队列的空间复杂度为 O(N)，递归调用栈的空间复杂度在最坏情况下也是 O(N)。
• 综合来看，总的空间复杂度为 O(N)。

五、总结知识点

1. 接口实现：NestedIterator 类实现了 Iterator 接口，这意味着它必须实现接口中定义的 next() 和 hasNext() 方法。

2. 内部类与接口：NestedInteger 是一个接口，它定义了嵌套整数的操作，包括检查是否为单个整数以及获取整数值或列表。

3. 泛型：List 使用了泛型，它表示列表中存储的是 NestedInteger 类型的对象。

4. 队列的使用：Queue 被用来存储扁平化后的整数。队列是一种先进先出（FIFO）的数据结构，在这里用于保持元素的迭代顺序。

5. 链表数据结构：LinkedList 是一种实现了 Queue 接口的类，它以链表的形式存储元素，支持高效的插入和删除操作。

6. 迭代器遍历：在 flattenList 方法中，使用了增强型 for 循环来遍历 nestedList，这是一种常见的遍历集合的方式。

7. 递归算法：flattenList 方法是一个递归方法，它会递归地处理嵌套列表，直到所有整数都被扁平化到队列中。

8. 方法重写：next() 和 hasNext() 方法被重写以符合 Iterator 接口的要求，分别用于获取下一个元素和检查是否还有更多元素。

9. 条件判断：在 flattenList 方法中，使用了 if-else 语句来判断当前元素是单个整数还是嵌套列表。

10. 队列操作：offer() 方法用于将元素添加到队列的末尾，而 poll() 方法用于从队列的头部移除并返回元素。

11. 成员变量：queue 是 NestedIterator 类的成员变量，它在构造函数中被初始化，并在整个类的生命周期中保持状态。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。