关于java:LeetCode374猜数字大小

29次阅读

共计 1200 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容：猜数字游戏的规定如下：

每轮游戏，我都会从 1 到 n 随机抉择一个数字。请你猜选出的是哪个数字。

如果你猜错了，我会通知你，你猜想的数字比我选出的数字是大了还是小了。

你能够通过调用一个事后定义好的接口 int guess(int num) 来获取猜想后果，返回值一共有 3 种可能的状况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num

1：我选出的数字比你猜的数字大 pick > num

0：我选出的数字和你猜的数字一样。祝贺！你猜对了！pick == num

返回我选出的数字。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分查找法

典型的二分查找问题，首先 low 初始值为 1，high 初始值为 num，二分查找过程如下：

循环的前提是 low 不大于 high；

而后 mid 的值为 low + (high - low) / 2，而后调用guess(num) 办法进行判断；

如果返回 -1，则 high 的值置为mid - 1，而后进行下一轮解决；

如果返回 1，则 low 的值置为mid + 1，而后进行下一轮解决；

如果返回 0，则返回 mid 值，该值即为选出的数字。

public class LeetCode_374 extends GuessGame {
    /**
     * 二分查找
     *
     * @param num
     * @return
     */
    public static int guessNumber(int num) {
        int low = 1, high = num;
        while (low <= high) {int mid = low + (high - low) / 2;
            if (guess(mid) == -1) {high = mid - 1;} else if (guess(mid) == 0) {return mid;} else if (guess(mid) == 1) {low = mid + 1;}
        }
        return -1;
    }

    public static void main(String[] args) {System.out.println(guessNumber(2126753390));
    }
}


class GuessGame {
    /**
     * 假如 1702766719 是最终的后果
     * Forward declaration of guess API.
     *
     * @param num your guess
     * @return -1 if num is lower than the guess number
     * 1 if num is higher than the guess number
     * otherwise return 0
     */
    public static int guess(int num) {if (num > 1702766719) {return -1;} else if (num == 1702766719) {return 0;} else {return 1;}
    }
}