374.猜数字大小 python二分查找的基础公式!
一个优秀的内容风控解决方案应该是怎样的?
信息传播的媒介与形态五花八门,对于互联网平台来说,保障内容安全越来越难。当下互联网平台面临哪些困境?7月3日,腾讯安全思享会,带大家一起探索亟需的答案,限额报名
374.猜数字大小
https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/374cai-shu-zi-da-xiao-pythoner-fen-cha-z-6b8x/
难度:简单
题目:
猜数字游戏的规则如下:
每轮游戏,我都会从 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
分析
今天这道每日一题,比昨天的:
278.*个错误的版本
要更简单一些,是一个标准的二分查找target。虽然这道题的中文翻译实在是有些逗比…
然后看看官方解题,解决不知道是套公式套的死板还是怎样?
以下是官方解题:
class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            if guess(mid) <= 0:
                right = mid   # 答案在区间 [left, mid] 中
            else:
                left = mid + 1   # 答案在区间 [mid+1, right] 中
        # 此时有 left == right,区间缩为一个点,即为答案
        return left
搞不懂,既然guess结果为0,即找到target了,不退出循环,还在那里缩小什么范围?
就是为了让你的代码看着能少一层判断,“显得”更为简洁吗?
解题:
class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = (left + right) // 2
            ret = guess(mid)
            if ret == 0:
                return mid
            elif ret == -1:
                right = mid – 1
            else:
                left = mid + 1