苏大CS预推免机试复盘

本文最后更新于：2025年9月2日 晚上

2025 Soochow University预推免机试复盘

批次：第一批下午场(8/30 13-16)

语言：python

不用外部库，尽量用最基础的包

格式类似leetcode的关键函数格式，但是不能实时判断是否解答题目，需要自己编写测试用例。最后提交一个py文件。

1. 日期是否合法

✅

注意判断闰年的方式：(y % 400 == 0) or (y % 4 == 0 and y % 100 != 0)

2.从仅含字母与数字的字符串中提取整数，求区间内的最小值与最大值

✅

给定字符串 s（只含 [a-zA-Z0-9]），以及闭区间 [L, R]。从 s 中提取所有连续数字形成的整数，筛出落在 [L,R] 的，输出它们的 min 和 max。

3. 判断 num 是否为「不含重复数字的素数」

输入num < 1e8

✅

用试除法判断素数加速处理

考试时，注意到题目中提到的数据量要求，但是没有想到取根号的技巧，仅使用了朴素的判断素数的方法，可能会导致超时

1
2
3
4
5
6
7
8
def is_prime(num):
	if num < 2: return False
	if num % 2: return num == 2
	r = int(math.isqrt(num))   # 取num的平方根
	for i in range(3, r + 1, 2):
		if num % 2 == 0: 
			return False
	return True

判断是否有重复数字

考试时知道应该用位掩码的方案，但是我不太会，就用了下面这个笨笨的方法，希望判卷不卡内存和时间😭

1
2
3
def distinct_digit(num):
	s = str(n)
	return len(s) == len(set(s))

4. 给定整数数组 arr 和一个个位数 d [0..9]，找出所有中间位等于 d 的数，返回其中最大值。若无，输出 -1

✅

奇数位数的数，其正中间那一位；偶数位数的数时偏左的那一位

基础的一道双指针

5. 过滤文件：后缀匹配 + 文件名回文（忽略大小写），返回第一个

✅

（这个有点奇怪，测试样例中返回的是下标为1的数？？？？

给定 n 个文件名和目标后缀（扩展名）ext，找出第一个满足：

  • 后缀为 ext（一般大小写不敏感）；
  • 不含后缀的basename为回文（忽略大小写）

6. 蛇形遍历矩阵（lc 498 Medium)

❌

这题遗憾，浪费了很多时间，没有做出来；

7. 每 k 个结点一组反转链表 （lc 25 Hard)

✅

给定单链表头指针和整数 k，将链表每 k 个结点一组翻转（不足 k 的尾部保持原样），返回新表头。

8. 二叉树（不记得了!）

9. 乘积最大子数组 (lc 152 Medium)

❌

没时间做了，又丢一题。

10. 打家劫舍 (lc 198 medium)

✅

题目其实是决定让哪家捐钱，不抢钱

有时间限制，我没时间想优化了，直接默写l

1
2
3
4
5
6
7
8
9
10
def rob(nums):
	n = len(nums)
	# dp[i]: 偷i间房子，收获的最大金额
	# dp[i] = max(dp[i-1], dp[i - 2] + num[i-1])     
	dp = [0] * (n + 1)
	dp[0] = 0     # 一间都不偷
	dp[1] = nums[0]  # 对于第一间，只有一个选择 -》 偷
	for i in range(2, n+1):
		dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])   #下标容易乱，注意一些
	return dp[n]

留个疑问，这个怎么做时间优化？还是说这个解法能过测试