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 服务器上某个文件被请求的nn个时间戳，确定该文件没有被请求的最大时间间隔。

    相关说明

    输入条件

    一个长度大于 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. 给定一个非负实数ff，将其转换成最简分数表示。其中，最简分数指的是分子和分母只有公因数 1 的分数。

    相关说明

    输入条件

    以定点十进制表示的非负实数ff，比如 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))

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

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

    E=p0log2p0+p1log2p1+⋯+pk−1log2pk−1E=p_0log_2p_0+p_1log_2p_1+\dots+p_{k-1}log_2p_{k-1}

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

    相关说明

    输入条件

    一个字符串列表，每个元素是一个小写英文单词

    输出要求

    根据单词的熵排序后的列表

    其它要求

    将代码写入函数 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. 给定一个mm行nn列的矩阵（用嵌套列表表示），按照顺时针进行螺旋式输出(如下图所示)。

    相关说明

    输入条件

    m≥1m≥1，n≥1n≥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 来存储学生选课信息，其中键是课程代码（整数表示），值是一个列表，用来存放选修这门课程的学生学号（整数表示）。求选修kk门课程的学生学号。

    相关说明

    输入条件

    DC 是如上定义的字典，kk是一个正整数

    输出要求

    以列表返回满足条件的学生学号，按照降序排列

    其它要求

    将代码写入函数 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 元的纸币。给定正整数nn，求支付nn元的所有方案数。比如当n=6n=6时，你有下面 5 种方案：1）6 张 1 元；2）1 张 2 元，4 张 1 元；3）2 张 2 元，2 张 1 元；4）3 张 2 元；5）1 张 5 元，1 张 1 元.

    相关说明

    输入条件

    正整数nn

    输出要求

    满足条件的所有支付方案数

    其它要求

    将代码写入函数 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 分以内。

上一页2021 年下一页苏州大学计算机科学与技术学院 2022 年本科生转专业工作实施细则

最后更新于