JS Leetcode 374. 猜数字大小 题解分析

壹 ? 引

本题来自LeetCode 374. 猜数字大小,题目难度简单,与昨天的题目一样,也是一道标准二分法的题目,不知道是不是端午节的缘故,这两天的题目都比较简单,题目描述如下:

猜数字游戏的规则如下:

每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):

-1:我选出的数字比你猜的数字小 pick < num
1:我选出的数字比你猜的数字大 pick > num
0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。

示例 1:

输入:n = 10, pick = 6
输出:6
示例 2:

输入:n = 1, pick = 1
输出:1
示例 3:

输入:n = 2, pick = 1
输出:1
示例 4:

输入:n = 2, pick = 2
输出:2

提示:

1 <= n <= 231 - 1
1 <= pick <= n

贰 ? 基础二分法

确实因为机翻的问题,我看到评论区不少人吐槽这个难受的题目翻译,这里简单重复下题目信息,给定一个数字n,一个目标数组pick,以及一个对比目标数字与猜测数字的API guess,也就是说让我们在数字范围1-n内猜数字,假定猜测的数字是num,如果目标数字picknum大,guess返回1,反之返回-1,如果数字相等了则返回0,现在就是要我们根据guess的返回找到这个目标数字。

直觉上来说,这道题与昨天的题没什么太大区别,都是根据一个API返回结果来搜索目标数,当然我们需要尽可能少的调用API来找到这个数字,因此这里使用二分法是很恰当的做法。

比如,我们一开始就选择1-n的中间数作为我们第一次猜测的数,当guess返回1,说明我们目标数比我们猜测的数要大,自然下次要查询的范围是中间数的右边区域,因此需要调整左边界。假定guess返回的是-1,说明目标数比我们猜测的数字要小,自然需要调整右边界,思路已经很清晰了,来实现这段代码:

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
    // 定义左右边界,注意n在题目中给定的范围,最小是1,因此左边界是1,右边界是n
    let l = 1, r = n;
    // 考虑目标值与给的数组范围相同,比如1,1情况
    while (l <= r) {
      	// 这种做法是为了避免数字越界
        var mid = Math.floor(l + (r - l) / 2);
        const res = guess(mid);
        if (res === 0) {
          	// 找到了就可以跳出循环了,此时的mid就是我们要的数字
            break;
        };
        // 目标数字比mid大,所以调整左边界
        if (res === 1) {
            l = mid + 1;
            // 目标数字比mid小,调整右边界
        } else if (res === -1) {
            r = mid - 1;
        };
    }
    return mid;
};

我一开始写的while循环条件是l<r,结果挂在了1,1的例子上,也就是猜测的数字是1,n的范围也是1-1,由于不满足while条件,导致判断直接没进去,所以为了让mid至少能执行计算一次,改了条件为l<=r

而在我看了官方题解后,发现一个问题,以1,1的例子来说,当l<r不满足条件时,其实没必要进去走里面的逻辑,因为此时的l和r注定相等才会不满足条件,所以我们直接返回一个l即可,所以while里面需要考虑的逻辑可以针对这个思路改一改。

还是以第一次取值为mid来说,假定guess返回的是1,那么pick一定在mid的右侧且不可能是mid自身,因此调整左边界为mid+1。反之,我们可以将-1和0的情况归纳在一起,当guess返回-1或者0时,此时pick一定是在mid左侧(包含mid),因此调整右边界为mid。这样查找下去,一定会遇到l和r重叠的情况,根据提议这个pick肯定是存在的,所以当两个指针重叠时,其实已经找到我们想要找的数字了,这个思路的代码实现如下,其实与昨天的题目一模一样:

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
    let left = 1, right = n;
    // 循环直至区间左右端点相同
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (guess(mid) <= 0) {
            right = mid; // 答案在区间 [left, mid] 中
        } else {
            left = mid + 1; // 答案在区间 [mid+1, right] 中
        }
    }
    // 此时有 left == right,区间缩为一个点,即为答案
    return left
};

以上就是本题的思路分析。

JS Leetcode 374. 猜数字大小 题解分析

上一篇:.Net对接阿里云短信平台


下一篇:MVC的视图搜索顺序