2023 字节笔试题 0827
笔试时间:2023年8月27日 秋招
第一题
题目:小红的字符串相似度
假设字符串s和t的最长相同前缀的长度是a,最长相同后缀的长度是6。小红认为字符串s和t的相似度是a x b。现在小红想进行最多一次修改,s的一个小写字母改成另一个小写字母,使得相似度尽量大。问相似度最大是多少?
输入描述
第一行输入一个仅包含小写字母的字符串s;
第二行输入一个仅包含小写字母的字符串t;
1 < len(s), len(t) < 10^5
输出描述
输出一个整数。
样例输入
abc
abba
样例输出
4
提示:
将s串的第三个字符改成‘a’,s串变成"aba"。最长相同前经和后缀分别是"ab"和"ba”。
参考题解
Python:
def cal(s, t): p = 0 q = 0 n = len(s) m = len(t) while p < n and p < m and s[p] == t[p]: p += 1 while n - q > 0 and m - q > 0 and s[n - q - 1] == t[m - q - 1]: q += 1 return p * q def main(): s = input() t = input() n = len(s) m = len(t) ans = cal(s, t) p = 0 q = 0 while p < n and p < m and s[p] == t[p]: p += 1 if p < n and p < m: ch = s[p] s = s[:p] + t[p] + s[p + 1:] ans = max(ans, cal(s, t)) s = s[:p] + ch + s[p + 1:] while n - q > 0 and m - q > 0 and s[n - q - 1] == t[m - q - 1]: q += 1 if n - q > 0 and m - q > 0: ch = s[n - q - 1] s = s[:n - q - 1] + t[m - q - 1] + s[n - q:] ans = max(ans, cal(s, t)) s = s[:n - q - 1] + ch + s[n - q:] print(ans) if __name__ == "__main__": main()
第二题
题目:小红的颜色矩阵
小红拿到了一个短阵,矩阵中格子的颜色为红色、绿色或者蓝色。现在小红有q次询问,每次询问一个子矩阵,希望你输出这个子短阵的颜色种类数。
输入描述
第一行输入两个正整数n,m,代表矩阵的行数和列数;
接下来的n行,每行输入m个字符串(字符串一定是“red"”、"green"、"blue"中的一种,代表格子的颜色);
接下来的一行,输入一个正整数q,代表小红的询问次数;
接下来的q行,每行输入四个正整数x1,y1,x2,y2代表询问的子矩阵左上角为第x1行第y1列,右下角为第x2行第y2列。
输出描述
输出q行,每行输出一个整数,代表颜色的数量。
样例输入
3 3
red blue blue
red blue blue
green green green
2
1 2 2 3
2 1 3
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。