【leetcode73】经典算法-Guess Number Higher or Lower

ゝ一世哀愁。 2022-04-11 06:30 95阅读 0赞

# 题目描述： #

## 从1～n中，随便的拿出一个数字，你来猜测。 ##

## 提示 ##

提供一个guess(int num)的api，针对猜测的数字，返回三个数值。0，-1,1

*  0;猜中返回num
 *  \-1：比猜测的数值小
 *  1：比猜测的数值大

## 例如： ##

n = 10, I pick 6.

Return 6.

# 原文描述： #

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’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

\-1 : My number is lower  
1 : My number is higher  
0 : Congrats! You got it!

## Example: ##

n = 10, I pick 6.

Return 6.

# 思路分析： #

*  明显是二分法的应用，关于二分法，看我之前的一片博客，讲的比较详细，链接如下：  
    [Java语言实现二分法][Java]

# 代码： #

/* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    
    public class Solution extends GuessGame {
        public int guessNumber(int n) {
             int L = 1,R = n;
            while(L <= R){
                int mid = L + ((R - L) >> 1);
                int res = guess(mid);
                if(res == 0) return mid;
                else if(res == 1)  L = mid + 1;
                else R = mid - 1;
            }
            return L;
        }
    }

# 更多leetcode题目，请看我的leetcode专栏。链接如下： #

[leetcode专栏][leetcode]

# #

[Java]: http://blog.csdn.net/lpjishu/article/details/50823154
[leetcode]: http://blog.csdn.net/column/details/fengsheng.html