LeetCode-374. Guess Number Higher or Lower

LeetCode-374. Guess Number Higher or Lower

難度: easy

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

  • -1: Your guess is higher than the number I picked (i.e. num > pick)..
  • 1: Your guess is lower than the number I picked (i.e. num < pick).
  • 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

 

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Constraints:

  • 1 <= n <= 231 - 1.
  • 1 <= pick <= n

解題流程

  1. 先看懂題目想描述甚麼情境
  2. 開始想像程式運作該經過哪些流程
  3. 將經過的流程所需的判斷跟細節列出
  4. 實作列出的流程

先看懂題目想描述甚麼情境

開始想像程式運作該經過哪些流程

將經過的流程所需的判斷跟細節列出

實作列出的流程

typescript

二分搜索


/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return       -1 if num is higher than the picked number
 *                1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */

function guessNumber(n: number): number {
    let low = 1;
    let high = n;
    while(low <= high) {
        let mid = Math.ceil((high + low)/2);
        const guessedNum = guess(mid);
        if(guessedNum === 0) {
            return mid;
        } else if(guessedNum === 1){
            low = mid + 1;
        } else if(guessedNum === -1) {
           high = mid - 1; 
        }
    }
    return 0;
};

感謝閱讀,如果有錯誤或是講得不清楚的部分,再請留言指教

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *