网站解析不了,自己建设网站步骤,网站策划案模板,手机网站商城建设374. 猜数字大小
难度#xff1a;简单
题目
猜数字游戏的规则如下#xff1a;
每轮游戏#xff0c;我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了#xff0c;我会告诉你#xff0c;你猜测的数字比我选出的数字是大了还是小了。
你可以通…374. 猜数字大小
难度简单
题目
猜数字游戏的规则如下
每轮游戏我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了我会告诉你你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果返回值一共有 3 种可能的情况-11 或 0
-1我选出的数字比你猜的数字小 pick num1我选出的数字比你猜的数字大 pick num0我选出的数字和你猜的数字一样。恭喜你猜对了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 2^31 - 11 pick n
个人题解
思路
很显然用二分查找可以logn时间复杂度找到对应数
/** * Forward declaration of guess API.* 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* int guess(int num);*/public class Solution extends GuessGame {public int guessNumber(int n) {int left 1;int right n;while (left right) {int mid left (right - left 1);int guessResult guess(mid);if (guessResult 0) {return mid;} else if (guessResult 1) {left mid 1;} else {right mid - 1;}}return left;}
}官方题解
public class Solution extends GuessGame {public int guessNumber(int n) {int left 1, right n;while (left right) { // 循环直至区间左右端点相同int mid left (right - left) / 2; // 防止计算时溢出if (guess(mid) 0) {right mid; // 答案在区间 [left, mid] 中} else {left mid 1; // 答案在区间 [mid1, right] 中}}// 此时有 left right区间缩为一个点即为答案return left;}
}作者力扣官方题解 链接https://leetcode.cn/problems/guess-number-higher-or-lower/solutions/824520/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
