8.17美团算法笔试 极差思路

#美团求职进展汇总#
前三题A了,第四题暴力枚举过了70%,第五题放了
第一题送分
第二题最大公约数,这对学数学尤其学过数论的来说就比较简单了,比较坑的是他的测试用例给错了,57明明不是素数。想让最大公约数是素数那就找他的第一个素因子就行了,如果这个数本身是素数那就是他本身。

第三题极差,其实只有两种情况,甚至是只有一种情况,设medium=sum//n:
1.数组的和能被数组长度(即一共多少个数)整除,即sum%n==0:这时候极差最终会是0,那就算把每个数变到那个平均数的操作数就可以了,然后再把操作数除以2就是操作数(因为每次操作是一个+1一个-1)
2:数组的和不能被数组长度整除,设m=sum%n,这时候极差最小是1,也就是最终状态是有m个数是medium+1,剩下n-m个数是medium。这时候把数组拍个序,对前n-m个数算和medium小了多少(要+1多少次),后m个数算比medium大了多少(要-1多少次),次数加一起除个2就行了。
为什么说其实只有一种情况,因为第一种是第二种里m=0的情况
全部评论
好多算法工程师
1 回复 分享
发布于 08-19 21:10 黑龙江
m
点赞 回复 分享
发布于 08-18 23:42 浙江
m
点赞 回复 分享
发布于 08-19 12:57 广东
m
点赞 回复 分享
发布于 08-19 14:26 江西
m
点赞 回复 分享
发布于 08-19 17:15 浙江
m
点赞 回复 分享
发布于 08-20 08:19 广东
算法太卷了
点赞 回复 分享
发布于 08-23 16:40 黑龙江

相关推荐

10-24 13:36
门头沟学院 Java
Zzzzoooo:更新:今天下午有hr联系我去不去客户端,拒了
点赞 评论 收藏
分享
2 5 评论
分享
牛客网
牛客企业服务