鸡蛋掉落-两枚鸡蛋

难度: Medium

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：

输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

提示：

1 <= n <= 1000

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def twoEggDrop(self, n: int) -> int:
       
        # 使用数学方法解决问题
        # 解不等式 x * (x + 1) / 2 >= n
        return math.ceil((-1 + math.sqrt(1 + 8 * n)) / 2)

Explain

题解利用数学公式来解决这个问题。首先，设x是我们需要的最小操作次数，其中第一枚鸡蛋以一个确定的步长序列（如x, x-1, x-2, ..., 1）来丢。这样，每丢一次，我们能检查的楼层数累积为1到x的和，即x*(x+1)/2。因此，为了覆盖所有楼层，需要满足x*(x+1)/2 >= n。通过解这个不等式，我们能找到满足条件的最小x值。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def twoEggDrop(self, n: int) -> int:
       # 使用数学方法解决问题
       # 解不等式 x * (x + 1) / 2 >= n，找到最小的x使得该式成立
       # 使用数学公式计算 x 的值
       return math.ceil((-1 + math.sqrt(1 + 8 * n)) / 2) # 计算并返回所需的最小操作次数

Explore

这个公式x*(x+1)/2是等差数列的求和公式，其中x代表了第一枚鸡蛋投掷的次数，且每次投掷的楼层高度递减（从x开始递减到1）。该公式的求和结果代表了在x次操作中最多能检查的楼层数。因此，这个公式的含义是，通过x次操作，最多能覆盖的楼层总数。要确保能检查所有楼层，就需要这个总数大于或等于楼的总层数n。

从x层开始递减地扔鸡蛋是为了最优化最坏情况下的投掷次数。如果从较高楼层开始，当第一个鸡蛋在较低的楼层破裂时，剩余的尝试次数和楼层数量能够更好地匹配，减少不必要的重复检查。递减方式可以在第一个鸡蛋破裂后，用第二个鸡蛋在较小的区间内逐层检查，从而更快找到临界楼层。递增或不规则方式会导致在第一个鸡蛋破裂后，可能剩下较多楼层需要逐一检查，从而增加总的尝试次数。

math.sqrt函数用于计算方程x*(x+1)/2 >= n的正根。方程求解后形成的一元二次方程是x^2 + x - 2n = 0。使用求根公式得到x = (-1 + sqrt(1 + 8n))/2。这里sqrt函数计算的是1+8n的平方根，确保得到的x是实数。ceil函数确保x向上取整，因为x可能是非整数而楼层数必须是整数。因此，这种方法能在理论上保证找到满足条件的最小整数x。

这种方法在任何正整数n的值上都是有效的。无论n的大小如何，x*(x+1)/2的形式能够覆盖从1层到任意高的楼层。由于每次增加x会让总楼层数以二次方的速度增长，因此对于任何给定的n，总能找到一个x使得x*(x+1)/2 >= n。这保证了算法的普适性和可靠性。