leetcode 雞蛋掉落java

Leetcode 雞蛋掉落

Leetcode 雞蛋掉落

你将獲得 K 個雞蛋，并可以使用一棟從 1 到 N 共有 N 層樓的建築。

每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。

你知道存在樓層 F ，滿足 0 <= F <= N 任何從高于 F 的樓層落下的雞蛋都會碎，從 F 樓層或比它低的樓層落下的雞蛋都不會破。

每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）并把它從任一樓層 X 扔下（滿足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

無論 F 的初始值如何，你确定 F 的值的最小移動次數是多少？

（其實這句話是說，在最壞的情況下，用盡量少的測試次數來找到F

示例 1：

輸入：K = 1, N = 2

輸出：2

解釋：

雞蛋從 1 樓掉落。如果它碎了，我們肯定知道 F = 0 。

否則，雞蛋從 2 樓掉落。如果它碎了，我們肯定知道 F = 1 。

如果它沒碎，那麼我們肯定知道 F = 2 。

是以，在最壞的情況下我們需要移動 2 次以确定 F 是多少。

示例 2：

輸入：K = 2, N = 6

輸出：3

示例 3：

輸入：K = 3, N = 14

輸出：4

提示：

1 <= K <= 100

1 <= N <= 10000

這道題還是很有意思的

初讀題會覺得就是一個簡單的數學奧賽問題，但是仔細讀題，發現問的是：

是以，在最壞的情況下我們需要移動 2 次以确定 F 是多少。

就是說在雞蛋都用完的情況下，怎麼移動的次數是最少的。

思路

聯想到二分法，比如說100層樓兩個蛋，第一個在50層扔了，如果沒摔碎，那麼在50之上繼續做。

如果摔碎了，就不能浪，必須從第一層一層層往上摔。

代碼

class Solution {
    /*
    若測試k次，能夠确定結果的最大測量樓層範圍為[0,dp[k][m]]，則稱dp[k][m]為最大測量樓層，則問題就是就是找到一個最小的m使得dp[k][m]>=N
    轉移方程dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1
    原因：假設第一次是在X層測試，
            若碎了，則F<X,需要測試它下面的樓層，蛋的數量和次數減少1，它的最大測量樓層為dp[k-1][m-1],還需要測試的樓層範圍為[0,X-1]
            若沒碎，則F>=X,需要測試它上面的樓層，蛋的數量不變，次數減少1，它的最大測量樓層為dp[k][m-1],還需要測試的樓層範圍為[X,dp[k][m]]
        若想達到最大測量層數，則分開的兩個區間的長度都應該達到最大測量樓層+1。即X-1 = dp[k-1][m-1]，dp[k][m] - X = dp[k][m-1]
        化去X，得到dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1
    注意左側都是m，右側都是m-1，可以隻使用一列存儲資料，K從大到小進行更新
    */
    public int superEggDrop(int K, int N) {
        int[] dp = new int[K+1]; //int型會自動初始化為0
        int m = 0;
        //從底層開始找
        while (dp[K]<N){
            m++;
            for (int i = K; i >= 1; i--)
            {
                dp[i] = dp[i] + dp[i-1] +1;
            }
        }
        return m;
    }
}
           

leetcode上最快的代碼:

class Solution {
    public int superEggDrop(int K, int N) {
       int[] d=new int[K+1];
        for (int i=0;i<d.length;i++){
            d[i]=1;
        }
        //當雞蛋數為0時，能确定的樓層數也就是0
        d[0]=0;
        //扔雞蛋的次數
        int x=1;
        //當K個雞蛋确定的樓層數大于等于N時，最少移動次數也就找到了
        while (d[K]<N){
            for (int i=K;i>=1;i--){
                //i代表雞蛋數
                d[i]=d[i]+d[i-1]+1;
            }
            x++;
        }
        return x;
    }
}