9.2美团

100 100 6.67 45 100
想问问各位哥第三题怎么写
就是那个要使第一个数最大的最小操作数
例如:
4
1 2 3 4
输出:
2

可对任一元素x2或/2向下取整。
每次笔试遇到这种题目都不会
全部评论
第三题样例很少,很多100%的其实不对。比如1 2 5 这个其实只需要2次,但是看评论的一些方法需要3次。我的思路是,找出最大元素,和次大元素,先把最大元素/2,直到“将”要比次大元素小。在把第一个元素*2直到比次大元素大。再看下此时和最大元素比还需不需要再乘一次2。这个正确性证明:如果此时想让第一个元素少乘一次2,就要让最大和次大都要/2,所以肯定步数会变多。而对于最大元素,其除2向下取整比第一个元素*2要小的多一些,肯定贪心希望最大元素尽量除2(比如1,2,5这种5/2=1肯定比2*2划算)。
2 回复 分享
发布于 2023-09-02 21:52 上海
记录首个元素,排序,如果记录元素不是排序后的倒数第二个直接乘2直到大于,是倒数第二个判断一下最大的除2个数与乘2个数比较
2 回复 分享
发布于 2023-09-02 21:15 黑龙江
要维护一个堆吧,当然如果图省事情可以直接第一个数乘2,也可以过83
点赞 回复 分享
发布于 2023-09-03 01:16 广东
排序数组nums[1, n],第一个数依次乘2,直到剩余最后一个数,最后一个数除以2
点赞 回复 分享
发布于 2023-09-02 22:14 北京
把第一个数提出来 剩下的找出最大的那个数循环/2,每除一次结果加一,直到比第一个数小或者相等。通过100
点赞 回复 分享
发布于 2023-09-02 22:10 浙江
把第一个数字拿出来,剩下的从小到大排序,并遍历i=1->n-1,如果第一个数字小于当前的a[i],则让第一个数字*=2知道大于等于;如果大于直接跳过。 最后若是走到n-1的位置,则判断a[n-1]/=2所需的步数,和a[0]*=2的步数(直到a[0]>a[n-1])的最小值,用最小值更新一下答案。 这样一来1 2 5的例子,一开始1会和2比大小,然后a[0]变成2,然后和5比大小,发现5/=2比1*2*2要用的次数少,所以最后的答案就是2. 当时这样考虑贪心是因为,如果你当前的a[0]没和最后一位数字比大小,那么不需要让最后的a[n-1]除以2,因为前面还有很多没比过大小的n-2,n-3等等的位置,这些位置如果你想执行除以2的操作,那实际上肯定不如a[0]*=2的操作快。所以真正要比较的只有a[0]和a[n-1]
点赞 回复 分享
发布于 2023-09-02 22:06 北京
我用的最大堆,每次要么第一个翻倍,要么减半最大值再比较,每一步都贪婪取最大缩短差距的那个方案(维护一个 max-min的差值变量);
点赞 回复 分享
发布于 2023-09-02 21:45 四川
第三题我是这么做的,先把除第一个数以外的数字升序排序,然后分两个方向计算,一个从左往右,一个从右往左。第一种只需要计算第一个数字跟最后一个数字差了几倍就可以了,连续乘2直到大于等于最后一个数字,乘的次数就是从左往右的结果。然后再从右往左,先从最后一个数字开始,所有大于第一个数的数字都连续除以2直到小于等于第一个数字,所有除以二的次数加起来就是从右往左的计算结果,最后两种方向的结果取最小值就是答案。
点赞 回复 分享
发布于 2023-09-02 21:30 重庆
大佬,问下第二题怎么做的,我只过了90多😭😭
点赞 回复 分享
发布于 2023-09-02 21:27 湖南
先遍历找到最大数,然后只要第一个数还大于最大数就判断,如果最大数mod2余1,那就最大数除2,要不然就第一个数乘2,这样直到第一个数大于最大数,退出循环,返回操作的个数结果就行
点赞 回复 分享
发布于 2023-09-02 21:23 广东
就只有一种情况,全数组只有个数大于第一个数,并且这个数%2=1。这种情况用这个数/2会比直接乘2第一个数少一次
点赞 回复 分享
发布于 2023-09-02 21:22 山东
把除了第一个数都放进优先队列,每次取出比较一下然后除2放回
点赞 回复 分享
发布于 2023-09-02 21:21 广东
找到最大数,往下取整除不就行了
点赞 回复 分享
发布于 2023-09-02 21:14 广东
第三题写了个dp通过了85%
点赞 回复 分享
发布于 2023-09-02 21:12 辽宁
正难则反,你只需要枚举需要增加多少次。这个增加显然只会对a[1] 增加,然后判断剩下的元素需要减少多少次。这样复杂度就是( log(1e9) * N)。
点赞 回复 分享
发布于 2023-09-02 21:11 浙江
猜了一个首位不是前二就乘法,否则除法,过了…
点赞 回复 分享
发布于 2023-09-02 21:11 北京

相关推荐

2025-12-27 16:21
已编辑
门头沟学院 Java
bg:中下211本科,java后端,无竞赛,无基础,大一升大二暑假开始学java。五段实习:美团-小红书-腾讯-淘天-字节。面秋招的简历只有美团、小红书、淘天。刚刚发现我的秋招蚂蚁流程挂了,这是我最后一个流程,那么我的秋招就算彻底结束了,总结一下:字节ssp+,职级2-1。美团ssp,+2打了半小时微信电话极力挽留。快手ssp,但报了字节薪资后没有争取的想法了。小红书sp,今年小红书给的很高,但比字节2-1还是差很多。虾皮应该是小sp?对虾皮一点意向都没,纯拿来集邮了。淘天ssp(暑期转正),说不要我的三方,毕业前考虑好了随时可以不签三方选择淘天。挂了的流程:京东二面挂,估计学历被卡了。懂车帝一面挂,和面试官聊不来,不认同我的方案。拼多多hr面挂,问我低于预期还来不来,当时说不考虑了,估计觉得我不忠诚。蚂蚁hr面挂,聊的还行,但估计我不会去给我挂了吧。阿里控股一面挂,没面前就知道是kpi了,因为时间可选的很多,而且都是半小时,我也拿他刷我的kpi了。上面差不多是我的情况,下面是我想说的话。我觉得我不算特别突出优秀的那类人,但我多少也算是靠前的那一批人,即使这样,秋招也不算特别顺利,也有挂了的流程,但你能说是我的问题吗,我觉得大部分情况不是的,如果真的是我的问题,我不可能本科校招拿到2-1,所以很多面试挂了,问题不出在面试者身上,很多是看运气+眼缘+和面试官合不合得来。所以我觉得,学会察言观色,了解面试官的脾性,也是面试很重要的一个点。比如面试官是喜欢听长回答,还是听短回答,他更看重哪些点,每个面试官对这些的侧重都是不一样的,所以作为面试者,要学会察言观色,通过面试官开局的一两个问题以及你回答后他的表现,就要判断出来。像我现在其实面试开局个五分钟,我就基本能判断个七七八八了,然后我后面的回答就会有所变化。这是我想说的第一个点:不要为面试结果焦虑,有时候问题不出在你身上,但你可以学一些面试技巧,尽量提高你的面试通过率,这里说的面试技巧指的不是网上那种烂大街的,一两分钟短视频说什么提高你面试通过率的,而是你要在你自己的面试过程中不断总结经验,吸取教训,旁人教你的终究是有限的。另外想说下选offer的事,上面其实可以看出来,我秋招最后是选了字节的,还没签三方我就来提前实习感受业务了,当我签完三方又过了一个多月,我这些天又在想这个问题,字节真的是我想要的吗,我现在总结了一下字节的好坏,发现当时可能被字节的高薪资影响判断了,如果现在再选一次的话,我应该会选杭州的小红书,会生活的更舒服点。具体种种就不展开说了。然后虽然我现在也可以说去把小红书舔回来,去毁字节,但我觉得没必要这么做,我可以采用其他的措施去不就,比如规划好两年内就跳槽,跳到杭州,跳到更舒适的城市。我觉得大家选offer的时候,真的可以冷静下来多方面考虑,薪资、城市、组内氛围、业务、老板是否看重、组内情况、未来升职机会等等都是可以考虑的因素,虽然有的时候不管选哪个,都不会坏,但最好也别让自己后悔吧,即使真后悔了,我觉得也没必要过度美化没走过的路,想好补救措施即可。这是我想说的第二个点:冷静好好做选择,不管是offer还是其他。但人生容错率很大,即使选错了,也一定有补救措施。最后还想说一些成长上的东西,尤其是现在AI火热的时代。我觉得大家如果想提高自己,或者说在未来社招跳槽有竞争力,肯定是要学AI相关的东西的,不说要会多懂AI,至少也要了解基本概念,而且一定要学会用AI提效。我现在字节的mt和我说,他现在80%代码都是AI写的。而我最近也开始尝试用AI工具,感觉现在AI真的进步很多,挺聪明的了,我现在写需求基本都是先让AI写,我再人工review小改动一下就差不多了。我觉得「AI取代程序员」是个很远的话题,但是「AI取代不会用AI的程序员」,可能真的就是近两年的事了。而怎么去学习这块的内容,其实我也正在探索,我也是刚学AI的起步阶段,我觉得大家也要有自己的信息检索能力,而不是别人喂你什么,你才学什么,自己一个人就不会学了。这是我想说的第三个点:趁年轻,多学习提升自己,拥抱AI,不要原地踏步,原地踏步的程序员最容易被淘汰。大概就是这样吧,今天看蚂蚁流程发现挂了,前几天腾讯约面我也拒了,就想到自己的秋招/校招算彻底结束了,有感而发,随便聊了下。牛客以后应该不会更新,大家不用关注,熟悉我的朋友应该知道我在其他平台有号。我更喜欢以长视频的形式去做分享,感觉会更有体系,而不是网上那种一两分钟的零碎短视频的那种营销号去起号,我也推荐大家多去看高质量的长文章、长视频,我觉得收获的能更多。希望大家能收获满意的offer与未来。
CEXBB:刷到最后才发现原来是优雅✌🏻,我的Java引路人
2025年终总结
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务