字节研发第二场笔试思路分享

四道编程，没有选择，俩小时。

1：

题目：输入两个小写字母组成的字符串a, b. 定义相似度为ab的相同前缀长度×相同后缀长度。 问，最多可以修改a中一个字符，最大相似度是多少。 数据范围 1 <= a.len, b.len <= 1e5。

思路：

记录两个数组left和right，right[i]表示，从a[i]开始，向右，一共有right[i]个字符和b相等。left[i]反之

然后遍历常识a中每个下标的可能替换值，如果从相等变成了不相等或者从不相等变成了相等。结合right和left数组拼接一下得到当前的相似度。

感觉做麻烦了，应该是从前向后找第一个不匹配的换掉，在从后往前找第一个不匹配的换掉。暴力就行了。

2：

题目：一个矩阵，每个坐标值可能为"red", "blue", "green"。q次询问x1, y1, x2, y2矩形范围内颜色种类数。数据范围：矩阵行列1~500，查询次数1~50000.

思路：就三种颜色。维护每种颜色的前缀和，查找的时候区间范围内如果不为0就种类+1

3：

题目：定义一个数字串的权值为：奇数位的和×偶数位的和。问：所有长度为n的数字串(可以有前导0)他们的权值是多少？数据范围：2 <= n <= 1e9。

思路：范围比较大，不能遍历，应该是一道数学思考题。

考虑一下，对于任意两个下标 i（奇数）和 j（偶数），他们俩乘积对结果的贡献可能有多少？

1×1 + 1×2 + ... + 1×9 + 2×1 + 2×2 + ... + 2×9 + · · · + 9×1 + 9×2 + ... + 9×9

= （1 + 2 + ... + 9) × (1 + 2 + ... + 9) = 45 * 45

而剩下的下标可能的组合数量为 = 10 ^ (n-2)

所以 i 和 j 对结果的可能贡献为 45 * 45 * 10 ^ (n-2)

而这样的 i 和 j 一共有多少对呢？一共有 奇数下标个数 * 偶数下标个数对

所以结果为 result = (n+1)/2 * n/2 * 45 * 45 * 10 ^ (n-2)

注意每一步乘法取模

4:

题目：定义f(x)为数字x的最大数位的值，f(5271)=7, f(112341)=4, f(981)=9。输入l和r，问l<=x<=r，的所有f(x)的和。数据范围：1 <= l, r <= 1e18。

思路：就是典型的数位dp，可以参考利口233.数字1的个数