窥视迭代器
难度:
标签:
题目描述
请你在设计一个迭代器，在集成现有迭代器拥有的 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 <= 10001 <= nums[i] <= 1000- 对
next和peek的调用均有效 next、hasNext和peek最多调用1000次
进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？
代码结果
运行时间: 27 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用一个现有的迭代器来初始化 PeekingIterator。
* 2. 添加一个成员变量来存储下一个元素并保持其状态。
* 3. peek() 方法返回下一个元素而不移动指针。
* 4. next() 方法返回下一个元素并移动指针到下一个位置。
* 5. hasNext() 方法检查是否还有下一个元素。
*/
import java.util.Iterator;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private Integer nextElement;
public PeekingIterator(Iterator<Integer> iterator) {
// Initialize the iterator and advance to the first element
this.iterator = iterator;
if (iterator.hasNext()) {
nextElement = iterator.next();
}
}
// Returns the next element in the iteration without advancing the iterator
public Integer peek() {
return nextElement;
}
@Override
public Integer next() {
Integer result = nextElement;
nextElement = iterator.hasNext() ? iterator.next() : null;
return result;
}
@Override
public boolean hasNext() {
return nextElement != null;
}
public static void main(String[] args) {
Iterator<Integer> iterator = Stream.of(1, 2, 3).iterator();
PeekingIterator peekingIterator = new PeekingIterator(iterator);
System.out.println(peekingIterator.next()); // 返回 1
System.out.println(peekingIterator.peek()); // 返回 2
System.out.println(peekingIterator.next()); // 返回 2
System.out.println(peekingIterator.next()); // 返回 3
System.out.println(peekingIterator.hasNext()); // 返回 false
}
}解释
方法:
此题解通过封装原有的迭代器来实现一个支持`peek`操作的新迭代器。核心思路是在PeekingIterator类中，使用一个额外的变量`_next`来存储下一个元素，从而在调用`peek`时不移动原迭代器的指针。当调用`next`方法时，首先返回`_next`中存储的元素，然后更新`_next`为原迭代器的下一个元素。如果原迭代器没有下一个元素，`_next`设为None。`hasNext`方法则检查`_next`是否为None来决定是否还有后续元素。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
类构造函数`PeekingIterator`中，`self._next = self._iter.next()`在迭代器为空时如何处理？是否会抛出异常？
▷🦆
在`next`方法中，如果当前没有下一个元素（即`_next`为None），调用此方法会返回什么？是否应该有异常处理机制？
▷🦆
在设计`peek`方法时，如何保证在连续多次调用`peek`时不会影响迭代器的状态？
▷相关问题
二叉搜索树迭代器
实现一个二叉搜索树迭代器类
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, 105]内 0 <= Node.val <= 106- 最多调用
105次hasNext和next操作
进阶：
- 你可以设计一个满足下述条件的解决方案吗？
next()和hasNext()操作均摊时间复杂度为O(1)，并使用O(h)内存。其中h是树的高度。