2020 年

作者 19级lf；修改 20-软工-高歌

1. 给定一个字符串，求其中元音字母（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())

   ---

2. 给定 Web 服务器上某个文件被请求的$n$个时间戳，确定该文件没有被请求的最大时间间隔。

   相关说明
   输入条件	一个长度大于 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:]))

   ---

3. 给定一个非负实数$f$，将其转换成最简分数表示。其中，最简分数指的是分子和分母只有公因数 1 的分数。

   相关说明
   输入条件	以定点十进制表示的非负实数$f$，比如 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))

   逻辑很简单，将$f$化为$\frac{f×10^{小数位数}}{10^{小数位数}}$，然后通过不断求最大公约数化简即可。要是不用牛顿迭代法（辗转相除法），单纯暴力约分估计也行，测试集比较水，应该不会丢分。这里需要注意的应该只有题目规定的“如果分子是 0，规定分母必须是 1”的特殊情况，不在不小心在这上面白白丢分了。

   ---

4. 定义一个包含$n$个字符（其中$k$个互不相同）的单词的熵如下：

   $E=p_0log_2p_0+p_1log_2p_1+\dots+p_{k-1}log_2p_{k-1}$

   其中$p_i=f_i/n$，而$f_i$是字符$i$在单词中的出现次数。给定多个单词，将它们按照熵的值从小到大排序，如果熵值一样，则按照字典顺序排序。

   相关说明
   输入条件	一个字符串列表，每个元素是一个小写英文单词
   输出要求	根据单词的熵排序后的列表
   其它要求	将代码写入函数 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 lst

   Python 中的 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()))

   ---

5. 给定一个$m$行$n$列的矩阵（用嵌套列表表示），按照顺时针进行螺旋式输出(如下图所示)。

   

   相关说明
   输入条件	$m≥1$，$n≥1$
   输出要求	输出结果放在一个列表中
   其它要求	将代码写入函数 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

   最后这个暴力写法应该是很多人比较喜欢也很容易写出来的做法。总体而言，这道题只要愿意花点时间，做出来应该并不困难。同理这道题也没有什么过分的测试集，基本只要写出来就不会丢分。

   ---

6. 使用字典 DC 来存储学生选课信息，其中键是课程代码（整数表示），值是一个列表，用来存放选修这门课程的学生学号（整数表示）。求选修$k$门课程的学生学号。

   相关说明
   输入条件	DC 是如上定义的字典，$k$是一个正整数
   输出要求	以列表返回满足条件的学生学号，按照降序排列
   其它要求	将代码写入函数 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

   ---

7. 假设你有任意多张 1 元、2 元、5 元和 10 元的纸币。给定正整数$n$，求支付$n$元的所有方案数。比如当$n=6$时，你有下面 5 种方案：1）6 张 1 元；2）1 张 2 元，4 张 1 元；3）2 张 2 元，2 张 1 元；4）3 张 2 元；5）1 张 5 元，1 张 1 元.

   相关说明
   输入条件	正整数$n$
   输出要求	满足条件的所有支付方案数
   其它要求	将代码写入函数 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 只要一大肯定要花很长时间，估计是得不到全分的。而其他两种应当都可以得全分。

   当然，有能力还是尽可能写动态规划，毕竟这种方法最快、空间开销也很小。暴力然后加缓存毕竟也算是奇淫巧计了，而且说不准未来的考试会不会加入空间限制，一旦加入空间限制这种方法也没法用了。

   ---

8. 找出一个字符串中所有的数字，其中整数用千分位形式表示，即从个位数起，每 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 分以内。