算法学习：每日一题 No.284

284. 窥探迭代器

这是一道算法设计题，第一次接触这类题，需要告诉自己：题干注释掉的代码，注释清楚的解释了代码的功能，多半是已经实现的功能，需要你去利用。

初看题干的时候，一拍脑袋，这用链表的实现就可以了不是么？结果打开代码编辑，和想象中的不同，以下是题头的部分：

/*
 * 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);

    // Returns the next element in the iteration.
    int next();

    // Returns true if the iteration has more elements.
    bool hasNext() const;
};

Below is the interface for Iterator, which is already defined for you. 我看到这句话的理解是接口已经定义了，但是没有实现。

实际上这个接口含有它的实现，接口中可以包含自己的实现和数据结构，但是抽象类不可以这样（Java中的概念）。

也就是说我们需要利用 Iterator 来完成我们最终的实现，而且我们实现的迭代器只能向后进行遍历。

来看看我们的任务：

bool hasNext() 是否有下一个元素

Iterator 中也实现了这个函数，我们可以将这个值缓存下来，也便于其它函数调用。

int next() 返回下一个元素

Iterator 中已经实现了 next() ，它会返回下一个元素的值，我们需要这个值，但是也不要忘记判断是否拥有下一个元素。如果没有下一个元素，我们就返回当前的元素。

这里判断的结果可以用来更新 hasNext() 的缓存。

对于 next() 的效果应该是：想象一个指针在进行移动，初始情况指针指向 -1 的位置，每调用一次都将指针向后移动并输出该元素内容。

我们可以将下一个元素的值缓存下来，调用 next() 的时候就返回这个值。

int peek() 返回数组中的下一个元素，但不移动指针

我们直接返回 next() 的缓存。

PeekingIterator(int[] nums) 构造函数

Iterator(const vector<int>& nums);
PeekingIterator(const vector<int>& nums) : Iterator(nums);

Iterator 中实现了复制构造函数，并且 PeekingIterator 的初始化列表中已经使用了该复制构造函数。

在这个构造函数中需要初始化两个缓存量：next() 和 hasNext() .

最后整体的实现：

class PeekingIterator : public Iterator {
public:
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
        this->hasNextFlag = Iterator::hasNext();
	    if (this->hasNextFlag)
        {
            this->nextNumber = Iterator::next();
        }
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return nextNumber;
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
        int res = this->nextNumber;
        this->hasNextFlag = Iterator::hasNext();
        if (this->hasNextFlag)
        {
            this->nextNumber = Iterator::next();
        }
	    return res;
	}
	
	bool hasNext() const {
	    return hasNextFlag;
	}
private:
    int nextNumber;
    bool hasNextFlag;
};

总结

C++ 面向对象的部分还需要好好学习。