### Problem 2: Repeated Implement `repeated`, which takes in an iterator `t` and returns the first value in `t` that appears `k` times in a row. > **Note:** You can assume that the iterator `t` will have a value that appears at least `k` times in a row. If you are receiving a `StopIteration`, your `repeated` function is likely not identifying the correct value. Your implementation should iterate through the items in a way such that if the same iterator is passed into `repeated` twice, it should continue in the second call at the point it left off in the first. An example of this behavior is in the doctests. ```python def repeated(t, k): """Return the first value in iterator T that appears K times in a row. Iterate through the items such that if the same iterator is passed into the function twice, it continues in the second call at the point it left off in the first. >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7]) >>> repeated(s, 1) 10 >>> repeated(s, 2) 9 >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7]) >>> repeated(s2, 3) 8 >>> s = iter([3, 2, 2, 2, 2, 2, 2, 4, 4, 5, 5, 5]) >>> repeated(s, 3) 2 >>> repeated(s, 3) 2 >>> repeated(s, 3) 5 >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5]) >>> repeated(s2, 3) 2 """ assert k >= 1 "*** YOUR CODE HERE ***" ```

一种解法是使用两个指针，一个指向当前考察的值，一个指向上一个已经出现了 $k$ 次的值。具体而言，我们用变量 `current` 记录当前考察的值，用变量 `last` 记录上一个已经出现了 $k$ 次的值，用变量 `count` 记录当前考察的值已经出现的次数。如果 `count` 达到了 $k$，那么返回 `current`。否则，如果 `current` 与 `last` 相同，说明已经有 $count+1$ 次出现了 `current`，所以 `count` 加 1。否则，将 `count` 设为 1，`last` 设为 `current`，继续迭代。

由于题目要求能够在同一个迭代器上多次调用 `repeated`，我们可以使用一个 `collections.deque` 来缓存已经迭代过的值，这样每次调用 `repeated` 的时候就可以继续从上一次结束的地方开始迭代。下面是实现的代码：

from collections import deque

def repeated(t, k):
    """
    Return the first value in iterator T that appears K times in a row.
    Iterate through the items such that if the same iterator is passed into
    the function twice, it continues in the second call at the point it left
    off in the first.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 1)
    10
    >>> repeated(s, 2)
    9
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s2, 3)
    8
    >>> s = iter([3, 2, 2, 2, 2, 2, 2, 4, 4, 5, 5, 5])
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    5
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(s2, 3)
    2
    """
    assert k >= 1
    last, current, count = None, None, 0
    cache = deque()
    while True:
        if not cache:
            try:
                current = next(t)
            except StopIteration:
                return None
        else:
            current = cache.popleft()
        
        if current == last:
            count += 1
            if count == k:
                return current
        else:
            count = 1
            last = current
        
        cache.append(current)