2021 年

By 20-软工-高歌

一个正整数，如果它能被 9 整除，或者它的十进制表示法中某一位上的数字为 9，则称其为与 9 相关的数。请计算所有小于等于 $n(n < 100)$ 的与 9 无关的正整数的平方和。
测试用例：
解：作为第一题还是很简单的一道题目。数据量很小，不需要什么优化，暴力做就行。一般这种题目如果已经明确指出数据量很小就不要考虑优化了，也不会多得分，纯属浪费时间。
```
def func1(n):
    result = 0
    for i in range(n):
        if not (i % 9 == 0 or '9' in str(i)):
            result += i * i
    return result
```
要是乐意也可以一行流，实际上一行流还会稍微快一点（10%左右，其实也比较有限，意义不大）
```
def func1(n):
    return sum(i * i for i in range(n) if not (i % 9 == 0 or '9' in str(i)))
```
现有一个列表 lst 包含了 $n$ 个 $[-100,100]$ 之间的整数，请编写程序返回出现次数最多的整数，当有多个出现次数相同的整数时，请返回最小的那一个整数。
测试用例：
解：经典 Python 题，没什么好说的。这里代码中最后 max 的 key 也可以写成key=lambda x: count[x]，可能更好理解点。如果看不懂最后的 max 是怎么回事，先用 sorted 按值排个序取第一个也可以，方法很多，这里只给出一个参考。
```
def func2(lst):
    if len(lst) == 0:
        return None
    count = {}
    for num in lst:
        count[num] = count.get(num, 0) + 1
    return max(count, key=count.get)
```
需要注意的一点是题目中说明 lst 为空时返回 None，不要忽略这种地方导致白白丢分。
Python 中实际上还提供了 Counter 类用于类似的场景。不过就这道题来说，没什么必要。而且如果用 Counter 很轻松地解决了问题，难说会不会扣分。
```
from collections import Counter

def func2(lst):
    if len(lst) == 0:
        return None
    return Counter(lst).most_common(1)[0][0]
```

给定一个元素是 $[0,9]$ 之间的整数且没有重复数字的列表 lst，返回其所有可能的全排列。全排列列表中的每个元素也是列表，全排列列表按照数值从小到大排序。

测试用例：

解：2021 年的这道全排列题确实是有些出人意料，主要是这道题出现在这么靠前的位置有些劝退，实际上后面大多数题都比这道题简单。虽说如此，全排列这道题也是一道非常经典的回溯基础题了，LeetCode 第 46 题和这题完全一样，区别只是这道题需要多个排序而已。如果刷题比较勤快，这道题是应该没有什么问题的。

下面演示一个最简单直接的暴力递归做法。虽然暴力，但时间开销其实和标准回溯差不多：

def func3(lst):
    def go(lst):
        if len(lst) == 0:
            return [[]]
        elif len(lst) == 1:
            return [lst]
        else:
            head, tail = lst[0], lst[1:]

            result = []
            for l in go(tail):  # 对每个子列表分别插值
                for i in range(len(l) + 1):
                    result.append(l[:i] + [head] + l[i:])

            return result

    return sorted(go(lst))  # 最后排序，减少时间开销

上面的代码有一定的优化空间，例如把range(len(l) + 1)提到前面去，但不会在时间复杂度上有太大的变化。

如果用回溯法，代码会更清晰也更简单，但这需要一定的技巧。当然，作为一种非常基础的算法，回溯是建议认真学习的：

def func3(lst):
        def backtrack(first=0):
            # 所有数都填完了
            if first == n:
                result.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]

        n = len(nums)
        result = []
        backtrack()
        return sorted(result)

上面这个解法来自 LeetCode 题库第 46 题的官方题解。如果你对这种解法感到很陌生，可以直接去 LeetCode 看题解，并认真学习一下回溯。此外全排列这道题过于经典，因此应当全网都能找到很多教程，这里就不赘述了。

此外 Python 中也确实存在函数可以直接进行全排列。但这种解法过于简单，所以 2021 年这么做题的人全部得了零分。下面给出这种解法，但这个解法在考试里是没有分的。事实上，当时考试时监考老师也发现了这个问题，警告直接使用 permutations 不会给分。不要不信邪。

from itertools import permutations

def func3(lst):
    return sorted(map(list, permutations(lst)))

itertools 模块中的函数全都是用 C 语言实现的，因此速度比较快。官方文档也提供了一种使用 Python 的实现，这个实现返回一个迭代器，感兴趣可以看一下。其中参数 r 可以指定生成序列的长度，否则默认生成长度为 iterable 长度的排列。

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

官方文档中还提供了另一种使用 product 的实现，感兴趣可以阅读https://docs.python.org/zh-cn/3/library/itertools.html?highlight=permutations#itertools.permutations

现有一个全部是英文字母的字符串 string，string 中包含了若干个单词，单词和单词之间以一个空格分开，string 的最前面和最后面没有空格。请编写程序对这些单词排序，返回排序单词组成的字符串。返回结果时单词和单词之间用一个空格分开，最前面和最后面没有空格。

排序规则如下：

首先，按照单词长度从大到小排序；
其次，单词长度相等时按照字典序从小到大排序（不区分大小写）；
最后，如果两个单词不区分大小写后相同，则按照 ASCII 码从小到大排序

测试用例：

解：这道题是比上一题简单多了，考察的只是最基本的排序。考虑到 Python 存在比较强大的排序函数，这道题做起来相当轻松：

def func4(string):
    words = string.split(' ')
    words.sort(key=lambda x: (-len(x), x.lower(), [ord(i) for i in x]))
    # 事实上Python本身对纯英文字母就是按照ASCII码排序的，
    # 因此这里可以简单写成key=lambda x: (-len(x), x.lower(), x)
    return ' '.join(words)

如果上面对 key 函数的应用令你感到困惑，这里有一个冒泡排序版本，原理是一样的：

def func4(string):
    words = string.split(' ')
    length = len(words)
    for i in range(length - 1):
        for j in range(length - 1 - i):
            a, b = words[j], words[j+1]
            if len(a) != len(b):
                if len(a) < len(b):
                    words[j], words[j+1] = b, a
            elif words[j].lower() != words[j+1].lower():
                if words[j].lower() > words[j+1].lower():
                    words[j], words[j+1] = b, a
            elif [ord(x) for x in a] != [ord(x) for x in b]:
                if [ord(x) for x in a] > [ord(x) for x in b]:
                    # 事实上Python本身对纯英文字母就是按照ASCII码排序的，
                    # 因此这里可以简单写成a != b和a > b
                    words[j], words[j+1] = b, a
    return ' '.join(words)

如果你接触过 C、Java 等语言，会知道这些语言中通过接收一个返回-1/0/1 的函数来确定排序顺序。这个函数接收两个参数 a、b，当 a<b 时返回-1，当 a=b 时返回 0，当 a>b 时返回 1。实际上 Python 2 时就存在函数 cmp 可以实现这一目的。即使在 Python 3 中，也可以导入 cmp_to_key 函数实现需求：

from functools import cmp_to_key

def func4(string):
    def sortFn(a, b):
        if len(a) != len(b):
            if len(a) > len(b):
                return -1
            elif len(a) < len(b):
                return 1
        elif a.lower() != b.lower():
            if a.lower() < b.lower():
                return -1
            elif a.lower() > b.lower():
                return 1
        else:  # 按ASCII码排序
            if [ord(i) for i in a] < [ord(j) for j in b]:
                return -1
            elif [ord(i) for i in a] > [ord(j) for j in b]:
                return 1
        return 0

    words = string.split(' ')
    words.sort(key=cmp_to_key(sortFn))
    return ' '.join(words)

上面的代码比较冗长，但其实也很清晰。

篮球三分球团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。现给定所有队员的比赛成绩，请你编写程序找出冠军队。
输入是一个列表 lst，它的每个元素是一个包含三个元素的列表，三个元素都是整型，分别代表队伍编号、队员编号和成绩。
- 其中队伍编号为 1 到 1000 的正整数；
- 队员编号为 1 到 10 的正整数；
- 成绩为 0 到 100 的整数；
- 题目输入保证冠军队是唯一的。
测试用例：
解：一道非常轻松的题，甚至连队员编号都没什么用……
```
def func5(lst):
    score = {}
    for l in lst:
        score[l[0]] = score.get(l[0], 0) + l[2]
    return max(score.items(), key=lambda item: item[1])
```
甚至可以写在一行。当然这个就纯属炫技了，不建议用。
```
from itertools import groupby

def func5(lst):
    return max({key: sum(g[2] for g in group)
                     for key, group
                     in groupby(sorted(lst), key=lambda x: x[0])}
               .items(), key=lambda item: item[1])
```
有一个机器人爬楼梯，它每步可以爬 1 阶，也可以爬 2 阶。如果合计有 1 阶，那么该机器人只有 1 种走法；如果合计有 2 阶，机器人可以走 2 次 1 阶，也可以 1 次走 2 级，因此有 2 种走法。编写程序计算 $n$ 米机器人有多少种走法。
测试用例：
解：一道过于经典的递归题，应该是大多数人接触到的第一道递归题目了，这道题如果做不出来那实在是有些说不过去。
```
def func6(n):
    def go(n):
        if n == 1:  # 1阶只有一种爬法
            return 1
        if n == 2:  # 2阶有爬两次1阶和爬一次2阶两种爬法
            return 2
        else:  # 其他阶数为爬n-1阶再爬1阶和爬n-2阶再爬2阶的爬法之和
            return go(n-1) + go(n-2)
    return go(n)
```
当然，上面这个只是最简单的解法。稍微思考可以发现，在递归过程中对于一些阶数的爬法会反复重新计算，例如计算 5 阶，会计算 go(4)、go(3)，计算 go(4)时又会计算 go(3)和 go(2)，可以发现这里 go(3)重复算了两次。当 n 增大时，整个函数的耗时会因此飞速增加。解决方法也很简单，加个缓存即可，这应该是很常见的思路。
```
def func6(n):
    cache = {}
    def go(n):
        if n == 1:  # 1阶只有一种爬法
            return 1
        if n == 2:  # 2阶有爬两次1阶和爬一次2阶两种爬法
            return 2
        else:  # 其他阶数为爬n-1阶再爬1阶和爬n-2阶再爬2阶的爬法之和
            if n in cache:
                return cache[n]
            else:
                cache[n] = go(n-1) + go(n-2)
                return cache[n]
    return go(n)
```
下面将 n 设为 30，然后使用 timeit 函数对两个函数分别测试 100 次取平均值：
```
>>> from timeit import timeit
# 旧函数
>>> timeit(lambda: func6(30), number=100)
0.15679146766662597
# 新函数
>>> timeit(lambda: func6(30), number=100)
2.0000934600830078e-05
```
可以看到加入缓存的提升是十分明显的。因此建议涉及递归时都使用缓存。学校的测试机器暂时对占用空间还是没什么要求的，尽可能用空间复杂度换时间复杂度是很划算的。甚至在极端情况下，打表也是可以得到很不错的分数的，虽然不太建议这么做。尽管给出的测试集或许简单到不需要缓存也能得满分，但还是建议尽量使用缓存，这不过是顺手的事。
此外，Python 当然也提供了简单的装饰器可以直接为函数加上缓存，和上面人工加缓存效果一样：
```
from functools import lru_cache

def func6(n):
    @lru_cache
    def go(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return go(n-1) + go(n-2)
    return go(n)
```
如果你不太清楚装饰器的用法，可以简单认为上面的装饰器等同于在函数定义后运行一遍go = lru_cache(go) ，事实上这正是装饰器的工作原理，十分简单。相当于：
```
from functools import lru_cache

def func6(n):
    def go(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return go(n-1) + go(n-2)

    go = lru_cache(go)

    return go(n)
```
不过这里的 lru_cache 同样是不太建议使用的，毕竟谁也不知道会不会扣分。
当然，如果你也想像使用 lru_cache 一样使用简单的装饰器实现类似的功能，可以自己定义，这也非常简单：
```
def func6(n):
    def cache_it(fn):
        cache = {}
        def new_fn(*args):
            if args in cache:
                return cache[args]
            else:
                cache[args] = fn(*args)
                return cache[args]
        return new_fn

    @cache_it  # 你当然也可以不使用装饰器，改在函数定义后补上一句go = cache_it(go)
    def go(n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return go(n-1) + go(n-2)

    return go(n)
```
上面实现了一个最简单的缓存装饰器。如果要应用到实际场景中，需要考虑一些更复杂的问题，例如使用类装饰器，但在这里这个简单的装饰器已经足够了。
"lru_cache"中的"lru"是什么意思？
你可能会好奇这里的"lru"是什么意思。"lru"就是"Least Recently Used"，即“最近最少使用”的简写。这是一个比我们上面的简单缓存高级些的缓存。我们上面实现的那个基本缓存有个问题，就是当 n 特别大的时候，缓存也会变得特别大，甚至有可能导致内存不足（虽然在这个简单的例子中，这事情不太可能发生）。
因此，更好的办法是限制缓存的大小。"lru"正如字面意思一样，当缓存大小超过上限时，就会将“最近最少使用”的那个缓存对（在这里，就是键值对）从缓存中删除。在多数情况下，这种删除方案能够使得删除缓存中的某一项对缓存产生的效果影响最小。lru_cache 既提高了速度，又没有占用太大的空间，是一个不错的解决思路。
这个思路很容易实现，你也可以很容易实现这样一个"lru_cache"，这里就不给出具体示例了。
需要指出的是，学校考察的这些题目都非常简单，我认为不需要在考试时实际实现一个 lru_cache，一个最简单的 cache 就已经够用了。在考试时实现 lru_cache 有些浪费时间，说不定还会出 BUG。
给定一个由元组构成的列表 lst，其中每个元组由 2 个 0 至 99 之间的整数元素构成。设有两个元组 $t_1$ 和 $t_2$ ，如果 $t_1$ 中的元素都不比 $t_2$ 中对应（同一位置）的元素大，且 $t_1$ 中至少存在一个元素比 $t_2$ 中对应元素小，则称 $t_1$ 支配 $t_2$ 。保留 lst 中所有不被任何元组支配的元组，并将 lst 按元组第 1 个元素从小到大的顺序排列。返回排序后的列表 lst。
测试用例：
解：同样是一道比较轻松的题目。题目可能要花点时间才能看懂，但做起来很简单。
```
def func7(lst):
    result = []
    for t2 in lst:
        is_dominated = False
        for t1 in lst:
            if t1 == t2:
                continue
            if t1[0] <= t2[0] and t1[1] <= t2[1]:
                is_dominated = True
                break
        if not is_dominated:
            result.append(t2)
    return sorted(result)
```
上面是最直接的解法。这里同样要注意一下返回 None 的条件，不要忘了。

已知一个元素都是整数的等差数列缺失了一个值，求出这个缺失值。

测试用例：

解：一样是一道非常轻松的题目。

def func8(lst):
    if len(lst) < 4:
        return None
    # 先排序
    lst.sort()
    # 依次判断两两数字之差
    diff = lst[1] - lst[0]
    for i in range(1, len(lst) - 1):
        d = lst[i+1] - lst[i]
        if d > diff:
            return lst[i] + diff
        elif d < diff:
            return lst[i-1] + d

上面的思路很简单，先排序，然后依次判断两两数字之差，并保存上一个两两数字之差的结果。若此次得到的差与上次结果不一致，则较小的那个差一定为等差数列的差，然后根据情况计算并返回缺失数。

甚至这道题简单到可以一行解决：

def func8(lst):
    return (lambda l:
        (lambda diffs: l[diffs.index(max(diffs))] + min(diffs))(
            [j - i for i, j in zip(l[:-1], l[1:])])
    )(sorted(lst))

总结

整体来说 2021 的题目还是很简单的，但凡 LeetCode 上刷过五十道题都能全部做出来。

唯一的困难可能在于第 3 题全排列，然而即使这道题使用简单的暴力递归也能比较完美地做出来并得到全分，稍微刷点题就会做。

然后第 6 题机器人爬楼梯那道题可能会有人因为没考虑缓存而丢分，但同样的，只要刷过题就几乎不可能忽略缓存的问题，而且甚至很难说按考试给的测试集，不考虑缓存是否会丢分。

第 7 题虽然是一道找规律题，但直接按题目思路做也不会有太大的时间开销，按转专业考试一贯的测试集较水的传统，应当也不会丢分。

除此之外，丢分应当就只能是考虑不周，例如没看到题目中要求返回 None 的条件，或是因为忽略了一些明显的边界条件。总体而言，其他题目只要通过了给出的测试样例应当就不会丢分了。

整张卷子没有一点要用到数据结构，也没有一题必须要使用真正意义上的算法，几乎只涉及递归。即使全排列所需用到的回溯，也是可选的，简单递归也能做得很不错。

理论上来说只要认真准备，考试时正常发挥，这张卷子编程题是可以得全分的，难度并不算大。

最后更新于1年前