题目地址：https://leetcode.com/problems/guess-number-higher-or-lower/#/descriptionopen in new window
题目描述
Weare playing the Guess Game. The game is as follows:
Ipick 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.
Youcall a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.
Return 6.
题目大意
从1～n中取了一个数字，现在给出了guess()函数，要你猜这个数字是多少。
解题方法
做这个题的重点是明白guess()函数，题目说了是我取了一个数字，你去猜这个数字，guess()是我的数字大了还是小了。。明白这个意思了么。
所以这个题是标准的二分查找。
/* 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 low = 1;
int high = n;
int mid = 0;
while(low <= high){
mid = low + (high - low) / 2;
if(guess(mid) == -1){
high = mid - 1;
}else if(guess(mid) == 1){
low = mid + 1;
}else{
return mid;
}
}
return mid;
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
python解法如下：
# 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
"""
left, right = 1, n[left, right]
mid = left
while left <= right:
mid = (right + left) / 2
res = guess(mid)
if res == 0:
return mid
elif res == 1:
left = mid + 1
else:
right = mid - 1
return mid
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发