2020 年
作者 19级lf；修改 20-软工-高歌
给定一个字符串，求其中元音字母（a、e、i、o、u）的个数。
相关说明
输入条件
一个任意长度的字符串
输出要求
元音字母的个数
其它要求
将代码写入函数 func1
测试用例：
输入
返回
'Java'
2
'Python'
1
解：一道非常基础的 Python 题，做法有很多，这里给出比较常规的一种。
def func1(s): result = 0 vowel_set = {'a', 'e', 'i', 'o', 'u'} for i in s.lower(): # 全部转成小写 if i in vowel_set: result += 1 return result然后是经典的一行流代码，可读性很差，没必要学，但可以图一乐。
def func1(s): return sum(i in {'a', 'e', 'i', 'o', 'u'} for i in string.lower())给定 Web 服务器上某个文件被请求的个时间戳，确定该文件没有被请求的最大时间间隔。
相关说明
输入条件
一个长度大于 1 的整数列表，每个元素是一个时间戳
输出要求
输出最大时间间隔
其它要求
将代码写入函数 func2
测试用例：
输入
返回
[1, 5]
4
[10, 7, 15, 9]
5
解：同样是比较简单的一道题，没太多好说的。
def func2(lst): lst.sort() result = lst[1] - lst[0] for i in range(1, len(lst) - 1): result = max(result, lst[i + 1] - lst[i]) return result同理，这题的代码也能很容易写在一行。
def func2(lst): return max(j - i for i, j in zip(sorted(lst)[:-1], sorted(lst)[1:]))给定一个非负实数，将其转换成最简分数表示。其中，最简分数指的是分子和分母只有公因数 1 的分数。
相关说明
输入条件
以定点十进制表示的非负实数，比如 1.23，.23，1 都是有效的输入
输出要求
以元组形式返回最简分数的分子和分母，如果分子是 0，规定分母必须是 1
其它要求
将代码写入函数 func3
测试用例：
输入
返回
1.25
(5, 4)
11.25125
(9001, 800)
解：本身不算太难的一道题目，但当年有不少人调用 decimal 库中的函数然后做错了。实际上直接做也没太大难度。
def func3(f): def gcd(m, n): # 辗转相除法求最大公约数 return gcd(n % m, m) if n % m != 0 else m if f == 0: return (0, 1) n = len(str(f).split('.')[1]) # 获得小数部分位数 x, y = f * 10 ** n, 10 ** n # 求最大公因数 m = gcd(x, y) return (int(x / m), int(y / m))逻辑很简单，将化为，然后通过不断求最大公约数化简即可。要是不用牛顿迭代法（辗转相除法），单纯暴力约分估计也行，测试集比较水，应该不会丢分。这里需要注意的应该只有题目规定的“如果分子是 0，规定分母必须是 1”的特殊情况，不在不小心在这上面白白丢分了。
定义一个包含个字符（其中个互不相同）的单词的熵如下：
其中，而是字符在单词中的出现次数。给定多个单词，将它们按照熵的值从小到大排序，如果熵值一样，则按照字典顺序排序。
相关说明
输入条件
一个字符串列表，每个元素是一个小写英文单词
输出要求
根据单词的熵排序后的列表
其它要求
将代码写入函数 func4
测试用例：
输入
返回
['aaa', 'aba', 'abc']
['abc', 'aba', 'aaa']
['ant', 'bat', 'cat', 'dog']
['ant', 'bat', 'cat', 'dog']
解：一样没什么难度，考察一些简单排序知识的掌握。只要会点基本语法这题应该没什么问题。
def func4(lst): def calculate(s): n = len(s) dct = {} for c in s: # 统计字符c在单词中的出现次数 dct[c] = dct.get(c, 0) + 1 E = 0 for fi in dct.values(): # 计算熵值E pi = fi / n E += pi * math.log2(pi) return E lst.sort(key=calculate) return lstPython 中的 max、min、sort、sorted、reverse、reversed 等函数都接收一个可选的 key 参数，传入一个自定义的函数，该函数依次处理原序列中的值并得到新值，按照得到的新值序列排序。这个算是很常规的用法，每年都会考的，有疏漏的建议留意一下。
如果善用推导式的话，上面的代码可以进一步简化，但执行效率没太大提升：
def func4(lst): return sorted(lst, key=lambda s: sum((fi / len(s)) * math.log2(fi / len(s)) for fi in {c: s.count(c) for c in set(s)}.values()))给定一个行列的矩阵（用嵌套列表表示），按照顺时针进行螺旋式输出(如下图所示)。
相关说明
输入条件
，
输出要求
输出结果放在一个列表中
其它要求
将代码写入函数 func5
测试用例：
输入
返回
[[1, 2], [3, 4]]
[1, 2, 4, 3]
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]
[1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]
解：难度不算太大的一道题，要做好需要一些技巧，但暴力做应当也没什么问题。这道题和 LeetCode 题库中的第 54 题一模一样，稍微刷点题应该不至于做不出来。
def func5(matrix): result = [] while matrix: result += matrix.pop(0) # 取矩阵第一行并删除 matrix = list(zip(*matrix))[::-1] # 旋转矩阵 return result上面是个比较简洁的答案，有些地方会有一些技巧性。但即使你写不出上面这样漂亮的代码，也可以直接模拟来做，代码冗长一些，但思路也是很清晰的。下面是 LeetCode 上的标准题解：
def func5(matrix): if not matrix or not matrix[0]: return list() rows, columns = len(matrix), len(matrix[0]) visited = [[False] * columns for _ in range(rows)] total = rows * columns order = [0] * total directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] row, column = 0, 0 directionIndex = 0 for i in range(total): order[i] = matrix[row][column] visited[row][column] = True nextRow, nextColumn = (row + directions[directionIndex][0], column + directions[directionIndex][1]) if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]): directionIndex = (directionIndex + 1) % 4 row += directions[directionIndex][0] column += directions[directionIndex][1] return order标准题解更考虑通用性，整体逻辑有些复杂。当然，你也可以再简单粗暴一点，给四个转弯处每个都写个循环判断：
def func5(matrix): result = [] if matrix is None: return result top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 while True: for i in range(left, right + 1): # ➡️ result.append(matrix[top][i]) top += 1 if top > bottom: break for i in range(top, bottom + 1): # ⬇️ result.append(matrix[i][right]) right -= 1 if right < left: break for i in range(right, left - 1, -1): # ⬅️ result.append(matrix[bottom][i]) bottom -= 1 if bottom < top: break for i in range(bottom, top - 1, -1): # ⬆️ result.append(matrix[i][left]) left += 1 if left > right: break return result最后这个暴力写法应该是很多人比较喜欢也很容易写出来的做法。总体而言，这道题只要愿意花点时间，做出来应该并不困难。同理这道题也没有什么过分的测试集，基本只要写出来就不会丢分。
使用字典 DC 来存储学生选课信息，其中键是课程代码（整数表示），值是一个列表，用来存放选修这门课程的学生学号（整数表示）。求选修门课程的学生学号。
相关说明
输入条件
DC 是如上定义的字典，是一个正整数
输出要求
以列表返回满足条件的学生学号，按照降序排列
其它要求
将代码写入函数 func6
测试用例：
输入
返回
DC = {1: [10, 11, 12], 2: [10, 11], 3: [10, 12]}, k = 1
[]
DC = {1: [10, 11, 12], 2: [10, 11], 3: [10, 12]}, k = 2
[12, 11]
DC = {1: [10, 11, 12], 2: [10, 11], 3: [10, 12]}, k = 3
[10]
解：这题的难度可比上一题低多了，没什么好说的。
def func6(DC, k): students = {} for subject in DC.values(): # 建立 {学生学号:选课数目} 的字典 for stu in subject: students[stu] = students.get(stu, 0) + 1 result = [] for stu in students.items(): # 将符合条件的学生学号加入结果 if stu[1] == k: result.append(stu[0]) result.sort(reverse=True) # 降序排列 return result假设你有任意多张 1 元、2 元、5 元和 10 元的纸币。给定正整数，求支付元的所有方案数。比如当时，你有下面 5 种方案：1）6 张 1 元；2）1 张 2 元，4 张 1 元；3）2 张 2 元，2 张 1 元；4）3 张 2 元；5）1 张 5 元，1 张 1 元.
相关说明
输入条件
正整数
输出要求
满足条件的所有支付方案数
其它要求
将代码写入函数 func7
测试用例：
输入
返回
6
5
16
25
解：一道经典的背包问题，算是压轴题。通用思路是用动态规划做。下面是个比较标准的做法：
def func7(n): # 动态规划完全背包问题 (空间优化版本) money = [1, 2, 5, 10] result = [1] + [0] * n for i in money: for j in range(i, n + 1): result[j] += result[j - i] return result[n]即使你对动态规划不太熟悉，纯暴力做应该也能得到大部分分。下面演示一个比较暴力的做法：
def func7(n): def go(n): if n < 0: return set() elif n == 0: return {(0, 0, 0, 0)} else: result = set() for t in go(n-1): result.add((t[0] + 1, t[1], t[2], t[3])) for t in go(n-2): result.add((t[0], t[1] + 1, t[2], t[3])) for t in go(n-5): result.add((t[0], t[1], t[2] + 1, t[3])) for t in go(n-10): result.add((t[0], t[1], t[2], t[3] + 1)) return result return len(go(n))上面这个做法的原理很简单，就是枚举所有情况，使用集合去重，最后输出集合的长度。
当然，上面的解法过于暴力，且递归导致的重复比较多，因此 n 一旦较大运行速度会很慢，所以有可能得不到全分。那么你可以添加缓存加快一下，这很简单：
def func7(n): cache = {} def go(n): if n in cache: return cache[n] else: if n < 0: result = set() elif n == 0: result = {(0, 0, 0, 0)} else: result = set() for t in go(n-1): result.add((t[0] + 1, t[1], t[2], t[3])) for t in go(n-2): result.add((t[0], t[1] + 1, t[2], t[3])) for t in go(n-5): result.add((t[0], t[1], t[2] + 1, t[3])) for t in go(n-10): result.add((t[0], t[1], t[2], t[3] + 1)) cache[n] = result return result return len(go(n))这样一来效率就高了不少。由于学校的测试对空间开销没什么要求，因此这么做应当没什么问题。
然后使用 timeit 函数对动态规划的解法和暴力解法分别测试 100 次，取平均时间，这里拿 n=25 测试：
>>> from timeit import timeit # 动态规划 >>> timeit(lambda: func7(25), number=100) 9.99927520751953e-06 # 暴力（无缓存） >>> timeit(lambda: func7(25), number=100) 0.6817917537689209 # 暴力（带缓存） >>> timeit(lambda: func7(25), number=100) 0.00043999433517456055可以看到，显然动态规划的时间开销最小，而且空间开销也非常小。而带缓存的暴力解法用空间换取了较小的时间开销，无缓存的暴力解法则要比其它两个解法都慢几个数量级，n 只要一大肯定要花很长时间，估计是得不到全分的。而其他两种应当都可以得全分。
当然，有能力还是尽可能写动态规划，毕竟这种方法最快、空间开销也很小。暴力然后加缓存毕竟也算是奇淫巧计了，而且说不准未来的考试会不会加入空间限制，一旦加入空间限制这种方法也没法用了。
找出一个字符串中所有的数字，其中整数用千分位形式表示，即从个位数起，每 3 位之间加一个逗号，比如 1,000,000，小数用定点十进制表示，并且小数点之前至少有一位数字（比如 0.618 中的 0 不可省略）。
相关说明
输入条件
一个字符串
输出要求
以列表返回该字符串中所有的数字，按照数值升序排列
其它要求
将代码写入函数 func8
测试用例：
输入
返回
'1.23-0.23=1.00'
['0.23', '1.00', '1.23']
'1,234.56-234.56=1,000'
['234.56', '1,000', '1,234.56']
解：这应该是 2020、2021、2022 三年中唯一需要使用正则表达式的题目。当然，正则表达式本质上都可以用循环和判断代替，考试时间很够，慢慢写循环判断也没有任何问题。
下面是使用正则表达式的做法：
def func8(s): pattern = re.compile('(\d{1,3}(,\d\d\d)*(\.\d+)?)') wordtuple = pattern.findall(s) wordlist = [] for tuple in wordtuple: for word in tuple: wordlist.append(word) break def str2num(word): word = word.replace(',', '') return eval(word) wordlist.sort(key=str2num) return wordlist值得注意的是这道题理论上可能会出现各种迷惑测试用例，例如"23,54.578,678,76"，其中的逗号就不是作为千分位分隔符的，如果只是按照简单忽略逗号的做法，这个字符串只能提取出"2354.57867876"这一个数字，即使对小数点后的逗号作额外判断，也只能提取出"2354.578"、"678"、"76"这三个数字。写判断需要考虑不少边界情况，做起来虽然不困难但耗时比较长，且容易漏情况。因此这道题使用正则表达式应该是最好的做法。
当然，学校给的测试集一如既往的水，即使写判断漏了很多情况，也能拿全分。当时有不少人就是慢慢写循环判断得的全分。没必要过于担心。
总结
相较于 2021 年的卷子，这张卷子要稍显困难一些，主要的困难在于最后两道题，此外螺旋矩阵那题也会花一些时间。
不过总体上来说，这张卷子仍然不需要太多的算法甚至数据结构知识，除第 7 题涉及动态规划，其他题目正常做都能得全分。即使第 7 题，暴力做也能得 6~8 分，学校的测试用例并不过分。
详细来说，第一个难点在于第 5 题螺旋矩阵。螺旋矩阵是一道很经典的题目，不过题目本身并不考察对算法的掌握。即使用常见的模拟思路暴力做，只要熟练也不会花费太多时间。况且这道题在 LeetCode 上排在很靠前的位置，稍微刷点题应该不至于得不到全分。
第二个难点是第 7 题，一道完全背包问题。如果要得全分，这道题最好用上动态规划。但是同样的，由于测试用例比较简单，你也可以尝试暴力解题，然后加个缓存进行一下加速，应该也能得全分。即使纯暴力解题，也能得到 6~8 分。当然，作为一道很经典的动态规划基础题，这题其实也属于那种稍微刷点题就能做出来的。
第三个难点是第 8 题，这里考察的主要是正则表达式的运用。当然对于不熟悉正则表达式的同学，路也没堵死，慢慢写循环判断一样能得全分。考试时间比较充裕，这题应当问题不大。
总的来说，这依然是一张理想情况下得全分也没有太大问题的卷子。即使算上一些意外因素，比如做到第 8 题时间不够用还没学过正则表达式因此来不及写出比较完美的代码，又比如第 7 题只写了个简单暴力解法得了一半分，这张卷子的编程题应当扣分也能控制在 8 分以内。
最后更新于