10.9号京东编程题2求解释

如图这是2021.10.9日京东笔试的第二道代码题，刚开始没啥思路，然后先是用1,2,3骗分，AC在18卡着不动，后边开始想着用一些常规手段进行求解，估计也能过40多吧，然后就用差值开始求解，依然卡在18不动。再后边再次添油加醋（注意，此时把k错认为了每次可以增加的值），然后写了如下代码，一提交，竟然AC了100，当时以为自己理解了，下来以后一思考，感觉自己完全理解失误了呀，所以想问问各位大佬，我这个代码有没有什么合理性的解释，我想着就算是瞎猫碰上死耗子，也不至于AC了100吧

#笔经##京东#

全部评论

推荐最新楼层

孙大剩

楼主

华为_通用软件开发工程师

题目是：小明手中有n块程木，并且小明知道每块积木的重量。现在小明希望将这些积木堆起来，要求是一块积木如果想放在另一块积木的上面，那么上面积木的重量减去下面积不的重量不能超过x(每堆中最下面的积木没有重量要求)。现在小明有一个机会，除了这n块积木，还可以获得k块任意重量的积木。小明希望将积木堆在一起，同时希望积不堆的数量越少越好，你能帮他找到最好的方案么? 输入是n，k，x，接着输入n个整数输出最小堆数

2 回复分享

发布于 2021-10-09 21:37

didiiiii

阿里巴巴_数据研发

直接大于三然后看任意的木块够不够就行，没有了就加一不用想的太复杂

2 回复分享

发布于 2021-10-09 23:47

丶先生

门头沟学院 Java

你这代码应该就是判断两个空隙是否大于x,大于就加一块积木直到k为0，但我感觉样例应该是没有考虑到两个空隙最大的距离>2*x的时候可以加多个积木

1 回复分享

发布于 2021-10-09 22:45

lky_super

新余学院 Java

感觉给的用例比较少，只考虑间隙里加一个积木就100了😅

1 回复分享

发布于 2021-10-09 23:52

牛客262307070号

哈尔滨工程大学 C++

我就直接原数据排序，然后求相邻差分，然后把大于x的差存下来，再给这些差排个序。设ans = 1，然后遍历差分数组，优先填补小的空隙，对每个空隙算一下需要填几个积木，就从k里面减去几，然后第i个空隙了，k不够减了，那后面的空隙就都不填了。ans直接加上(n-i)，输出。

点赞回复分享

发布于 2021-10-09 21:43

牛客353845269号

北京邮电大学算法工程师

我理解的是你最后一个条件不用判断k大于0吧因为从之前的条件来看最后一个条件你的k是可以满足gap的所以我觉得你的答案是对的呀😂

点赞回复分享

发布于 2021-10-09 22:13

八城十八

宜昌市夷陵中学测试工程师

先将数组排序，如果nums[i]-nums[i-1]-x＞0，就加入一个集合，然后集合排序，依次对集合中的数减x

点赞回复分享

发布于 2021-10-10 09:10

等offer的嘴哥

门头沟学院安全工程师

所以第一题是怎么做的？卡在91% 想不到临界值了。。

点赞回复分享

发布于 2021-10-10 11:34

Rhine_d

哈尔滨工程大学 C++

我是这样的。先是数字从小到大排序。要堆的数量少，就要求每个堆的数量尽量大。能分成的堆肯定是相邻连续的，不可能交叉跨着分配。这些堆的间隙肯定大于x，此时可以计算出每个间隙的最少填充数。例如 1 2 3 7 9，x=3。很显然间隙在3和7之间，(7-3)/x == 1，所以这个间隙用一个积木就可以填充。如果这个间隙的大小是x的整数倍，那么要求的数要-1。比如3与9差距为6, 6/3==2,但实际上只需要一个数字就可以填充这个间隙。把所有堆之间的间隙算出来，从小到大用k去减，尽量填充间隙。每填充一个间隙就减少一个堆，最后的结果就是一开始堆的数量 - 填充间隙的数量

点赞回复分享

发布于 2021-10-11 12:46