TNotes.leetcode

Appearance

0374. 猜数字大小【简单】

0374. 猜数字大小【简单】 ​

1. 📝 题目描述 ​

我们正在玩猜数字游戏。猜数字游戏的规则如下：

我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。

如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：

  • -1：你猜的数字比我选出的数字大 （即 num > pick）。
  • 1：你猜的数字比我选出的数字小 （即 num < pick）。
  • 0：你猜的数字与我选出的数字相等。（即 num == pick）。

返回我选出的数字。

示例 1：

txt
输入：n = 10, pick = 6
输出：6

示例 2：

txt
输入：n = 1, pick = 1
输出：1

示例 3：

txt
输入：n = 2, pick = 1
输出：1

提示：

  • 1 <= n <= 2^31 - 1
  • 1 <= pick <= n

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
  let left = 1
  let right = n

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2)
    const result = guess(mid)

    if (result === 0) {
      return mid // 猜对了
    } else if (result === -1) {
      right = mid - 1 // 猜的数字太大，往左找
    } else {
      left = mid + 1 // 猜的数字太小，往右找
    }
  }

  return -1 // 理论上不会执行到这里
}
  • 时间复杂度：O(log⁡n)，因为每次都将搜索范围减半
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

Discussions