[Leetcode] Peeking Iterator 瞥一眼迭代器

smallStone 发布于2019-08-14 12:35 / 2428人阅读

摘要：当的时候除了要返回缓存，还要将缓存更新为下一个数字，如果没有下一个就将缓存更新为。代码后续如何支持任意类型的迭代器使用的方式，代码中已经将替换为的

Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().
Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].
Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.
Hint:
Think of "looking ahead". You want to cache the next element. Is one variable sufficient? Why or why not? Test your design with call order of peek() before next() vs next() before peek().Show More Hint  Follow up: How would you extend your design to be generic and work with all types, not just integer?
Credits: Special thanks to @porker2008 for adding this problem and creating all test cases.

缓存法 复杂度

时间 O(1) 空间 O(1)

思路

为了能peek后下次next还得到同样的数字，我们要用一个缓存保存下一个数字。这样当peek时候，返回缓存就行了，迭代器位置也不会变。当next的时候除了要返回缓存，还要将缓存更新为下一个数字，如果没有下一个就将缓存更新为null。

代码

class PeekingIterator implements Iterator {

    T cache;
    Iterator it;

    public PeekingIterator(Iterator iterator) {
        // initialize any member here.
        this.cache = iterator.next();
        this.it = iterator;
    }

    // Returns the next element in the iteration without advancing the iterator.
    public T peek() {
        return cache;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public T next() {
        T res = cache;
        cache = it.hasNext() ? it.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return it.hasNext() || cache != null;
    }
}

后续 Follow Up

Q：如何支持任意类型的迭代器？
A：使用Generic的方式，代码中已经将Integer替换为Generic的T

GPU云服务器云服务器 -迭代器迭代器数组迭代器迭代器对象

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64577.html

【LC总结】Iterator题目<Zigzag 1&2><BST>&

摘要：方法直接查找数组的位的迭代器，调用方法得到的整数即为要返回的元素。再写迭代器的方法返回指针元素的并让指针通过递归方法指向下一个元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

WelliJhon 2019-08-14 15:49 评论0 收藏0
leetcode 341 Flatten Nested List Iterator 以及其他Iter

摘要：返回的是表示是否走到了结尾。起到的就是缓存作用，因为调用之后马上就走到下一个了。如果调用，返回用得到和最初的输入相同的做相同的步骤存入不断拆开得到结果。思想就是来自括号，后面也会跟进的专题 Iterator其实就是一个单链表，无法回头看。java里很多数据结构都有这个接口，使用时需要initalize,得到一个iterator. 调用next()返回的是一个object, 指向的是下一...

chaosx110 2019-08-14 18:00 评论0 收藏0
[Leetcode] Zigzag Iterator Z形迭代器

摘要：用变量和取模来判断我们该取列表中的第几个迭代器。同样，由于每用完一个迭代器后都要移出一个，变量也要相应的更新为该迭代器下标的上一个下标。如果迭代器列表为空，说明没有下一个了。 Zigzag Iterator Given two 1d vectors, implement an iterator to return their elements alternately. For exa...

SolomonXie 2019-08-14 12:35 评论0 收藏0
[Leetcode] Flatten 2D Vector 整平二维向量

摘要：另一个则是的迭代器，它负责记录当前到哪一个的迭代器了。每次时，我们先调用一下，确保当前的迭代器有下一个值。代码当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器 Flatten 2D Vector Implement an iterator to flatten a 2d vector. For example, Given 2d vector = [ ...

MageekChiu 2019-08-14 12:36 评论0 收藏0
[Leetcode] Binary Search Tree Iterator 二叉搜素树迭代器

摘要：代码先找到第一个节点，并把路径入栈栈为空时不再有下一个栈顶是待返回元素如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

shixinzhang 2019-08-14 12:36 评论0 收藏0