Topic describes

This is 284 on LeetCode. Top iterator, medium difficulty.

Tag: “Data structure”, “simulation”

Design an iterator that supports peek in addition to hasNext and next operations.

Implement the PeekingIterator class:

  • PeekingIterator(int[] nums)Uses an array of specified integersnumsInitialize the iterator.
  • int next()Returns the next element in the array and moves the pointer to the next element.
  • bool hasNext()Returns if the next element exists in the arraytrue; Otherwise, returnfalse.
  • int peek()Returns the next element in the array, butDon’tMove the pointer.

Example:

Input: [" PeekingIterator ", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] output: [null, 1, 2, 2, 3, false] PeekingIterator = new PeekingIterator([1, 2, 3]); / / [1, 2, 3] peekingIterator. Next (); // Returns 1, moves the pointer to the next element [1,2,3] peekingiterator.peek (); [1,2] peekingiterator.next (); // return 2 and move to the next element [1,2,3] peekingiterator.next (); // return 3 and move to the next element [1,2,3] peekingiterator.hasnext (); / / returns FalseCopy the code

Tip:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • Calls to next and peek are valid
  • Next, hasNext, and Peek are called up to 1000 times

Advanced: How would you expand your design? Make it universal, so it fits all types, not just integers?

Iterator basic knowledge + simulation

Regular iterator “access” supports only two operations:

  • hasNext()Action: Returns if the next element existsTrueOtherwise returnFalse. Implementation, is to determine whether the cursor reached the end position;
  • next()Action: Returns the next element (if no next element existsnull). Implementatively, this is to return the element to which the cursor points and move it back.

In this case, we also need to support the peek() operation, which returns the element to which the cursor points if the cursor is moved.

Implementatively, we can make the operation a step earlier by calling next() first and storing the element with the variable nextnextNext, externally calling peek() or next() to determine whether to update NextNextNext; And since we have pre-stored the element at the next access location, we can tell if the end of the iterator has been reached by determining whether NextnextNext is null (hasNext() implementation).

Code:

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iter;
    Integer next;
    public PeekingIterator(Iterator<Integer> iterator) {
          iter = iterator;
          if (iter.hasNext()) next = iter.next();
    }

    public Integer peek(a) {
          return next;
    }

    @Override
    public Integer next(a) {
          Integer ans = next;
          next = iter.hasNext() ? iter.next() : null;
        return ans;
    }

    @Override
    public boolean hasNext(a) {
          returnnext ! =null; }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The advanced

  • How would you expand your design? Make it universal, so it fits all types, not just integers?

Thanks to Java’s “generics” design, we can easily support any type: we just need to change Integer to a generic identifier, such as E.

Code:

class PeekingIterator implements Iterator<E> {
    Iterator<E> iter;
    E next;
    public PeekingIterator(Iterator<E> iterator) {
          iter = iterator;
          if (iter.hasNext()) next = iter.next();
    }

    public E peek(a) {
          return next;
    }

    @Override
    public E next(a) {
          E ans = next;
          next = iter.hasNext() ? iter.next() : null;
        return ans;
    }

    @Override
    public boolean hasNext(a) {
          returnnext ! =null; }}Copy the code

Java generics are implemented by “erasure”. At compile time, the compiler automatically adds casting code, and after the casting logic is added, the generic information is no longer needed. Therefore, after compile, the generic information is erased directly, not carried to runtime.

Other languages that do not support generics can be implemented with a similar approach: save a data type and, when implementing an interface that uses generics, perform a manual override before receiving it in/back out.

The last

This is No.284 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have locks, so we will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.