首页 > 代码库 > leetcode-Peeking Iterator-284

leetcode-Peeking Iterator-284

2024-08-11 17:17:59   211人阅读

给定一个派生类，这个派生类只继承了基类的next()和hasNext()方法，现在要求重写派生类的next(),hasNext()和peek()方法

peek()始终取next指针的后一个元素

分析：

peek()取的是next指针的后一个元素，并且只有next()和hasNext()两个方法可用，容易发现hasNext()对peek()没有用处，所以对peek()的实现只能通过next()

这是不可避免的，但是产生一个问题就是peek()只是取next后面的值，而不应该移动这个指针的

当然虽然有这个问题，但内部的实现肯定要这么做，那怎么保证对外的接口合法呢

用一个标志位isvis，表示是否用了peek

1.isvis=0，说明没有用peek，系统正常，next指针指向正确的位置，以后的操作该怎样就怎样，比如想调用next()，那就调用next()，取得下一个值并移动指针

2.isvis=1，说明用了peek，系统不正常，next指针指向的是正确位置的下一个位置，如果想调用next()，则不能真的调用next()，因为指针其实已经被peek移动过了

那么返回值该怎么办？用缓存，peek移动指针后保存这个值，这时如果调用next()，直接返回缓存里的值

也就是说isvis=1有两层含义：

1.系统不正常，next指针无需移动

2.缓存里的值可用

 1 // Below is the interface for Iterator, which is already defined for you. 2 // **DO NOT** modify the interface for Iterator. 3 class Iterator { 4     struct Data; 5     Data* data; 6 public: 7     Iterator(const vector<int>& nums); 8     Iterator(const Iterator& iter); 9     virtual ~Iterator();10     // Returns the next element in the iteration.11     int next();12     // Returns true if the iteration has more elements.13     bool hasNext() const;14 };15 16 17 class PeekingIterator : public Iterator {18 private:19     int cache;20     int isvis;21 public:22     PeekingIterator(const vector<int>& nums) : Iterator(nums) {23         // Initialize any member here.24         // **DO NOT** save a copy of nums and manipulate it directly.25         // You should only use the Iterator interface methods.26         isvis=0;27     }28 29     // Returns the next element in the iteration without advancing the iterator.30     int peek() {31         if(!isvis){32             isvis=1;33             return cache=Iterator::next();34         }35         else return cache;36     }37 38     // hasNext() and next() should behave the same as in the Iterator interface.39     // Override them if needed.40     int next() {41         if(!isvis) return Iterator::next();42         else{43             isvis=0;44             return cache;45         }46     }47 48     bool hasNext() const {49         if(isvis) return true;50         return Iterator::hasNext();51     }52 };

 

leetcode-Peeking Iterator-284


联系
我们