米哈游笔试思路分享(2025-03-08)

第一题

送分题，模拟

第二题

解答题目意思，需要找到字符串的两个子串(长度>2)是回文字符，返回任意两个回文子串的区间即可

思路一 动态规划

用f[i][j] 表示 [i, j]区间子串是不是回文串

状态转移方程：if s[i] == s[j]: f[i][j] = f[i + 1][j - 1]

如何递推？

普通的dp递推一般是按照方程从前往后递推或者从后往前递推，但是注意到这里的方程里有 i + 1, j - 1 一个往前，一个往后。两个方向都不行，怎么办呢？

• 可以使用队列来递推，比如队列里先保存[i, j], 取出[i, j]后往两边递推，既看[i - 1, j + 1]满不满足回文，是回文的话就放入队列

如何初始化？

考虑单数和偶数情况

• 单数情况下初始情况为单个字符，单个字符肯定是回文，需要把所有单个字符全部放入队列，既[i, i] (for i in [0, s.length])
• 偶数情况下初始情况为0个字符，肯定是回文，全部放到队列即可，注意区间取值[i, i - 1] (for i in [1, s.length])

优化

题目只需要任意两个回文子串，所以我们找到两个后就可以提前结束

思路二 暴力 + 剪枝

直接暴力枚举 4个坐标 + 判断回文 是会超时的，可以进行一些优化

我们可以剔除一些明显不满足题意的情况，例如我们枚举[i, j, m, n] 四个坐标

• 当[i, j] 区间不为回文时，[m, n]就不需要枚举了

对于判断字符串是不是回文，可以用双指针

最终伪代码如下

for(i in [0, s.length - 3))
	for(j in [i + 1, s.length - 2))
		if(check(i, j)){ // 检查[i, j]是不是回文
			for(m in [j + 1, s.length - 1)){
				for(n in [m + 1, s.length)){
					if(check(m, n)){
						return {i, j, m, n};
					}
				}
			}
		}

顺带一提，我发现暴力还比第一种思路耗时会小些

第三题

n个字符串， 需要两两判断，看两个字符串同一个位置字符差异个数是否小于k，小于k就可以放到同一个集合

可以使用并查集，先两层遍历判断两个字符串差异值是否小于k，小于的话就合并

最终看并查集里面最大的集合的个数m是不是等于字符串个数n

• 是的话，输出YES
• 不是的话，说明有多个集合，输出NO, 保留最大的集合满足最小操作次数，既 (n - m)

最后，如果对你有用的话，求个花花