LeetCode 374. 猜数字大小

简介: 猜数字游戏的规则如下:每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。

网络异常,图片无法展示
|

题目地址(374. 猜数字大小)

leetcode-cn.com/problems/gu…

题目描述

猜数字游戏的规则如下:
每轮游戏,我都会从 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

思路

二分法实现

代码

  • 语言支持:Python3

Python3 Code:

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 0, n
        while left <= right:
            mid = (left + right)//2
            res = guess(mid)
            if res == 0:
                return mid
            elif res == -1:
                right = mid - 1
            else:
                left = mid + 1
        return -1

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(logn)O(logn)
  • 空间复杂度:O(1)O(1)
目录
相关文章
|
6月前
leetcode:374. 猜数字大小(二分查找)
leetcode:374. 猜数字大小(二分查找)
36 0
【Leetcode -367.有效的完全平方数 -374.猜数字大小】
【Leetcode -367.有效的完全平方数 -374.猜数字大小】
44 0
|
Python
力扣每日一题:374.猜数字大小 python二分查找的基础公式!
力扣每日一题:374.猜数字大小 python二分查找的基础公式!
235 0
|
Python
Python|力扣猜数字
Python|力扣猜数字
53 0
|
算法 前端开发 程序员
「LeetCode」374-猜数字大小⚡️
「LeetCode」374-猜数字大小⚡️
133 0
「LeetCode」374-猜数字大小⚡️
|
算法
​LeetCode刷题实战299:猜数字游戏
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
131 0
​LeetCode刷题实战299:猜数字游戏
|
算法 API
​LeetCode刷题实战374:猜数字大小
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
111 0
[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏
[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏
[leetcode/lintcode 题解] 阿里算法面试题:猜数字游戏