2021-05-23 16:42 .NET

关注

2021华为社招机试--叠积木

积木宽高相等，长度不等，每层只能放一个或拼接多个积木，每层长度相等，求最大层数，最少2层。

输入：给定积木的长度，以空格分隔，例如:3 6 6 3。

输出：如果可以搭建，返回最大层数，如果不可以返回-1。

例1：

输入：3 6 6 3

输出：3

例2：

输入：3 5

输出：-1

理解：需要判断所有积木长度和是否是素数，素数无法搭建；

且最大公约数小于积木单块最大长度，无法搭建；

剩下的怎么组合就完全没有思路了，大佬们帮忙解个惑！！！😆😆😆

#互联网求职##华为#

全部评论

推荐最新楼层

Moonstrucks

大数据开发工程师

参考力扣698题，不要谢我，其余的也就是先求和从sum/max 便利到sum/2 ，每次进行一次判断，贪心策略是遇到第一个就输出，便利完还没有就返回-1

送花回复

发布于 2022-04-15 00:07

凤凰传奇

Java

提供一种java解法： 1、计算积木总和，设为sum 2、最大可能层数为积木数量m（每个积木长度相同的情况)，依次递减，最小层数为2 3、计算层数floor = sum % m，floor不为0，说明该层数无效 4、经过第2、3步获取到有效可能层数的合集floorList 5、遍历floorList（从大到小），获取每层平均长度avtLength = sum / i 6、判断avtLength 是否有效，如有效则输出该长度对应层数i，全部无效输出-1 7、源码：http://kill.cn/1/%E5%8D%8E%E4%B8%BA%E6%9C%BA%E8%AF%95%E5%A0%86%E7%A7%AF%E6%9C%A8.html

送花回复

发布于 2022-04-09 09:34

滴滴

校招火热招聘中

官网直投

xknowledge

Java

不好意思，回答错误。。。应该是动态规划。你说的素数是对的✧٩(ˊωˋ*)و✧

送花回复

发布于 2021-05-26 20:22

还好。201906120052763

Java

想法： 1.是否素数，否则返回 2.求出素数的所有公约数，公约数从所给积木的最大开始遍历，依次使用贪心算法进行组合看是否满足 eg:3 6 6 3 sum=18，公约数集合为：1，2，3，6，9（最小2层，所以公约数集合遍历到一半就行了）所以遍历的集合为6，9 依次看是否满足，满足就返回，此例中6满足，那么返回18/6=3

送花回复

发布于 2021-06-09 12:07

牛客686485025号

测试开发

我的思路是拿到长度之和p，进行求余数判断，余数为零，则可能搭建成功，层数m放入列表，排个序，从最大开始判断，p/m是否等于数组中长度t，直到找到等于则说明一定可以成功，打印当前列表值则为最大层数（判断就是一个循环，p/m=p/m—t）

送花回复

发布于 2021-07-02 02:17

大风吹201905241558291

这题100分还是200分？

送花回复

发布于 2021-05-25 18:47

H叔

算法工程师

话说机试的时候如果有哪个库函数忘记用法了可以上网百度吗？

送花回复

发布于 2021-05-25 21:50

xknowledge

Java

200分。。。贪婪算法吧，，第一次用牛客网，没时间了😂

送花回复

发布于 2021-05-26 19:02

xknowledge

Java

求什么素数啊，第一步，找出最长积木，把它设置为墙的宽度。第二步，迭代所有积木组成的数据集。如果积木长度等于墙的宽度，墙的层数加一，并移除该积木；如果积木长度不等于墙的宽度，那继续从剩余的积木中消除可以和它互补等于墙宽度的若干个积木，如果有，那么墙的层数+1，移除这些积木；如果找不到这块短积木的“补集”，直接返回-1，表示无法砌成完美的墙。第三步，如果没有返回-1 。继续执行第二步。大致的思路是这样的。

送花回复

发布于 2021-05-26 19:08

缘来是你好吧

Java

可以用一个笨办法,那就是组合所有可能的每层长度,然后按照这个长度看看能够搭建多少层.求最大值,可能通过不了100%,但是60%应该没问题

送花回复

发布于 2021-07-29 14:47

凤凰传奇

Java

再补充下，第6步为关键步骤，具体判断avtLength是否有效思路如下： 1、从积木集合giftList中任取1个元素，值等于avtLength则从giftList中去掉该元素 2、从积木集合giftList中任取2个元素，和等于avtLength则从giftList中去掉该2个元素 3、依次类推，任取元素最大值为max = giftList.size() - 1，因为最小层数为2 4、当取元素完毕，判断giftList是否为空，为空则说明avtLength有效，不为空说明无效 5、主要算法：集合中任取n个元素 #华为机试

送花回复

发布于 2022-04-09 09:43

清风抚山岗

Java

没有读懂题目，哪位给解释下，谢谢

送花回复

发布于 2021-06-02 18:31

仰望上帝

Python

积木宽高相等，长度不等，每层只能放一个或拼接多个积木，每层长度相等，求最大层数，最少2层。输入：给定积木的长度，以空格分隔，例如:3 6 6 3。输出：如果可以搭建，返回最大层数，如果不可以返回-1。例1：输入：3 6 6 3 输出：3 例2：输入：3 5 输出：-1

送花回复

发布于 2021-09-28 15:52