【Day49】374. 猜数字大小

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

题解:

/** 
 * 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
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int l = 0;
        int r = n;
        while (l <= r)
        {
            int m = (l-r)/2 + r;
            int res = guess(m);
            if (res == 0)
            {
                return m;
            }
            else if (res < 0)
            {
                r = m-1;
            }
            else
            {
                l = m + 1;
            }
        }

        return -1;
    }
};

   转载规则


《【Day49】374. 猜数字大小》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day50】852. 山脉数组的峰顶索引 【Day50】852. 山脉数组的峰顶索引
852. 山脉数组的峰顶索引符合下列属性的数组 arr 称为 山脉数组 : arr.length >= 3 存在 i(0 < i < arr.length - 1)使得: arr[0] < arr[1] <
2021-06-15
下一篇 
【Day48】278. 第一个错误的版本 【Day48】278. 第一个错误的版本
278. 第一个错误的版本你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, …,
2021-06-13
  目录