题目描述

给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。设计并实现一个支持 peek() 操作的顶端迭代器 – 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。

示例:

假设迭代器被初始化为列表 [1,2,3]。

调用 next() 返回 1，得到列表中的第一个元素。 现在调用 peek() 返回 2，下一个元素。在此之后调用 next() 仍然返回 2。 最后一次调用 next() 返回 3，末尾元素。在此之后调用 hasNext() 应该返回 false。

解题思路

刚看到这个题时时一脸懵逼了，因为对于C++的面向对象开发一无所知，然后看到java和python的模板感觉很简单，但是题目确都不太懂，感觉和以前刷的算法题很不一样

暴露了自己对面向对象编程的不熟 解法一 初始化 peek_num = None，在调用peek和next时维护peek_num class PeekingIterator: def __init__(self, iterator): """ Initialize your data structure here. :type iterator: Iterator """ self.iterator = iterator self.peek_num = None def peek(self): """ Returns the next element in the iteration without advancing the iterator. :rtype: int """ if self.peek_num == None: self.peek_num = self.iterator.next() return self.peek_num return self.peek_num def next(self): """ :rtype: int """ if self.peek_num == None: return self.iterator.next() temp = self.peek_num self.peek_num = None return temp def hasNext(self): """ :rtype: bool """ if self.peek_num != None: return True return self.iterator.hasNext() 解法二 将iterator转化为数组 class PeekingIterator: def __init__(self, iterator): self.ls = [] while iterator.hasNext(): self.ls.append(iterator.next()) def peek(self): return self.ls[0] def next(self): return self.ls.pop(0) def hasNext(self): return len(self.ls) > 0 cpp version // Below is the interface for Iterator, which is already defined for you. // **DO NOT** modify the interface for Iterator. class Iterator { struct Data; Data* data; public: Iterator(const vector<int>& nums); Iterator(const Iterator& iter); virtual ~Iterator(); // Returns the next element in the iteration. int next(); // Returns true if the iteration has more elements. bool hasNext() const; }; class PeekingIterator : public Iterator { private: bool _flag; int _value; public: PeekingIterator(const vector<int>& nums) : Iterator(nums) { _flag = false; } // Returns the next element in the iteration without advancing the iterator. int peek() { if(_flag) return _value; _flag = true; _value = Iterator::next(); return _value; } // hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. int next() { if(_flag){ _flag = false; return _value; } return Iterator::next(); } bool hasNext() const { if(_flag) return true; if(Iterator::hasNext()) return true; return false; } }; java version class PeekingIterator implements Iterator<Integer> { LinkedList<Integer> list = new LinkedList(); public PeekingIterator(Iterator<Integer> iterator) { while(iterator.hasNext()){ list.add(iterator.next()); } } // Returns the next element in the iteration without advancing the iterator. public Integer peek() { if(!list.isEmpty()){ return list.peekFirst(); } return -1; } // hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. @Override public Integer next() { if(!list.isEmpty()){ return list.pollFirst(); } return -1; } @Override public boolean hasNext() { if(list.size() > 0) return true; return false; } }