2022 年

作者 21级cy 及群内各成员集思广益贡献的代码；修改 20-软工-高歌

奶茶店的奶茶 10 元一杯，现在促销买 5 杯送 3 杯，买 3 杯送 1 杯，现有 $n$ 元，计算最多可以买多少杯。

测试用例：

解：第一题依然是一道不能更简单的基础题，没什么好说的。

def func1(n):
    a = n // 50  # 能买8杯的次数
    n %= 50
    b = n // 30  # 能买4杯的次数
    n %= 30
    c = n // 10  # 能买1杯的次数
    return 8 * a + 4 * b + c

给定两个整数 $n$ 和 $m$ ，计算区间 $[n, m]$ 中是三位数且是奇数的整数个数。
测试用例：
解：依然是一道没什么难度的题目。按最基本的思路，可以写出下面这样的代码：
```
def func2(n, m):
    result = 0
    for i in range(n, m + 1):
        if 100 <= i <= 999 and i % 2 == 1:
            result += 1
    return result
```
虽然上面的代码很明显没什么问题，也显然能拿全分，但你也可以考虑优化一下：
```
def func2(n, m):
    if m <= 100:
        return 0
    n = 100 if n < 100 else n if n % 2 == 0 else n - 1
    m = m + 1 if m % 2 == 1 else m
    return (m - n) // 2
```
然后是喜闻乐见的一行流代码：
```
def func2(n, m):
    return sum(1 for i in range(n, m + 1) if 100 <= i <= 999 and i % 2 == 1)
```
如果你真喜欢写一行流可以注意一下，列表推导式很多时候可以换成生成器推导式（用圆括号包裹），这样更省空间，然后作为函数参数的生成器推导式还可以进一步省略其两边的圆括号，就像上面的代码不用写成sum((1 for i in range(n, m + 1) if 100 <= i < 1000 and i % 2 == 1))或sum([1 for i in range(n, m + 1) if 100 <= i < 1000 and i % 2 == 1])。

已知一个正整数集合，如果将其中的数按从小到大的顺序排列，是缺失一个数的等比数列。请求出这个缺失的值。

测试用例：

解：这道题显然就是 2021 年的第 8 题换个皮，思路也是一致的：

def func3(s):
    if len(s) < 4:
        return -1
    s = sorted(list(s))
    t = s[-1] // s[0]  # 公比q ** len(s) == t
    q = 1
    while q ** len(s) < t:
        q += 1
    for i in range(len(s) - 1):
        if s[i] * q != s[i + 1]:  # 如果s[i + 1]不是s[i]的q倍，则缺失值为s[i] * q
            return s[i] * q

给定一个由大小写字母组成的驼峰字符串，求驼峰高度的最大值。其中驼峰字符串由小写字母开始与结束，小写与大写字母间隔出现，例如 aBa，xYa, eRdHp。驼峰高度根据三个相邻的字母（即小写大写小写）进行计算：中间大写字母 ASCII 码值分别减左右两边小写字母的 ASCII 码值，然后取绝对值，绝对值大的即为该峰的高度。计算所有峰高，并返回最大值。举例，eRdHp 有两个峰 eRd 与 dHp，其中 eRd 的峰高为 max(19, 18)=19, dHp 的峰高为 max(28, 40)=40，因此整个字符串的驼峰高度最大值是 40。
测试用例：
解：一道看着复杂其实做起来非常简单的题目，照着题目直接写就行。
```
def func4(s):
    result = 0
    for i in range(1, len(s), 2):
        # 小写字母ASCII码比大写字母大，分别计算差值，取最大值，并更新最大值
        result = max(result,
                     max(ord(s[i - 1]) - ord(s[i]),
                         ord(s[i + 1]) - ord(s[i])))
    return result
```
给定一个由整数组成的列表，对其进行排序。排序的依据是：根据整数的出现次数降序排序，如果两个整数的出现次数相同，那么根据整数的大小升序排序。
测试用例：
解：年年都会考的排序题，这一年也没什么特别的。
```
def func5(lst):
    dct = {}
    for i in lst:  # 统计所有数字出现次数
        dct[i] = dct.get(i, 0) + 1
    # 按照出现次数降序，出现次数相同按数字大小升序
    return sorted(lst, key=lambda x: (-dct[x], x))
```

给定一个 $n$ 行 $n$ 列的矩阵（用嵌套列表表示），将最大的数与最小的数互换位置，第二大与第二小的互换，以此类推，直至结束。返回转换后的嵌套列表。

测试用例：

解：也是很容易考到的矩阵题了，这道题用不到什么复杂的算法，还是挺简单的。下面是一种做法。做法有很多，不用局限于这里给出的一种。

def func6(matrix):
    n = len(matrix)
    # 将数值和坐标放在一起
    t = [(matrix[i][j], i, j) for i in range(n) for j in range(n)]
    t.sort()  # 按数值大小升序
    l, r = 0, n ** 2 - 1  # 左右指针
    while l < r:
        i1, j1 = t[l][1], t[l][2]  # 较小数的坐标
        i2, j2 = t[r][1], t[r][2]  # 较大数的坐标
        # 交换较小数和较大数
        matrix[i1][j1], matrix[i2][j2] = matrix[i2][j2], matrix[i1][j1]
        l += 1  # 两个指针向中间靠拢
        r -= 1
    return matrix

冠数定义为质因子只有 2，3 或 5 的正整数。方便起见，1 也定义为冠数。前 10 个冠数是 1，2，3，4，5，6，8，9，10，12。给定正整数 $n$ ，求第 $n$ 个冠数。

测试用例：

解：有一定难度的算法题，应该可以说是三年中最难的一道题了。这道题考察的应该是对动态规划的应用，此外这道题用小顶堆做起来也非常方便，但本意应该还是考察动态规划。

和往年的压轴题类似，这道题也是 LeetCode 的中等题，而且是那种广为流传的经典算法题，一般不叫作“冠数”而叫作“丑数”。不过这道题在 LeetCode 第 264 题，刷题不太勤快的同学可能碰不到。

这道题最重要的一点是要发现冠数一定是由冠数乘以 2、3、5 得到的。如果这点都没发现，你可能只能写出类似下面这样的暴力程序：

def func7(n):
    i = 1
    while n > 1:
        i += 1
        t = i
        while t % 2 == 0:
            t //= 2
        while t % 3 == 0:
            t //= 3
        while t % 5 == 0:
            t //= 5
        if t == 1:
            n -= 1
    return i

上面的代码显然只能得少部分分。但如果你发现了上面提到的规律“冠数一定是由冠数乘以 2、3、5 得到的”，那么可以对代码进行一些优化：

def func7(n):
    s = {1, 2, 3, 5}
    t = 1
    while n > 1:
        t += 1
        # 优化思路：冠数一定是冠数乘2、乘3或乘5
        if (t % 2 == 0 and t // 2 in s or
            t % 3 == 0 and t // 3 in s or
            t % 5 == 0 and t // 5 in s):
            n -= 1
            s.add(t)  # 将冠数加入集合中
    return t

上面的代码就可以得到一半分了。到这里为止，还不算太难。（注：有些同学可能会认为这里使用的in是 O(n)的，然而实际上由于集合是使用字典实现的，而字典的in是 O(1)的，因此集合的in也是 O(1)的，在这里这几个in不会对时间复杂度产生太大影响）

然而如果你稍微聪明一点，就可以发现你不需要一个数字一个数字这样试。为什么不每次选择最小的一个数，并将它乘以 2、3、5 然后添加到集合中呢？

def func7(n):
    s = {1}
    for i in range(n):
        t = min(s)
        s.remove(t)
        s.add(2 * t)
        s.add(3 * t)
        s.add(5 * t)
    return t

从理论上来说，上面的代码是得不到满分的，毕竟它还保留着一个 O(n)的min操作。但事实是这代码真能得满分，可能还是测试用例太水了。

没学过数据结构和算法的极限也就到这里了。下面给出使用动态规划的做法：

def func7(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    p2 = p3 = p5 = 1
    for i in range(2, n + 1):
        num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
        dp[i] = min(num2, num3, num5)
        if dp[i] == num2:
            p2 += 1
        if dp[i] == num3:
            p3 += 1
        if dp[i] == num5:
            p5 += 1
    return dp[n]

使用动态规划的一直是这样，代码很简单但思路不太容易想到，这里解释一下上面代码的思路（引自 LeetCode 第 264 题 zzxn 的题解）。

pi 是有资格同 i 相乘的最小冠数的位置。举例来说，一开始冠数只有{1}，1 可以同 2、3、5 相乘，取最小的 1×2=2 添加到序列中。

现在冠数有{1, 2}，因为 1 已经和 2 相乘过了，因此不用再算 1×2 了，因此 1 失去了和 2 相乘的资格，于是 p2 变成了 2，现在 1 有和 3、5 相乘的资格，2 有和 2、3、5 相乘的资格，但 2×3 和 2×5 没有必要比较，因为有更小的 1 可以和 3、5 相乘，所以只需要比较 1×3、1×5、2×2。

依次类推，每次分别比较有资格同 2、3、5 相乘的最小冠数，选择最小的那个最为下一个冠数，假设选择到的冠数是同 i（i=2/3/5）相乘得到的，所以它失去了同 i 相乘的资格，于是使对应的 pi += 1，让 pi 指向下一个冠数即可。

此外还有个经典的使用最小堆的写法，如果你学过最小堆应该能很容易想到。这也是个可以得全分的思路：

import heapq

def func7(n):
    factors = [2, 3, 5]
    seen = {1}  # 用集合防止元素重复添加
    heap = [1]

    for i in range(n - 1):
        curr = heapq.heappop(heap)  # 弹出堆顶元素
        for factor in factors:  # 向堆中添加当前元素的2、3、5倍
            nxt = curr * factor
            if nxt not in seen:
                seen.add(nxt)
                heapq.heappush(heap, nxt)

    return heapq.heappop(heap)

用最小堆的思路就很简单了，每次从堆顶取出最小元素 x，然后将 2x、3x、5x 加入堆中。这里使用集合去重。最小堆的解法时间复杂度为 $O(n\log{n})$ ，相比动态规划的 $O(n)$ 在时间复杂度上不是最优的，但胜在很容易想到，只要学过数据结构就会做。

按照 2022 年的情况来看，导入 heapq 模块并没有扣分。但如果你想保险一些，可以直接用 list 模拟最小堆：

def func7(n):
    def heap_insert(heap, i):  # 堆插入，如果当前节点比父节点小就交换
        while i != 0 and heap[i] < heap[(i - 1) // 2]:
            heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]
            i = (i - 1) // 2

    def heapify(heap, i, size):  # 堆调整，i是父节点下标，size是堆的规模，从根往叶交换
        l = 2 * i + 1  # 左子节点
        while l < size:  # 还有子节点时
            # 取较小的子节点的下标
            m = l + 1 if l + 1 < size and heap[l + 1] < heap[l] else l
            # 取父子中较小的下标
            m = m if heap[m] < heap[i] else i
            if m == i:  # 父节点小就说明已经换好了
                break
            heap[m], heap[i] = heap[i], heap[m]  # 否则将小的子节点和父节点交换
            i = m  # 更新父节点
            l = 2 * i + 1 # 更新左子节点

    factors = [2, 3, 5]
    seen = {1}  # 用集合防止元素重复添加
    heap = [1]
    for i in range(n - 1):
        curr = heap[0]  # 获取堆顶元素
        heap[0] = heap[-1]  # 将最后一个元素放到堆顶
        heap.pop()  # 删除最后一个元素
        heapify(heap, 0, len(heap))  # 从该元素开始进行堆调整
        for factor in factors:  # 向堆中添加当前元素的2、3、5倍
            nxt = curr * factor
            if nxt not in seen:
                seen.add(nxt)
                heap.append(nxt)
                heap_insert(heap, len(heap) - 1)

    return heap[0]

当然，堆毕竟是数据结构范畴的知识，理论上来说转专业考试不至于考到这个，出题老师的意思应该更多还是倾向于动态规划。

已知对于任意正整数 $n$ ，一定存在仅由 0 和 7 组成的数，它是 $n$ 的正整数倍。下表给出了若干例子。给定正整数 $n$ ，求满足条件的最小的数。

测试用例：

解：虽然这也不算一道简单题，但比起第 7 题，确实要简单不少。思路很多。

最简单的思路就是一个一个试：

def func8(n):
    lst = [7]
    while True:
        for num in lst:
            if num % n == 0:
                return num

        tmp = []
        for num in lst:
            tmp.append(num * 10)
            tmp.append(num * 10 + 7)

        lst = tmp

如果你聪明点可以发现，这个 7 和 0 组成的数字本质上就是个把 1 换成 7 的二进制，这样做更快一点：

def func8(n):
    num = 1
    while True:
        result = 0
        p = 1
        tmp = num

        while tmp:
            result += (tmp & 1) * 7 * p
            tmp >>= 1
            p *= 10

        if result % n == 0:
            return result

        num += 1

当然，上面两种思路都能得满分。就算你拿字符串拼接得到这个数字，应该也能得满分，问题不是很大。至于二进制的这种写法，想不到也无所谓，都能做。

总结

2022 年的题目总体上是按照难度从小到大排列的。其中前六题应当没有什么问题，也没涉及什么算法知识，同样也没有容易丢分的点。难度主要集中在最后两题，其中第 7 题比第 8 题更难，而第 8 题应该是比较容易得满分的。

除第 7 题外，整张卷子没有任何地方需要用到数据结构和算法的知识，也没考到正则表达式。第 7 题虽然比较困难，但想出个最简单的暴力解法还是很容易的，即使暴力按 4 分算，这张卷子也就扣个 6 分而已。因此从理论上说，这张卷子的编程题扣分应当和前两年在同一水准。

这张卷子整体让人感觉偏难主要还是第 7 题带来的，而后两题的时间限制是 2022 年新加的，这也给人一定的心理压力（虽然第 8 题的时间限制其实没啥意义，因为几乎不可能超过这个时间）。

一如既往，第 7 题涉及了往年的卷子中也很常用的算法动态规划，这道题的区别在于纯暴力做几乎不可能得到全分，而且需要发现一定的规律（冠数必然是其它冠数乘以 2、3、5）。这确实反映了这几年来转专业考试的难度在逐渐增大。

事实上在 2022 年之前这份指南中还说“不用学任何算法也能拿全分，尤其是数据结构”，但 2022 年的考试表明有时候学点数据结构做起来反而简单，比如这次第 7 题如果学过最小堆很容易想到怎么写，而动态规划的思路不那么好想。因此目前来说，是建议适当学点数据结构与算法的，毕竟谁也不知道未来的转专业考试是否会越来越难。

最后更新于1年前