class Solution {
public:
int twoEggDrop(int n) {
}
};
1884. 鸡蛋掉落-两枚鸡蛋
给你 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原站题解
java 解法, 执行用时: 46 ms, 内存消耗: 39.3 MB, 提交时间: 2024-10-13 09:27:01
class Solution {
private static final int[] f = new int[1001];
static {
for (int i = 1; i < f.length; i++) {
f[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
f[i] = Math.min(f[i], Math.max(j, f[i - j] + 1));
}
}
}
public int twoEggDrop(int n) {
return f[n];
}
public int twoEggDrop2(int n) {
return (int) Math.ceil(Math.sqrt(n * 8 + 1)) / 2;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2024-10-13 09:26:22
var f [1001]int
func init() {
for i := 1; i < len(f); i++ {
f[i] = math.MaxInt
for j := 1; j <= i; j++ {
f[i] = min(f[i], max(j, f[i-j]+1))
}
}
}
func twoEggDrop(n int) int {
return f[n]
}
func twoEggDrop2(n int) int {
return int(math.Ceil((math.Sqrt(float64(n*8+1)) - 1) / 2))
}
python3 解法, 执行用时: 3224 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-21 16:46:15
class Solution:
def twoEggDrop(self, n: int) -> int:
dp = [0] * (n+1)
for i in range(1, n+1):
dp[i] = float('inf')
for j in range(1, i+1):
dp[i] = min(max(dp[i - j] + 1, j), dp[i]) # dp[i - j] + 1表示第一个鸡蛋没碎的次数，j表示第一个鸡蛋碎了的次数
return dp[n]
python3 解法, 执行用时: 4012 ms, 内存消耗: 15 MB, 提交时间: 2022-11-21 16:40:15
class Solution:
def twoEggDrop(self, n: int) -> int:
'''
dp[i][0]表示只有一颗蛋去检测i层楼需要的最小次数；
dp[i][1]表示有两颗蛋去检测i层楼需要的最小次数。
'''
dp = [[float('inf')]*2 for _ in range(n+1)]
dp[0] = [0, 0]
for i in range(1, n+1):
dp[i][0] = i
for k in range(1,i+1):
dp[i][1] = min(dp[i][1], max(dp[k-1][0], dp[i-k][1])+1)
return dp[n][1]
python3 解法, 执行用时: 4040 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-21 16:38:12
class Solution:
def twoEggDrop(self, n: int) -> int:
INF = 10 ** 3
dp = [[INF for _ in range(n + 1)] for _ in range(3)]
for i in range(1, n + 1):
dp[1][i] = i #如果只有一个鸡蛋，只能从底往上一层一层地试
dp[1][0] = 0 #1个鸡蛋，0层，不需要步骤
dp[2][0] = 0 #2个鸡蛋，0层，
for up in range(1, n + 1):
for down in range(1, up + 1):
#----鸡蛋碎-->1个鸡蛋检验down - 1层
a1 = dp[1][down - 1]
#----鸡蛋没碎-->2个鸡蛋检验up - down层
a2 = dp[2][up - down]
#----要保证一定可以，所以要取max(a1, a2)
dp[2][up] = min(dp[2][up], max(a1, a2) + 1)
return dp[2][n]
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-21 16:36:53
# 公式递推版
class Solution:
def twoEggDrop(self, n: int) -> int:
res = 0
while res*(res+1)//2<n:
res += 1
return res
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-21 16:26:38
class Solution:
def twoEggDrop(self, n: int) -> int:
'''
找规律
1 + 2 + 3 + 4 + .... + x >= n
求出 x
'''
from math import ceil, sqrt
return int(ceil((-1 + sqrt(1+8*n))/2))