[Leetcode] Peeking Iterator 瞥一眼迭代器

smallStone 發布于2019-08-14 12:35 / 2432人閱讀

摘要：當的時候除了要返回緩存，還要將緩存更新為下一個數字，如果沒有下一個就將緩存更新為。代碼后續如何支持任意類型的迭代器使用的方式，代碼中已經將替換為的

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云服務器云服務器 -迭代器迭代器數組迭代器迭代器對象

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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