284. 窥探迭代器

转载自Leet Code

题目描述

设计一个迭代器，除了支持hasNext和next操作之外，还支持peek操作。

实现PeekingIterator类:

• PeekingIterator(int[] nums) 使用指定整数数组 nums 初始化迭代器。

• int next() 返回数组中的下一个元素，并将指针移动到下个元素处。

• bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。

• int peek() 返回数组中的下一个元素，但 不 移动指针。

每位数字按照逆序存储，每个节点只能存储一位数字。

示例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 次

进阶：

如何拓展你的设计从而适应所有的类型，而不只是整数型？

---

方法: 迭代器

最直接的思路: 用一个 列表 存储迭代器中的每个元素, 然后遍历列表模拟迭代器;

更好的方法: 利用 迭代器的性质 实现顶端迭代器的操作。

顶端迭代器需要实现以下三种操作：

• next: 返回迭代器的下一个元素、将指针后移一位；
• hasNext: 判断迭代器中是否还有剩余元素;
• peek：返回迭代器的下一个元素、不移动指针。

每种编程语言自带的迭代器性质不同，不一定支持上述的所有操作。

以 Java 为例: Iterator 接口支持next和hasNext操作，但是不支持peek 操作。

为了支持peek操作，可以用一个nextElement存储迭代器的下一个元素。

各项操作的具体实现如下:

• next: 用表示返回值的ret存储nextElement，然后将nextElement后移一位、返回ret;
• hasNext: 由于nextElement存储迭代器的下一个元素，因此当nextElement不为空时返回true;
• peek：由于该操作不移动指针，直接返回nextElement。

时空复杂度: $T(N) = O(1), S(N) = O(1); $

class MySolution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode p1 = l1; ListNode p2 = l2;
    	
    	int add = 0;
    	ListNode ansP = null; ListNode tailP = null;
    	while (p1!=null&&p2!=null)
    	{
    		int sum = p1.val+p2.val+add;
    		int val = sum%10; add = sum/10;
    		ListNode newP = new ListNode(val);
    		
    		if (ansP==null) {
                ansP = newP;tailP = ansP;
            }
    		else {
    			tailP.next = newP; tailP = newP;
    		}
            p1=p1.next; p2=p2.next;
    	}
		ListNode node =  p1!=null?p1:p2;
    	while (node!=null)
    	{
    		int val;
    		if (add==0)
    			val = node.val;
    		else{
        		int sum = node.val+add;
        		val = sum%10; add = sum/10;
    		}

    		ListNode newP = new ListNode(val);
			tailP.next = newP; tailP = newP;
            node = node.next;
    	}
    	if (add!=0) 
        {
    		int val = add;
    		ListNode newP = new ListNode(val);
			tailP.next = newP; tailP = newP;
    	}
    	return ansP;
    }
}

---

进阶问题

对于动态语言 (JavaScript, Python等)，不需要拓展上述设计。

对于静态语言 (Java, C/C++等)，可以使用泛型来扩展设计:

在PeekingIterator中定义泛型，使用时可以用任意类型。

class PeekingIterator<E> implements Iterator<E> {
    private Iterator<E> iterator;
    private E nextElement;

    public PeekingIterator(Iterator<E> iterator) {
        this.iterator = iterator;
        nextElement = iterator.next();
    }
    
    public E peek() {
        return nextElement;
    }
    
    @Override
    public E next() {
        E ret = nextElement;
        nextElement = iterator.hasNext() ? iterator.next() : null;
        return ret;
    }
    
    @Override
    public boolean hasNext() {
        return nextElement != null;
    }
}