LeetCode算法题-Guess Number Higher or Lower(Java实现)

LeetCode算法题-Guess Number Higher or Lower(Java实现)

这是悦乐书的第211次更新,第224篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第79题(顺位题号是374)。我们正在玩数字游戏。 游戏如下:我从1到n中选择一个数字。 你必须猜测我选择了哪个数字。每次你猜错了,我都会告诉你这个数字是高还是低。您调用预定义的API guess(int num),它返回3个可能的结果(-1,1或0):

-1:我的数字较低
1:我的数字更高
0:猜对了!

例如:

输入:n = 10,pick = 6
输出:6

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

暴力解法,直接使用for循环,依次调用guess(int num)方法,直到猜对了为止。但是此解法超时。

此解法时间复杂度是O(n),空间复杂度是O(1)。

public int guessNumber(int n) {
    for (int i=1; i<n; i++) {
        if (guess(i) == 0) {
            return i;
        }
    }
    return n;
}


03 第二种解法

使用二分查找法来判断,在求中间数的时候,需要换种写法mid = (high-low)/2 + low;或者将类型换成long,这样做是为了避免溢出。

此解法的时间复杂度是O(log n),空间复杂度是O(1)。

public int guessNumber2(int n) {
    int low = 1;
    int high = n;
    while (low <= high) {
        int mid = (high-low)/2 + low;
        int result = guess(mid);
        if (result == 0) {
            return mid;
        } else if(result == 1) {
            low = mid + 1;
        } else if(result == -1) {
            high = mid - 1;
        }
    }
    return -1;
}


04 小结

算法专题目前已连续日更超过两个月,算法题文章79+篇,