锯齿迭代器

难度:

标签:

题目描述

代码结果

运行时间: 33 ms, 内存: 16.3 MB

/*
 * 思路：
 * 使用 Java Stream API 来实现锯齿迭代器。
 * 这里主要的思路是先合并两个列表，再按照交替顺序排序。
 * 将两个列表中的元素分成一个列表中的奇数索引和偶数索引，然后交替合并它们。
 */
import java.util.*;
import java.util.stream.*;
 
public class ZigzagIteratorStream {
    private List<Integer> mergedList;
    private Iterator<Integer> iterator;
 
    public ZigzagIteratorStream(List<Integer> v1, List<Integer> v2) {
        List<Integer> combinedList = Stream.concat(v1.stream(), v2.stream()).collect(Collectors.toList());
        List<Integer> zigzagList = new ArrayList<>();
        int size1 = v1.size(), size2 = v2.size();
        int maxSize = Math.max(size1, size2);
 
        for (int i = 0; i < maxSize; i++) {
            if (i < size1) zigzagList.add(v1.get(i));
            if (i < size2) zigzagList.add(v2.get(i));
        }
        this.mergedList = zigzagList;
        this.iterator = mergedList.iterator();
    }
 
    public int next() {
        return iterator.next();
    }
 
    public boolean hasNext() {
        return iterator.hasNext();
    }
}

解释

方法:

这个题解使用队列（deque）来实现锯齿迭代器。初始化时，将非空的输入数组及其初始下标 0 作为元组依次加入队列。每次调用 next() 方法时，从队首取出当前要迭代的数组和下标，返回当前元素，并将下标加 1。如果更新后的下标没有超出数组范围，则将新的元组加入队尾。hasNext() 方法则遍历队列中的所有元组，判断是否存在还未迭代完的数组。

时间复杂度:

O(m+n+k)

空间复杂度:

O(1)

代码细节讲解

🦆

为何在设计锯齿迭代器时选择使用`deque`而不是其他类型的数据结构如列表或链表？

▷

在锯齿迭代器的设计中，使用`deque`（双端队列）是因为它支持从两端高效地添加和删除元素。当使用列表时，从列表的开头删除元素的时间复杂度为O(n)，因为需要移动其他所有元素。而在链表中，虽然添加和删除操作的时间复杂度为O(1)，但链表在随机访问时不如`deque`高效。`deque`提供了平衡的方案，即支持快速的随机访问以及从两端高效的插入和删除，这适合锯齿迭代器中经常进行的操作。

🦆

初始化`ZigzagIterator`时，如果输入的数组中存在长度远不同，这种实现方式是否会导致某些数组迭代结束得更快？如何处理这种情况以保持锯齿形迭代？

▷

是的，如果输入的数组长度不同，按照当前的实现，较短的数组可能会比较长的数组先迭代完成。为了处理这种情况并保持锯齿形的迭代，可以在迭代过程中动态调整各个数组元素的取出顺序。具体地，可以在元素取出后立即将其（如果仍有剩余元素）放回队列，这样可以确保在所有数组中都尽可能均匀地进行迭代。

🦆

在`next`方法中，如果当前数组已迭代完成，是否考虑过将队列的这个元组直接丢弃，而不是检查后再次加入队列？这样做的优缺点是什么？

▷

在`next`方法中，当当前数组已迭代完成，实际上我们是直接丢弃队列中的这个元组，而不是再次加入队列。这种设计的优点是保持了队列的简洁性，只有未完全迭代的数组才保留在队列中，这有助于减少无效的检查和操作。缺点可能是需要在每次调用`next`时进行条件检查，但这是管理动态数据集的必要操作，以确保不会访问已经迭代完毕的数组。

🦆

请问`hasNext`方法中遍历队列来检查是否还有元素未迭代的操作，是否会影响整体性能？能否优化此方法以减少不必要的遍历？

▷

在`hasNext`方法中遍历队列确实可能影响性能，特别是当队列较大时。为了优化这个方法，可以考虑使用一个标志来跟踪是否还有更多的元素可以迭代。每次调用`next`时，如果发现数组已迭代完毕，则更新这个标志。这样，`hasNext`就可以直接返回这个标志的状态，从而避免每次都遍历队列。这个方法可以显著减少在元素接近尾部时的计算量。

相关问题

二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 10⁵] 内
0 <= Node.val <= 10⁶
最多调用 10⁵ 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

展开二维向量

窥视迭代器

请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。

实现 PeekingIterator 类：

PeekingIterator(Iterator<int> nums) 使用指定整数迭代器 nums 初始化迭代器。
int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
int peek() 返回数组中的下一个元素，但不移动指针。

注意：每种语言可能有不同的构造函数和迭代器 Iterator，但均支持 int next() 和 boolean hasNext() 函数。

示例 1：

输入：
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
输出：
[null, 1, 2, 2, 3, false]

解释：
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // 返回 1 ，指针移动到下一个元素 [1,2,3]
peekingIterator.peek();    // 返回 2 ，指针未发生移动 [1,2,3]
peekingIterator.next();    // 返回 2 ，指针移动到下一个元素 [1,2,3]
peekingIterator.next();    // 返回 3 ，指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
对 next 和 peek 的调用均有效
next、hasNext 和 peek 最多调用 1000 次

进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

扁平化嵌套列表迭代器

给你一个嵌套的整数列表 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
嵌套列表中的整数值在范围 [-10⁶, 10⁶] 内

摆动排序给表达式添加运算符