设计-迭代器模式

摘要: 迭代器模式，题目清单，典型题解

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们简要介绍一下常用的设计模式：迭代器模式。列出了一些与迭代器相关的题目清单。最后解决两个比较典型的问题。

$1 迭代器模式

对于以下循环：

for(int i = 0; i < n; ++i)
    cout << a[i];

将循环变量 i 的作用抽象化，通用化后形成的模式称为迭代器模式。

迭代器模式用于在数据集合中按照顺序遍历集合(Collection) 或聚合(Aggregate)中的元素，同时无须关注集合或聚合内部的实现细节。

一个可能的迭代器的接口如下：

template <class T>
class Iterator
{
    virtual bool hasNext() =0;
    virtual T next() =0;
};

核心的方法有两个，next() 获取下一个元素，以及 hasNext() 判断是否存在下一个元素。

为什么要引入 Iterator 这种复杂的设计模式呢，如果是数组，直接用 for 循环就可以了。原因是引入迭代器之后可以将遍历与实现分离开，例如以下遍历的代码：

while(it.hasNext())
{
    T t = it.next();
    ...
}

这里的 while 循环并不依赖 T 的实现。

C++ 的 STL 中大量使用了迭代器模式。Python 为迭代器模式提供了内置支持。

$2 题目清单

• 281. 锯齿迭代器
• 173. 二叉搜索树迭代器
• 284. 顶端迭代器
• 1286. 字母组合迭代器
• 251. 展开二维向量
• 604. 迭代压缩字符串
• 341. 扁平化嵌套列表迭代器
• 1586. 二叉搜索树迭代器 II

$2 典型题解

284. 顶端迭代器

请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。

实现 PeekingIterator 类：

• PeekingIterator(Iterator nums) 使用指定整数迭代器 nums 初始化迭代器。
• int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
• bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false 。
• int peek() 返回数组中的下一个元素，但 不 移动指针。

注意：每种语言可能有不同的构造函数和迭代器 Iterator，但均支持 int next() 和 boolean hasNext() 函数。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 1000
对 next 和 peek 的调用均有效

示例 1：
输入：
[“PeekingIterator”, “next”, “peek”, “next”, “next”, “hasNext”]
[[[1, 2, 3]], [], [], [], [], []]
输出：
[null, 1, 2, 2, 3, false]
解释：
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next(); // 返回 1 ，指针移动到下一个元素 [1,2,3]
peekingIterator.peek(); // 返回 2 ，指针未发生移动 [1,2,3]
peekingIterator.next(); // 返回 2 ，指针移动到下一个元素 [1,2,3]
peekingIterator.next(); // 返回 3 ，指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False

代码(C++)

利用父类的拷贝构造函数。

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.
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        auto tmp = *this;
        return tmp.next();
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {
        return Iterator::next();
    }

    bool hasNext() const {
        return Iterator::hasNext();
    }
};

1586. 二叉搜索树迭代器 II

实现二叉搜索树（BST）的中序遍历迭代器 BSTIterator 类：

• BSTIterator(TreeNode root) 初始化 BSTIterator 类的实例。二叉搜索树的根节点 root 作为构造函数的参数传入。内部指针使用一个不存在于树中且小于树中任意值的数值来初始化。
• boolean hasNext() 如果当前指针在中序遍历序列中，存在右侧数值，返回 true ，否则返回 false 。
• int next() 将指针在中序遍历序列中向右移动，然后返回移动后指针所指数值。
• boolean hasPrev() 如果当前指针在中序遍历序列中，存在左侧数值，返回 true ，否则返回 false 。
• int prev() 将指针在中序遍历序列中向左移动，然后返回移动后指针所指数值。

注意，虽然我们使用树中不存在的最小值来初始化内部指针，第一次调用 next() 需要返回二叉搜索树中最小的元素。

你可以假设 next() 和 prev() 的调用总是有效的。即，当 next()/prev() 被调用的时候，在中序遍历序列中一定存在下一个/上一个元素。

进阶：你可以不提前遍历树中的值来解决问题吗？

提示:

树中节点个数的范围是 [1, 1e5] 。
0 <= Node.val <= 1e6
最多调用 1e5 次 hasNext、 next、 hasPrev 和 prev 。

示例 1:
输入
[“BSTIterator”, “next”, “next”, “prev”, “next”, “hasNext”, “next”, “next”, “next”, “hasNext”, “hasPrev”, “prev”, “prev”]
[[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]]
输出
[null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]
解释
// 划线的元素表示指针当前的位置。
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // 当前状态为 [3, 7, 9, 15, 20]
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 3
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 7
bSTIterator.prev(); // 状态变为 [3, 7, 9, 15, 20], 返回 3
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 7
bSTIterator.hasNext(); // 返回 true
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 9
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 15
bSTIterator.next(); // 状态变为 [3, 7, 9, 15, 20], 返回 20
bSTIterator.hasNext(); // 返回 false
bSTIterator.hasPrev(); // 返回 true
bSTIterator.prev(); // 状态变为 [3, 7, 9, 15, 20], 返回 15
bSTIterator.prev(); // 状态变为 [3, 7, 9, 15, 20], 返回 9

代码 (C++)

在栈里维护当前节点 iter 的父亲链 fathers;

• iter 有后继的判定:
  • iter -> right != nullptr
  • 迭代父亲链，在父亲链耗尽之前，必须有某个父亲链中的相邻节点 f1, f2(f1 是 f2 的父节点)，有 f1 -> left == f2
• iter 有前驱的判定
  • iter -> left != nullptr
  • 迭代父亲链，在父亲链耗尽之前，必须有某个父亲链中的相邻节点 f1, f2(f1 是 f2 的父节点)，有 f1 -> right == f2

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        dummy = new TreeNode(-1);
        dummy -> right = root;
        iter = dummy;
    }

    bool hasNext() {
        if(iter -> right != nullptr)
            return true;
        int m = fathers.size();
        TreeNode *f2 = iter;
        for(int i = m - 1; i >= 0; --i)
        {
            TreeNode *f1 = fathers[i];
            if(f1 -> left == f2)
                return true;
            f2 = f1;
        }
        return false;
    }

    int next() {
        if(iter -> right != nullptr)
        {
            if(iter != dummy)
                fathers.push_back(iter);
            iter = iter -> right;
            while(iter -> left != nullptr)
            {
                fathers.push_back(iter);
                iter = iter -> left;
            }
            return iter -> val;
        }
        else
        {
            int m = fathers.size();
            TreeNode *f2 = iter;
            for(int i = m - 1; i >= 0; --i)
            {
                TreeNode *f1 = fathers[i];
                fathers.pop_back();
                if(f1 -> left == f2)
                {
                    iter = f1;
                    return iter -> val;
                }
                else
                    f2 = f1;
            }
            return -1;
        }
    }

    bool hasPrev() {
        if(iter -> left != nullptr)
            return true;
        int m = fathers.size();
        TreeNode *f2 = iter;
        for(int i = m - 1; i >= 0; --i)
        {
            TreeNode *f1 = fathers[i];
            if(f1 -> right == f2)
                return true;
            f2 = f1;
        }
        return false;
    }

    int prev() {
        if(iter -> left != nullptr)
        {
            fathers.push_back(iter);
            iter = iter -> left;
            while(iter -> right != nullptr)
            {
                fathers.push_back(iter);
                iter = iter -> right;
            }
            return iter -> val;
        }
        else
        {
            int m = fathers.size();
            TreeNode *f2 = iter;
            for(int i = m - 1; i >= 0; --i)
            {
                TreeNode *f1 = fathers[i];
                fathers.pop_back();
                if(f1 -> right == f2)
                {
                    iter = f1;
                    return iter -> val;
                }
                else
                    f2 = f1;
            }
            return -1;
        }
    }

private:
    TreeNode *iter;
    TreeNode *dummy;
    vector<TreeNode*> fathers; // [dummy -> iter] 的父亲链
};

---