LeetCode 题解工作台
猜数字大小
我们正在玩猜数字游戏。猜数字游戏的规则如下： 我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。 如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 二分·搜索·答案·空间
答案摘要
我们在区间 进行二分查找，找到第一个满足 `guess(x) <= 0` 的数，即为答案。 时间复杂度 $O(\log n)$。其中 为题目给定的上限。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
我们正在玩猜数字游戏。猜数字游戏的规则如下：
我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。
如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：
-1：你猜的数字比我选出的数字大 （即num > pick）。1：你猜的数字比我选出的数字小 （即num < pick）。0：你猜的数字与我选出的数字相等。（即num == pick）。
返回我选出的数字。
示例 1：
输入：n = 10, pick = 6 输出：6
示例 2：
输入：n = 1, pick = 1 输出：1
示例 3：
输入：n = 2, pick = 1 输出：1
提示：
1 <= n <= 231 - 11 <= pick <= n
解题思路
方法一：二分查找
我们在区间 进行二分查找，找到第一个满足 guess(x) <= 0 的数，即为答案。
时间复杂度 。其中 为题目给定的上限。空间复杂度 。
# The guess API is already defined for you.
# @param 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
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
return bisect.bisect(range(1, n + 1), 0, key=lambda x: -guess(x))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) since each guess reduces the search space by half. Space complexity is O(1) because only the low, high, and mid variables are stored. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect you to explain why binary search fits this interactive guessing scenario.
- question_mark
They may ask about edge cases like n = 1 or pick at the boundaries.
- question_mark
Interviewers often check whether you handle integer overflow when computing mid = low + (high - low)/2.
常见陷阱
外企场景- error
Using (low + high)/2 directly can cause integer overflow for large n.
- error
Not updating low or high correctly based on the guess feedback leads to infinite loops.
- error
Failing to consider that pick could be at the initial bounds causes off-by-one errors.
进阶变体
外企场景- arrow_right_alt
Modify the game to allow a range of valid picks and find any number in that range.
- arrow_right_alt
Implement a version where guesses have a cost, requiring minimal total guess cost.
- arrow_right_alt
Adapt the binary search approach to a descending ordered pick range instead of ascending.