[Leetcode]374. Guess Number Higher or Lower

https://leetcode.com/problems/guess-number-higher-or-lower/description/

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 (-11, 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 function用来干啥的呢。

先二分搜索试试看。这个二分跟普通的二分就一点不一样,不是让你二分search 而是二分看是什么数,换汤不换药,以前是已知数让你看在不在,现在是他告诉你大小,你自己缩小范围,信息点给的是一样的,guess(int num)这个函数来指示大了还是小了,我们好挪动范围。这道题最神奇的地方在于,题目对-1, 和1这个返回值 的理解。我一开始就理解反了,真么着都不对,心塞塞,后来调过来就好了,呵呵。还有一个不能饶恕的错误,第一次提交竟然因为没检查low 比 high小 而Stack Overflow 了!不能再犯!

但是感觉狗家给这个题不是很正常,边界条件要问好,估计这才是重点。

AC Solution, Recursion:
public class Solution extends GuessGame {
    int result = 0;
    public int guessNumber(int n) {    
        return helper(1, n);
    }
    public int helper(int low, int high){
        if(low >= high){
            return low;
        }
        int mid = low + (high - low) / 2;
        if(guess(mid) == 0){
            return mid;
        }
        else if(guess(mid) == 1){
            return helper(mid+1, high);
        }
        else{
            return helper(low, mid-1);
        }
    }
}

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

Comments

Popular posts from this blog

LeetCode] 644.Maximum Average Subarray II

[Leetcode]375. Guess Number Higher or Lower II

[Leetcode] 643. Maximum Average Subarray I