LeetCode刷題-猜數字大小

前言說明

演算法學習，日常刷題記錄，

題目連接

猜數字大小

題目內容

猜數字游戲的規則如下：

每輪游戲，我都會從1到n隨機選擇一個數字，請你猜選出的是哪個數字，

如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了，

你可以通過呼叫一個預先定義好的介面int guess(int num)來獲取猜測結果，回傳值一共有3種可能的情況(-1，1或0)：

-1：我選出的數字比你猜的數字小pick < num

1：我選出的數字比你猜的數字大pick > num

0：我選出的數字和你猜的數字一樣，恭喜！你猜對了！pick == num

回傳我選出的數字，

示例1:

輸入：n = 10, pick = 6

輸出：6

示例2:

輸入：n = 1, pick = 1

輸出：1

示例3:

輸入：n = 2, pick = 1

輸出：1

示例4:

輸入：n = 2, pick = 2

輸出：2

提示：

1 <= n <= 2^31 - 1

1 <= pick <= n

分析程序

看題可以得知用二分法查找，取1-n的中間值，呼叫guess函式和pick比較，

如果guess結果大于0，那么pick > num，選出的數字大于猜測的數字，所以選出的數字在區間[mid + 1, right]中，

如果guess結果小于0，那么pick < num，選出的數字小于猜測的數字，所以選出的數字在區間[left, mid - 1]中，

注意：這里的guess函式是兩數相反了，因為拿了pick作為比較基準，而不是傳遞進去num引數作為比較基準，所以和我們平時的認知是剛好相反的，

所以如下代碼：

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        // 定義左右指標，左指標初始為1，右指標初始為n
        int left = 1, right = n;

        // 計算中間指標
        int center = (left + right) / 2;

        // 計算猜測結果
        int result = guess(center);

        // 回圈直至guess的結果為0
        while (result != 0) {
            if (result > 0) {
                // 若是大于0，那么pick > num，選出的數字大于猜測的數字，所以選出的數字在區間[mid + 1, right]中
                left = center + 1;
            } else {
                // 若是小于0，那么pick < num，選出的數字小于猜測的數字，所以選出的數字在區間[left, mid - 1]中
                right = center - 1;
            }

            // 計算中間指標
            center = (left + right) / 2;;

            // 計算猜測結果
            result = guess(center);
        }

        // 當猜測結果為0時，即為二分查找到的數字
        return center;
    }
}

但是提交后提示運行時間超時：

是什么原因呢？我們可以看一下提示中n的范圍：

1 <= n <= 2^31 - 1

其實這里如果輸入2^31 - 1和1，一開始就已經整數溢位了，所以可以想象，還可能會出現2^31 - 1和一個二分查找時的中間指標相加再除以2，2^31 - 1已經是整數最大值了，若再加一個數，肯定就整數溢位了，導致二分查找時中間指標發生了跳躍變化，最終導致運行時間超時，我們計算中間指標如下：

// 計算中間指標
int center = (left + right) / 2;

錯誤的地方就在這里，這里可能會導致整數溢位，我們需要用其他方法來計算中間指標，可以改成如下：

// 計算中間指標，不用center = (left + right) / 2來計算，防止計算時溢位
int center = left + (right - left) / 2;

這樣一來，就不會出現整數溢位了，

解答代碼

所以需要考慮整數溢位的問題，解答代碼如下：

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        // 定義左右指標，左指標初始為1，右指標初始為n
        int left = 1, right = n;

        // 計算中間指標，不用center = (left + right) / 2來計算，防止計算時溢位
        int center = left + (right - left) / 2;

        // 計算猜測結果
        int result = guess(center);

        // 回圈直至guess的結果為0
        while (result != 0) {
            if (result > 0) {
                // 若是大于0，那么pick > num，選出的數字大于猜測的數字，所以選出的數字在區間[mid + 1, right]中
                left = center + 1;
            } else {
                // 若是小于0，那么pick < num，選出的數字小于猜測的數字，所以選出的數字在區間[left, mid - 1]中
                right = center - 1;
            }

            // 計算中間指標，不用center = (left + right) / 2來計算，防止計算時溢位
            center = left + (right - left) / 2;

            // 計算猜測結果
            result = guess(center);
        }

        // 當猜測結果為0時，即為二分查找到的數字
        return center;
    }
}

提交結果

執行用時0ms，時間擊敗100.00%的用戶，記憶體消耗35MB，空間擊敗84.51%的用戶，

原文鏈接

原文鏈接：猜數字大小