鸡蛋掉落 | 前端芯事

题目

两枚鸡蛋是不定鸡蛋的特殊情况，力扣上通过率却相差很多，所以我们着重掌握不定鸡蛋的情况即可，但是两枚鸡蛋容易讲解。

无限鸡蛋

如果有无限个鸡蛋，那么这道题非常像我们小时候玩的猜数字游戏，我们可以采用二分法，某个楼层知道碎或不碎后，我们可以每次将规模减少一般，所以我们至多需要 2^n === 100，n 的结果的鸡蛋即可。

值得吐槽一下的是，这道题的标签上带有“二分查找”的提示，我错误地想成，如果只剩最后一个鸡蛋必须一层一层地实验了，但是多出来的鸡蛋可以采用上面的二分法。实际上，如果两枚鸡蛋，第一个枚放在 50 楼，如果它碎了，那个还需要从 1-49 层扔，最坏情况需要扔到 49 层，共 50 次，远大于题目二的示例告诉我们的 14 次。

正确的扔法

我们可以一定间隔地扔，比如先在第 10 层扔，如果答案是 9，我们共计需要扔 10 次。如果答案是 19，我们在第 20 层扔，加上第 10 层扔的哪一次，我们需要扔 11 次。

如此往复，我们会发现，随着往后我们的次数会增加，但是如果答案是比较靠后的，最后的次数并不是 14，但是非常接近了。

实际上，我们真正的扔法是递减的间隔，我们假设第一个间隔是 14，第二个间隔是 13，在一枚鸡蛋依次在间隔上实验是否会碎的次数会减少，正好抵消我们第一枚鸡蛋不碎时向上确认一个间隔的那一次操作。这样次数就是相对稳定的。

代码

我们可以写出我们的第一版代码：

typescript

function superEggDrop(k: number, n: number): number {
  if (k === 1) {
    return n;
  }
  if (k === 0) {
    return Infinity;
  }
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  let min = n;
  for (let i=1; i<=n; i++) {
    let ans1 = superEggDrop(k-1, i-1);
    let ans2 = superEggDrop(k, n - i);
    min = Math.min(min, 1 + Math.max(ans1, ans2));
  }

  return min
};


function twoEggDrop(n: number): number {
  return superEggDrop(2, n);
};

两枚鸡蛋我们直接带入即可。

由于们有递归调用我们的方法，我们不妨处理一下非常临界的情况，比如仅一枚鸡蛋需要 n 次，没有鸡蛋我们无法确认次数等。

我们并不清楚间隔是多少合适，所以我们每一层都去实验，答案取最小值。

对于每一次扔后的结果，会产生两种情况:

鸡蛋碎了，那么鸡蛋个数减少，我们确认了楼层在 i 层之前。
鸡蛋没碎，鸡蛋个数不变，但是楼层的返回减少了，答案在 i + 1 至 n 之间，实际上问题的规模减少了，我们不需要关心第几层，只需要关心有多少层即可，所以我们子问题传入 n - i 即可。

提交后发现，这样执行是会超时的，由于我们用到了递归，我们不妨使用记忆化来尝试加速。

typescript

const memo = new Map<string, number>()

function superEggDrop(k: number, n: number): number {
  if (memo.has(`${k},${n}`)) {
    return memo.get(`${k},${n}`)
  }

  if (k === 1) {
    return n;
  }
  if (k === 0) {
    return Infinity;
  }
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  let min = n;
  for (let i=1; i<=n; i++) {
    let ans1 = superEggDrop(k-1, i-1);
    let ans2 = superEggDrop(k, n - i);
    min = Math.min(min, 1 + Math.max(ans1, ans2));
  }

  memo.set(`${k},${n}`, min);

  return min
};


function twoEggDrop(n: number): number {
  return superEggDrop(2, n);
};

此时，两枚鸡蛋的题目能够通过了，但是另一题依然通不过。

观察发现，我们的循环求解的 ans1 和 ans2 一个随 i 增大而增大，另一个随之增大而减小，我们可以通过二分法来加速，这也是为什么这道题被打上二分搜索标签的原因。

typescript

const memo = new Map<string, number>()

function superEggDrop(k: number, n: number): number {
  if (memo.has(`${k},${n}`)) {
    return memo.get(`${k},${n}`)
  }

  if (k === 1) {
    return n;
  }
  if (k === 0) {
    return Infinity;
  }
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  let min = n;
  let low = 1;
  let high = n;
  while (low + 1 <= high) {
    let i = (low + high) >> 1;
    let ans1 = superEggDrop(k-1, i-1);
    let ans2 = superEggDrop(k, n - i);

    if (ans1 < ans2) {
      low = i + 1;
    } else if (ans1 > ans2) {
      high = i - 1;
    } else {
      low = high = i;
    }
  }

  let ans1 = Math.max(superEggDrop(k-1, low-1), superEggDrop(k, n - low));
  let ans2 = Math.max(superEggDrop(k-1, high-1), superEggDrop(k, n - high));

  min = 1 + Math.max(ans2, ans1);

  memo.set(`${k},${n}`, min);

  return min
};


function twoEggDrop(n: number): number {
  return superEggDrop(2, n);
};

我们通过二分确定了第一次从那里扔，一般情况下我们得到的 low 和 high 不是同一个，所以我们均对其再次求解，并取其较大值。

总结

这道题是曾经某司经典的算法面试题，如果真的没有刷过这道题，除非是特别天才，很难想到正确的扔法。

即使想到了正确的扔法，题目中还需要分别应用记忆化搜索和二分搜索来优化，难度算是非常大的。

题目 ​

无限鸡蛋 ​

正确的扔法 ​

代码 ​

总结 ​

题目

无限鸡蛋

正确的扔法

代码

总结