Cracking Coding Interview - 6.8 the Egg Drop Problem

The Egg Drop Problem: There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it’s dropped from any floor below, it will not break. You’re given two eggs. Find N, while minimizing the number of drops for the worst case.

Hints: #156, #233, #294, #333, #357, #374, #395

解法1（错误）

有个楼一共有100层，已知当鸡蛋在>= N层往下丢的时候鸡蛋会破，在 < N层往下丢丢时候鸡蛋不会破。现在给你2鸡蛋，求最少丢几次能够知道这个N是几。

因为有100层，因此每一层的概率都是相同的：0.01

也就是N在[1, 50]的概率是0.5，在[51, 100]的概率也是0.5，我们可以参考二分查找的办法来做：

所以我们要在(1 + 100) / 2 = 50层丢

• 如果破了，那么我们得从1层开始丢，直到丢破了为止。

• 如果没破

  • 那么我们得在(51 + 100) / 2= 75层丢
  • 如果破了就从51层开始丢，知道丢破为止。
  • 如果没破
    • 就在(76 + 100) / 2 = 88层丢
    • 如果破了，则从76层开始丢，直到丢破为止。
    • 如果没破：。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int findFloor(int start, int end) {
  int mid = (start + end) / 2;
  boolean broken = drop(mid);
  if (broken) {
    // 鸡蛋破了，则从start开始一层一层找
    return findFloorOneByOne(start);
  }
  // 鸡蛋没破，在下一个区间找
  return findFloor(mid + 1, end);
}

// 暴力一层一层往上找
public int findFloorOneByOne(int start) {
  int i = start;
  while (!drop(i)) {
    i++;
  }
  return i;
}

这个解法最坏情况下要丢几次呢？50次。

解法2（错误）

如果我们把东西分成长度为10的若干段，那么我们这么找：

1

1...10...20...30...40...50...60...70...80...90...100

1. 在10层丢，如果破了，在1～9层丢，总共丢10次
2. 在20层丢，如果破了，在11～19层丢，总共丢11次
3. 在30层丢，如果破了，在21～29层丢，总共丢12次
4. 。。。
5. 在90层丢，如果破了，在81～89层丢，总共丢18次
6. 最后[91, 100]区间里不需要丢10次，我们手里还有两个蛋，可以再分割成小区间，因此肯定少于10次。

所以最坏情况下丢18次。

公式是：f(n) = (100/n - 1) + (n - 1) = n + 100/n - 2

f(n)是最坏情况丢的次数，(100/n - 1)是最多丢多少次确定区间，(n - 1)是在区间内最多丢多少次确定楼层，n是区间大小。

后面解不出来了。

解法2（正确）

上面的最坏情况是随着丢的次数增加而增加的，可以表现为 丢egg1的次数 + 丢egg2的次数。因为采取的是固定宽度，因此丢egg2的次数是固定的，而丢egg1的次数又是递增的，因此总体丢的次数是递增的。

想一个办法弄让总丢次数恒定。比如当多丢一次egg1时，能够少丢一次egg2。

如果我们把楼层间隔设置为X，那么就意味着：

1. egg1丢一次，如果破了，egg2丢X - 1次。如果没破看下面：
2. egg1再丢一次，如果破了，egg2丢X - 2次。如果没破看下面：
3. egg1再丢一次，如果破了，egg2丢X - 3次。如果没破看下面：

那么就是说，egg1从X层开始丢、加X-1层、加X - 2层，直到丢到100层。

1
2
3

X + (X - 1) + (x - 2) + ... + 1 = 100
                   X(X + 1) / 2 = 100
                              X = 13.65

因为X取整数，可以是14或者13，看选哪一个。

如果是14，那么是14 + 13 + 12 + 11 + ... + 4=99，看最后一个4，这里一共是11次丢egg1，在加上4-1次丢egg2，总共丢14次。如果答案是100层，那么丢12次就行了。

如果是13，那么是13 + 12 + 11 + 10 + ... + 1 = 91，如果答案是100，那么要丢13次egg1再加9次egg2，总共丢22次。

所以X是14，所以总丢次数是14次。