樓有 n 層高榛鼎，雞蛋若從 k 層或以上扔逃呼，就會碎。從 k 層以下扔者娱，就不會碎抡笼。
現(xiàn)在給兩個雞蛋，用最少的扔的次數(shù)找到 k黄鳍。返回最壞情況下次數(shù)推姻。
【要求】找到x層落下不會碎， x+1層落下會碎的臨界層所需要的最少嘗試次數(shù) r(r for result)
【假設(shè)】
- 只有1雞蛋測試框沟，需要從1層開始一層一層實驗藏古，最壞次數(shù)為k
- 如果有兩個雞蛋，第一個雞蛋用來試探, 只要它從 k 層樓扔下去沒碎, 則目標就在[k+1, n]之間了.但一旦運氣不好碎了, 對于已知的區(qū)間, 我們只能用剩下一個雞蛋從小到大一層層試,因為我們要保證策略必須成功, 不能冒險了.
"最壞情況下代價最小"這句話十分重要, 它反映了題目的重要數(shù)學結(jié)構(gòu):
我們可以把任何一種策略都看成一個決策樹,每一次扔雞蛋都會有兩個子節(jié)點, 對應(yīng)碎與不碎的情況下下一步應(yīng)該扔的樓層.
那么, 策略的一次執(zhí)行, 是樹中的一條從根往下走的路,當且僅當這條路上出現(xiàn)過形如 k 沒碎 與 k+1 碎了的一對節(jié)點時, 路停止, 當前節(jié)點不再擴展.
那么要找的是這么一棵樹, 使得所有路里最長者盡量短, 也即, 要找一個最矮的決策樹.
再看一個節(jié)點處, 選擇樓層時會發(fā)生什么.
容易看出, 選擇的樓層如果變高, 那么"碎子樹"高度不減, "不碎子樹"高度不增.
同樣的, 選擇的樓層變矮的話, "碎子樹"高度不增, "不碎子樹"高度不減.
這時候答案很明顯了: 為了使兩子樹中高度最大者盡量小, 我們的選擇應(yīng)當使兩子樹高度盡量接近.
最終希望的結(jié)果是, 整個二叉樹盡量像一個滿二叉樹. -
假設(shè)第一次在根節(jié)點上, 我們選擇扔k層, 其"碎子樹"的高度顯然是k - 1.
為了考慮不碎子樹的高度, 設(shè)不碎后第二次扔m層(顯然m > k ),
則這個新節(jié)點的碎子樹高度為 m - k - 1, 不碎子樹高度仍然未知,
但按照滿二叉樹的目標, 我們認為它與碎子樹相同或少1就好.
那么在根節(jié)點上的不碎子樹的高度就是m -k-1 + 1, 令它與碎子樹高度相同, 于是:
m - k - 1 + 1 = k - 1 => m = k + k - 1
也即, 如果第一次扔在k層, 第二次應(yīng)該高k-1 層, 這可以有直觀一點的理解:每扔一次, 就要更保守一些, 所以讓區(qū)間長度少1.[1, k) -> [k + 1, 2k - 1).用類似剛才的分析, 可以繼續(xù)得到, 下一次應(yīng)該增高k - 2, 再下一次應(yīng)該增高k - 3.
如果大樓100層, 考慮:
k + (k-1) + (k-2)+...+3+2+1 = (k+1)*k/2 =100 =>k ~= 14
所以第一次扔14層, 最壞需要14次(策略不唯一, 樹的葉子可以交換位置).
以上是數(shù)學做法...當然還有代碼做法....
設(shè)f(n, m)為n層樓, m個蛋所需次數(shù), 那么它成了一道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 最壞情況最少的次數(shù)
*/
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);
}
