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

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

3

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

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,其实不太理解题意。。。。

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

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

1

答案两个蛋100层楼预期结果14次?不懂了

确实很多用例都有问题

//要求最少尝试次数,反过来说,k个鸡蛋,假设x次尝试,最多能区分y层。由于x与y是正相关的,所以只要找到最小的x, 使 y >= n, 即可。
//k = 1, y_k1_xn = n
//----------------------------------------
//k = 2, y_k2_x1 = y_k1_x1 = 1
// 中间的1代表选为分界线的那层,往上鸡蛋数量不变,往下鸡蛋数量减1;上下都能最多尝试x-1次
// y_k2_x2 = y_k2_x1 + 1 + y_k1_x1 = 3
// y_k2_x3 = y_k2_x2 + 1 + y_k1_x2 = 6
// y_k2_x4 = y_k2_x3 + 1 + y_k1_x3 = 10
// .. .. ..
//----------------------------------------
//k = 3, y_k3_x1 = y_k1_x1 = 1
// y_k3_x2 = y_k2_x2 = 3
// y_k3_x3 = y_k3_x2 + 1 + y_k2_x2 = 7
// y_k3_x4 = y_k3_x3 + 1 + y_k2_x3 = 14
// y_k3_x5 = y_k3_x4 + 1 + y_k2_x4 = 25
// .. .. ..
//-----------------------------------------
//k = 4, y_k4_x1 = y_k1_x1 = 1
// y_k4_x2 = y_k2_x2 = 3
// y_k4_x3 = y_k3_x3 = 7
// y_k4_x4 = y_k4_x3 + 1 + y_k3_x3 = 15
// y_k4_x5 = y_k4_x4 + 1 + y_k3_x4 = 30
// y_k4_x6 = y_k4_x5 + 1 + y_k3_x5 = 56
// .. .. ..
//---------------------------------------------
// ......

// 写得有点冗余,提交是通过了
func superEggDrop(k int, n int) int {
if k == 1 {
return n
}

times := 1
y_k_t := maxEggDropLevel(k, times)
for {
    if y_k_t >= n {
        break
    }

    y_k_t += (1 + maxEggDropLevel(k-1, times))
    times++
}
return times

}

func maxEggDropLevel(eggNum int, times int) int {
if 0 == eggNum || 0 == times {
return 0
}

if 1 == eggNum {
    return times
}

if eggNum == times {
    return (1 << times) - 1
}

return maxEggDropLevel(eggNum, times-1) + 1 + maxEggDropLevel(eggNum-1, times-1)

}

蛋不是无穷的,不能一直让你仍啊,比如k=2,n=9, 你拿一个蛋在4层碎了,那么你又在2层也碎了,这时候你没蛋了,怎么试1层呢?

答案没错