Skip to content

Latest commit

 

History

History
92 lines (78 loc) · 3.38 KB

顶端迭代器.md

File metadata and controls

92 lines (78 loc) · 3.38 KB

Top Iterator

Given an interface of an iterator class that contains two methods: next() and hasNext(). Design and implement a top iterator that supports the peek() operation, which essentially retrieves the element that should have been returned by the next() method.

Example

Suppose the iterator is initialized to the list [1,2,3].

Calling next() returns 1, the first element of the list.
Now calling peek() returns 2, the next element. Subsequent calls to next() still return 2.
The last call to next() returns 3, the last element. Subsequent call to hasNext() should return false.

Solution

/**
 * // This is the Iterator's API interface.
 * // You should not implement it, or speculate about its implementation.
 * function Iterator() {
 *    @return {number}
 *    this.next = function() { // return the next number of the iterator
 *       ...
 *    }; 
 *
 *    @return {boolean}
 *    this.hasNext = function() { // return true if it still has numbers
 *       ...
 *    };
 * };
 */

/**
 * @param {Iterator} iterator
 */
var PeekingIterator = function(iterator) {
    this.iterator = iterator;
    this.cache = null;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.peek = function() {
    if(this.cache !== null) return this.cache;
    var cache = this.iterator.next();
    this.cache = cache;
    return cache;
};

/**
 * @return {number}
 */
PeekingIterator.prototype.next = function() {
    if(this.cache !== null) {
        var cache = this.cache;
        this.cache = null;
        return cache;
    }
    return this.iterator.next();
};

/**
 * @return {boolean}
 */
PeekingIterator.prototype.hasNext = function() {
    if(this.cache !== null) return true;
    return this.iterator.hasNext();
};

/** 
 * Your PeekingIterator object will be instantiated and called as such:
 * var obj = new PeekingIterator(arr)
 * var param_1 = obj.peek()
 * var param_2 = obj.next()
 * var param_3 = obj.hasNext()
 */

Approach

The idea of this problem is to implement a new iterator method peek() using the existing iterator iterator, which has two methods next() and hasNext(). By implementing the constructor function PeekingIterator and instantiating it with the new keyword, we can achieve this goal. We need to implement the next(), hasNext(), and peek() methods on the prototype chain of the PeekingIterator constructor. We store the reference of the iterator object in the iterator property when creating the instance. We also initialize and set the cache property to null. First, we implement the peek() method. When this method is called, we first retrieve the next value of the iterator object and then write it to the cache property before returning the value. Then, we implement the next() method. We first check if the cache is null. If there is a cached value, we set the cache to null and return the cached value. If there is no cached value, we simply call the next() method of the iterator. Similarly, for the implementation of the hasNext() method, we first check if there is a cached value. If there is a cached value, we consider that the iteration is not yet complete. If there is no cached value, we call the hasNext() method of the iterator to determine if there are more elements.

Daily Problem

https://github.com/WindrunnerMax/EveryDay

Problem Source

https://leetcode-cn.com/problems/peeking-iterator/