讨论/《算法面试题汇总》 - 鸡蛋掉落/
《算法面试题汇总》 - 鸡蛋掉落
共 22 个回复

转载大神的方法https://blog.csdn.net/haut_ykc/article/details/105447682
希望对看不懂的人有帮助

2

class Solution {
public:
int superEggDrop(int K, int N) {
int remainTestCount = 1;//穷举移动次数(测试的次数)
while (getConfirmFloors(remainTestCount, K) < N){
++remainTestCount;
}
return remainTestCount;
}
//在remainTestCount个测试机会(扔鸡蛋的机会 或者移动的次数),eggsCount个鸡蛋可以确定的楼层数量
int getConfirmFloors(int remainTestCount, int eggsCount){
if (remainTestCount == 1 || eggsCount == 1){
//如果remainTestCount == 1你只能移动一次,则你只能确定第一楼是否,也就是说鸡蛋只能放在第一楼,如果碎了,则F == 0,如果鸡蛋没碎,则F == 1
//如果eggsCount == 1鸡蛋数为1,它碎了你就没有鸡蛋了,为了保险,你只能从第一楼开始逐渐往上测试,如果第一楼碎了(同上),第一楼没碎继续测第i楼,蛋式你不可能无限制的测试,因为你只能测试remainTestCount次
return remainTestCount;
}
return getConfirmFloors(remainTestCount - 1, eggsCount - 1) + 1 + getConfirmFloors(remainTestCount - 1, eggsCount);
}
};

2

本来的理解k个鸡蛋,n层楼是先从中间层h=n/2试起,若鸡蛋碎了,则剩下k-1个蛋走底下的1~h-1层,若鸡蛋没碎,则剩下k个蛋走上面h+1~n层楼,那么最坏的情况需要移动 1 + max{f(k-1,h-1), f(k, n-h-1)},但是很多用例都不通过。比如k=2,n=9时代码结果5,真实结果4,其实不太理解题意。。。。

1

因为要确切知道F值,计算最坏情况下的次数

1

答案没错

看我的回复

问题在于,一次运行二分法并不是最小值。所以需要先用二分法找到交点的左右两个临近点,再从临近点里选择最小值。

我和你这个是一样的,也是很多不过。

image.png
谁能帮忙解释一下为什么输入2,9时的预期结果是4?

鸡蛋1个,就从0楼~n楼慢慢扔
鸡蛋2~m个,就用m-1个先做二分搜索,如果m-1个内使用a(a<=m-1)个完成了查找,那就等于m-1;如果没有找到,那就剩下的从最小楼层一层一层往上扔