美文网首页
[数组][二分]374. Guess Number Higher

[数组][二分]374. Guess Number Higher

作者: Reflection_ | 来源:发表于2017-11-01 13:45 被阅读0次

    题目:374. Guess Number Higher or Lower

    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.

    猜数字,给一个范围[1,n],猜了以后用 guess(int num)告诉是猜对,还是猜大/小了。

    二分查找。

    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int low = 1, high = n;
            int pick = low + (high - low) / 2;
            while(low <= high && guess(pick) != 0){
                if (guess(pick) == 1) low = pick +1;
                else high = pick -1;
                pick = low + (high - low) / 2;
            }
            return pick;
            
        }
    }
    

    减少调用guess(num)的次数,return那里返回low或high都可以,因为跳出循环的时候,low=high。

    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int low = 1, high = n;
            int pick;
            int tip;
            while(low < high){
                pick = low + (high - low) / 2;
                tip = guess(pick);
                if(tip == 0) return pick;
                else if (tip == 1) low = pick + 1;
                else high = pick - 1;
               
            }
            return high;//or low
            
        }
    }
    

    相关文章

      网友评论

          本文标题:[数组][二分]374. Guess Number Higher

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