2023届网易互联网秋招 0820笔试
T1
题意：给定两个数，每次可以删除其中一个数中的某一位，问最少删几次，使其中一个数是另一个数的倍数
数据范围：每个数<1e9
个人思路：基础bfs，每次往队列里丢下一步的可能的两个数的pair，同时用HashSet验重（已经丢进去过的不丢了）
结果：通过100%数据
T2
题意：给定一个长度为n的数组，每次可以使某个数+1，目标数组的要求为对任意一个数，其左右两个数相等，问至少进行几次操作
数据范围：要用O(n)算法
个人思路：该数组的奇数和偶数下标子数组分别要全部一样，那么找到奇数和偶数下标子数组的最大值，然后使子数组各自变为这个最大值即可。注意，两者最大值一样时，要使偶数下标子数组的全数+1
结果：通过100%数据
T3
题意：一个由r,e,d三个字符组成的长度为n的子串，定义e为好e的要求是:同时与r,d相邻。每次操作可以把串中的一个字符改为另一个字符，问要使好e最多，最少改动多少字符
数据范围：n<2e5（还是2e6不记得了）
个人思路：奇数长度的串很好贪，要么是redered...，要么是dereder...，扫一遍就行，偶数不知道怎么处理，xjb乱贪...
结果：通过80%数据
T4
题意：一个长为n的数组,找出有几个三元组i,j,k，满足i<j<k,a[i]==a[k]且a[i]>a[j]
数据范围：n<1e5，a[i]<1e9
个人思路：先将数组离散化（让最大值从1e9变成1e5），然后树状数组处理。枚举J，树状数组记录在J在某一个位置，每个数在J的左右两边各有几个数及其乘积（如左边有5个3，右边有2个3，那么tree[3].l=5, tree[3].r=2, tree[3].sum=5*2=10），每次求比J大的数的tree.sum即可，并且动态更新（每往右走一个数，tree[J].l+=1，tree[J+1].r-=1，同时记得更新sum）
add(int pos, long value, boolean isLeft) {
long diffValue = isLeft ? tree[pos].r * value : tree[pos].l * value;
if (isLeft) {
tree[pos].l += value;
} else {
tree[pos].r += value;
}
for (; pos < MAXN; pos += ((pos) & (-pos))) {
trees[pos].sum += diffValue;
}
} 结果：通过100%数据
吐槽：网站崩了10分钟，牛客的并发不行啊
#网易##做完网易2023秋招笔试题，我裂开了#
查看20道真题和解析