Q2: Insert Items

实现一个函数，传入列表，一个值before，一个值after，在列表中每个等于before的之后插入after

def insert_items(s, before, after):
    """Insert after into s after each occurrence of before and then return s.

    >>> test_s = [1, 5, 8, 5, 2, 3]
    >>> new_s = insert_items(test_s, 5, 7)
    >>> new_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> test_s
    [1, 5, 7, 8, 5, 7, 2, 3]
    >>> new_s is test_s
    True
    >>> double_s = [1, 2, 1, 2, 3, 3]
    >>> double_s = insert_items(double_s, 3, 4)
    >>> double_s
    [1, 2, 1, 2, 3, 4, 3, 4]
    >>> large_s = [1, 4, 8]
    >>> large_s2 = insert_items(large_s, 4, 4)
    >>> large_s2
    [1, 4, 4, 8]
    >>> large_s3 = insert_items(large_s2, 4, 6)
    >>> large_s3
    [1, 4, 6, 4, 6, 8]
    >>> large_s3 is large_s
    True
    """
    idx = 0
    while idx<len(s):
        if s[idx]==before:
            s.insert(idx+1,after)
            idx+=1
        idx+=1
    return s

注意：

在before==after时，可能会一直在相同元素后添加相同元素，导致死循环
需要在每次相等时手动让idx向后移动一位
且需要判断长度防止死循环

Q3: Group By

实现函数，传入列表s与函数fn，返回一个字典

字典的值为s的元素，键为fn(e)，且对相同fn(e)的的元素在同一个列表中

def group_by(s, fn):
    """Return a dictionary of lists that together contain the elements of s.
    The key for each list is the value that fn returns when called on any of the
    values of that list.

    >>> group_by([12, 23, 14, 45], lambda p: p // 10)
    {1: [12, 14], 2: [23], 4: [45]}
    >>> group_by(range(-3, 4), lambda x: x * x)
    {9: [-3, 3], 4: [-2, 2], 1: [-1, 1], 0: [0]}
    """
    grouped = {}
    for val in s:
        key = fn(val)
        if key in grouped:
            grouped[key].append(val)
        else:
            grouped[key] = [val]
    return grouped

遍历s，计算key值，若存在则直接添加到key对应val的列表中，若无则创建列表并填入该值

Q5: Count Occurrences

实现一个函数，传入一个迭代器t，整数n和值x，返回前n个t中和x相等的的数值的个数

注意：在t上调用next n次，确保至少在t中有n个元素

def count_occurrences(t, n, x):
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    cnt = 0
    times = 0
    while cnt<n:
        if next(t)== x:
            times+=1
        cnt+=1
    return times

注意提前跳出循环一次，防止迭代器到尾后返回traceback

Q6: Repeated

实现函数，传入迭代器t与一个大于1的整数k，返回t中第一个连续出现k次的元素

def repeated(t, k):
    """Return the first value in iterator t that appears k times in a row,
    calling next on t as few times as possible.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(t, 3)
    8
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(u, 3)
    2
    >>> repeated(u, 3)
    5
    >>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(v, 3)
    2
    """
    assert k > 1
    pre = 0
    cnt = 0
    while True:
        cur = next(t)
        if cur == pre:
            cnt+=1
        else:
            cnt=1
        pre = cur
        if cnt == k:
            return cur

一开始想用两个迭代器，但是不会复制

每次调用迭代器的next值，并保存前一个值，每次比较

若前后相同，则计数重复+1，否则还原为1（自身重复一次）

Q7: Sprout Leaves

传入一颗树，与新的叶子节点，使该树延伸出对应叶子节点，通过print_tree输出

如t = tree(1, [tree(2), tree(3, [tree(4)])])

调用sprout_leaves(t, [5, 6])后打印出树如下

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    if is_leaf(t):
        return tree(label(t), [tree(leaf) for leaf in leaves])
    return tree(label(t), [sprout_leaves(s, leaves) for s in branches(t)])

Q8: Partial Reverse

实现函数，传入列表s与起始元素start，将start到列表末尾的元素反转

def partial_reverse(s, start):
    """Reverse part of a list in-place, starting with start up to the end of
    the list.

    >>> a = [1, 2, 3, 4, 5, 6, 7]
    >>> partial_reverse(a, 2)
    >>> a
    [1, 2, 7, 6, 5, 4, 3]
    >>> partial_reverse(a, 5)
    >>> a
    [1, 2, 7, 6, 5, 3, 4]
    """
    end = len(s)-1
    while start < end:
        s[start], s[end] = s[end], s[start]
        start+=1
        end-=1

使用序列解包，交换两个元素可以通过a,b=b,a实现

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【CS61A】CS61A——Lab5