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的情况
前三题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的情况
全部评论
好多算法工程师
m
m
m
m
m
算法太卷了
相关推荐
11-01 04:25
卡内基·梅隆大学 Java xbbb:请问什么时候约的面啊?我的两周前发了邮件抢面试,没抢到结果就再也不发了😡
查看3道真题和解析 秋招你被哪家公司挂了?
点赞 评论 收藏
分享
点赞 评论 收藏
分享