美团秋招8.17笔试 JAVA后端开发

选择题10题（30分）

算法 + JAVA + 计网 + 计组 八股

难度中等，算法考察了二叉排序树，二叉树前中后序，图的广搜深搜

编程题3题（20 + 20 + 30）

1.T组询问，给定一个数字n, 找到一个数字m满足1<=m <= n使得 gcd(n, m) 为质数

做法：直接枚举就好

2.给定一个长度为n的数组a, 每次操作可以让 a[i] -> a[i] - 1, a[j] -> a[j] + 1, 问最少多少次操作可以使得数组极差最小。

做法：令 k = sum % n, svg = sum / n, 构造一个序列 b，后 k 个数为 svg + 1, 剩余数为 svg

将 a 升序排序后， 因为加减对称，所以答案就是 a[i] - b[i] (a[i] > b[i]) 的和。

3.给定一个长度为 n 的数组 a, 和一个数字 k, 每次操作必须选择一个非空区间 [l, r] 将区间中所有数字乘上 k , A先手且希望最终数组和最大， B后手希望数组和最小，问一轮过后数组和 sum 是多少。

数据范围： 1 <= n <= 1e3, -1e9 <= a[i], k <= 1e9

做法：

k > 0 ：可以枚举 A 的操作区间，问题转化为动态维护全局最小子段和，因为 B 一定操作最小子段和区间

k = 0： 答案为 0

k < 0 ：相反，维护全局最大子段和

实现：n^2 枚举 A 操作区间，线段树单点修改维护区间最小/大子段和, 详见https://blog.csdn.net/m0_51156601/article/details/124014996

复杂度： O(n^2logn)

不知道是否有大佬提供O(n^2)及以内的做法，欢迎讨论。