leetcode Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API
guess(int num)
which returns 3 possible results (-1
,1
, or0
):
1
2
3 -1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!Example:
1
2
3 n = 10, I pick 6.
Return 6.
题意:猜数字,给定一个数n,要你调用guess函数,来判断你猜的n和对方的值是否一样。
思路:就是二分搜索嘛。。。。没什么好说的
C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
class Solution {
public:
int guessNumber(int n) {
int L = 1,R = n;
while(L<=R){
int mid = L + ((R - L) >> 1);
int res = guess(mid);
if(res == 0) return mid;
else if(res == 1) L = mid + 1;
else R = mid - 1;
}
return L;
}
};
Java 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int L = 1,R = n;
while(L <= R){
int mid = L + ((R - L) >> 1);
int res = guess(mid);
if(res == 0) return mid;
else if(res == 1) L = mid + 1;
else R = mid - 1;
}
return L;
}
}
Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# 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):
class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
L, R = 1, n
while L <= R:
mid = L + ((R - L) >> 1)
res = guess(mid)
if res == 0:
return mid
elif res == 1:
L = mid + 1
else:
R = mid - 1
return L
本题是leetcode 374 Guess Number Higher or Lower题解
更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/