> For the complete documentation index, see [llms.txt](https://gaoge011022.gitbook.io/suda-major-change-guide-cs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gaoge011022.gitbook.io/suda-major-change-guide-cs/wang-nian-kao-ti-ji-ti-jie/2020.md).

# 2020 年

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

1. 给定一个字符串，求其中元音字母（a、e、i、o、u）的个数。

   | **相关说明** |               |
   | -------- | ------------- |
   | 输入条件     | 一个任意长度的字符串    |
   | 输出要求     | 元音字母的个数       |
   | 其它要求     | 将代码写入函数 func1 |

   测试用例：

   | **输入**   | **返回** |
   | -------- | ------ |
   | 'Java'   | 2      |
   | 'Python' | 1      |

   解：一道非常基础的 Python 题，做法有很多，这里给出比较常规的一种。

   ```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
   ```

   然后是经典的一行流代码，可读性很差，没必要学，但可以图一乐。

   ```python
   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      |

   解：同样是比较简单的一道题，没太多好说的。

   ```python
   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
   ```

   同理，这题的代码也能很容易写在一行。

   ```python
   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 库中的函数然后做错了。实际上直接做也没太大难度。

   ```python
   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'] |

   解：一样没什么难度，考察一些简单排序知识的掌握。只要会点基本语法这题应该没什么问题。

   ```python
   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 参数，传入一个自定义的函数，该函数依次处理原序列中的值并得到新值，按照得到的新值序列排序。这个算是很常规的用法，每年都会考的，有疏漏的建议留意一下。

   如果善用推导式的话，上面的代码可以进一步简化，但执行效率没太大提升：

   ```python
   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$$列的矩阵（用嵌套列表表示），按照顺时针进行螺旋式输出(如下图所示)。

   ![](https://s3.bmp.ovh/imgs/2022/05/30/9647c41a9c080e42.png)

   | **相关说明** |                 |
   | -------- | --------------- |
   | 输入条件     | $$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 题一模一样，稍微刷点题应该不至于做不出来。

   ```python
   def func5(matrix):
       result = []
       while matrix:
           result += matrix.pop(0)  # 取矩阵第一行并删除
           matrix = list(zip(*matrix))[::-1]  # 旋转矩阵
       return result
   ```

   上面是个比较简洁的答案，有些地方会有一些技巧性。但即使你写不出上面这样漂亮的代码，也可以直接模拟来做，代码冗长一些，但思路也是很清晰的。下面是 LeetCode 上的标准题解：

   ```python
   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
   ```

   标准题解更考虑通用性，整体逻辑有些复杂。当然，你也可以再简单粗暴一点，给四个转弯处每个都写个循环判断：

   ```python
   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]     |

   解：这题的难度可比上一题低多了，没什么好说的。

   ```python
   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     |

   解：一道经典的背包问题，算是压轴题。通用思路是用动态规划做。下面是个比较标准的做法：

   ```python
   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]
   ```

   即使你对动态规划不太熟悉，纯暴力做应该也能得到大部分分。下面演示一个比较暴力的做法：

   ```python
   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 一旦较大运行速度会很慢，所以有可能得不到全分。那么你可以添加缓存加快一下，这很简单：

   ```python
   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 测试：

   ```python
   >>> 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 三年中唯一需要使用正则表达式的题目。当然，正则表达式本质上都可以用循环和判断代替，考试时间很够，慢慢写循环判断也没有任何问题。

   下面是使用正则表达式的做法：

   ```python
   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 分以内。