楼有 n 层高，鸡蛋若从 k 层或以上扔，就会碎。从 k 层以下扔，就不会碎。
现在给两个鸡蛋，用最少的扔的次数找到 k。返回最坏情况下次数。
【要求】找到x层落下不会碎， x+1层落下会碎的临界层所需要的最少尝试次数 r(r for result)
【假设】
- 只有1鸡蛋测试，需要从1层开始一层一层实验，最坏次数为k
- 如果有两个鸡蛋，第一个鸡蛋用来试探, 只要它从 k 层楼扔下去没碎, 则目标就在[k+1, n]之间了.但一旦运气不好碎了, 对于已知的区间, 我们只能用剩下一个鸡蛋从小到大一层层试,因为我们要保证策略必须成功, 不能冒险了.
"最坏情况下代价最小"这句话十分重要, 它反映了题目的重要数学结构:
我们可以把任何一种策略都看成一个决策树,每一次扔鸡蛋都会有两个子节点, 对应碎与不碎的情况下下一步应该扔的楼层.
那么, 策略的一次执行, 是树中的一条从根往下走的路,当且仅当这条路上出现过形如 k 没碎 与 k+1 碎了的一对节点时, 路停止, 当前节点不再扩展.
那么要找的是这么一棵树, 使得所有路里最长者尽量短, 也即, 要找一个最矮的决策树.
再看一个节点处, 选择楼层时会发生什么.
容易看出, 选择的楼层如果变高, 那么"碎子树"高度不减, "不碎子树"高度不增.
同样的, 选择的楼层变矮的话, "碎子树"高度不增, "不碎子树"高度不减.
这时候答案很明显了: 为了使两子树中高度最大者尽量小, 我们的选择应当使两子树高度尽量接近.
最终希望的结果是, 整个二叉树尽量像一个满二叉树. -
假设第一次在根节点上, 我们选择扔k层, 其"碎子树"的高度显然是k - 1.
为了考虑不碎子树的高度, 设不碎后第二次扔m层(显然m > k ),
则这个新节点的碎子树高度为 m - k - 1, 不碎子树高度仍然未知,
但按照满二叉树的目标, 我们认为它与碎子树相同或少1就好.
那么在根节点上的不碎子树的高度就是m -k-1 + 1, 令它与碎子树高度相同, 于是:
m - k - 1 + 1 = k - 1 => m = k + k - 1
也即, 如果第一次扔在k层, 第二次应该高k-1 层, 这可以有直观一点的理解:每扔一次, 就要更保守一些, 所以让区间长度少1.[1, k) -> [k + 1, 2k - 1).用类似刚才的分析, 可以继续得到, 下一次应该增高k - 2, 再下一次应该增高k - 3.
如果大楼100层, 考虑:
k + (k-1) + (k-2)+...+3+2+1 = (k+1)*k/2 =100 =>k ~= 14
所以第一次扔14层, 最坏需要14次(策略不唯一, 树的叶子可以交换位置).
以上是数学做法...当然还有代码做法....
设f(n, m)为n层楼, m个蛋所需次数, 那么它成了一道DP题..
f(0,m) = 0,(m>=1)
f(h,1) = n,(h>=1)
f(h,m) = (1->k->n)min{max{f(k-1,m-1), f(h-k, m)}} + 1
即：
f(h,m) = (1->k->n)min{max{f(k-1,m-1), f(h-k, m)}} + 1.png
public class Solution {
/**
*
* @param n 楼层
* @return 最坏情况最少的次数
*/
public int dropEggs(int n){
long k = 0;
for (int i = 1; ; ++i) {
k += (long)i;
if (k >= (long)n)
return i;
}
}
另外一种暴力方法：
public int dropEggs(int n) {
long x = n;
double x1 = (Math.sqrt(x * 8 + 1) - 1) / 2;
return (int)Math.ceil(x1);
}
网友评论