0374. Guess Number Higher or Lower¶
题目信息¶
- 题号:
0374
- 难度:
Easy
- 主题:
交互接口、隐藏整数、返回值语义、搜索范围
- 原题:
- 重点:
隐藏整数位于 1 到 n、只能通过
guess获得大小关系、正确解释-1、0、1
题目重述¶
系统预先在闭区间 [1, n] 中选择一个整数 pick。平台提供 guess(num) 接口:若 num 大于 pick,返回 -1;若 num 小于 pick,返回 1;二者相等时返回 0。
实现函数并返回隐藏整数 pick。n 位于 [1, 2^31-1],平台保证 pick 一定在该范围内。程序不能直接读取 pick,只能根据多次接口调用的结果确定答案。
自建示例¶
隐藏数位于区间内部:
输入:n = 20,pick = 13
输出:13
解释:对小于 13 的猜测,接口返回 1;对大于 13 的猜测,接口返回 -1;猜测 13 时返回 0。
隐藏数位于上边界:
输入:n = 6,pick = 6
输出:6
解释:隐藏数可以等于 n,搜索范围包含两个端点。
接口返回值直接决定保留哪一半¶
维护仍可能包含 pick 的闭区间 [left, right]。猜测中点后,返回 0 立即得到答案;返回 -1 表示猜测偏大,隐藏数只能在左半;返回 1 表示猜测偏小,隐藏数只能在右半。每次更新都保留端点合法性。
C++ 实现¶
class Solution {
public:
int guessNumber(int n) {
long long left = 1;
long long right = n;
while (left <= right) {
long long middle = left + (right - left) / 2;
int result = guess(static_cast<int>(middle));
if (result == 0) return static_cast<int>(middle);
if (result < 0) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
};
代码分析¶
guess 的 -1 与 1 含义恰好分别对应“猜大”和“猜小”,不能按普通比较函数的直觉反写;用 long long 计算中点避免边界加法溢出。每次调用缩小一半搜索区间,时间复杂度为 O(log n),额外空间为 O(1)。