专栏首页Michael阿明学习之路LeetCode 374. 猜数字大小(二分查找)

LeetCode 374. 猜数字大小(二分查找)

1. 题目

我们正在玩一个猜数字游戏。 游戏规则如下:

  • 我从 1 到 n 选择一个数字。
  • 你需要猜我选择了哪个数字。
  • 每次你猜错了,我会告诉你这个数字是大了还是小了。

你调用一个预先定义好的接口 guess(int num),它会返回 3 个可能的结果(-1,1 或 0):

-1 : 我的数字比较小 1 : 我的数字比较大 0 : 恭喜!你猜对了!

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/guess-number-higher-or-lower 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 模拟二分查找
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int i = 1, j = n, mid;
        while(i <= j)
        {
        	mid = i+((j-i)>>1);
        	if(guess(mid) == 0)
        		return mid;
        	else if(guess(mid) < 0)
        		j = mid-1;
        	else
        		i = mid+1;
        }
        return mid;
    }
};

0 ms 8.2 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1064. 不动点(二分查找)

    给定已经按升序排列、由不同整数组成的数组 A,返回满足 A[i] == i 的最小索引 i。 如果不存在这样的 i,返回 -1。

    Michael阿明
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • LeetCode 253. 会议室 II(贪心+优先队列)

    给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei), 为避免会议冲突,同时要考虑充分...

    Michael阿明
  • 并查集

    void Make_set(int n) { for(int i=0;i<=n;i++) { father[i]=i; ...

    用户1624346
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

    查询区间 [ id-k,id+k] 小于 val 的个数 num , 再在该区间查询第 num 大的数。

    用户2965768
  • 4768 跳石头

    4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

    attack
  • 2570 绝对素数

    2570 绝对素数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一个自然数...

    attack
  • P2820 局域网

    题目背景 某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回...

    attack
  • 推荐一个markdown格式转html格式的开源JavaScript库

    用浏览器打开这个html,在顶部输入框里输入markdown代码后,能自动调用这个开源库,转换成html源代码,然后赋给innerHTML, 这样我们在UI上能...

    Jerry Wang
  • 逆元模板

    对于(a/b)%m==? 1.当m是素数的时候,根据费马小定理,直接输出b^(n-2)即可 2.否则,扩展欧几里得exgcd(b,m,x,y) 1 #incl...

    attack

扫码关注云+社区

领取腾讯云代金券