美文网首页
374. Guess Number Higher or Lowe

374. Guess Number Higher or Lowe

作者: 这就是一个随意的名字 | 来源:发表于2017-07-30 10:46 被阅读0次

    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.
    猜数游戏,要求返回指定的数字,可调用guess(n)查看所猜的数字n与指定数字的大小关系。


    思路
    二分查找

    // Forward declaration of guess API.
    // @param num, your guess
    // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
    int guess(int num);
    
    class Solution {
    public:
        int guessNumber(int n) {
            int low=1;
            while(low<=n){
                int mid=low+(n-low)/2;       //防止溢出
                int res=guess(mid);
                if(res==0)  return mid;
                else if(res==-1)    n=mid-1;
                else    low=mid+1;
            }
            return -1;
        }
    };
    

    相关文章

      网友评论

          本文标题:374. Guess Number Higher or Lowe

          本文链接:https://www.haomeiwen.com/subject/rjmhlxtx.html