题目:374. 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, 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(int num)告诉是猜对,还是猜大/小了。
二分查找。
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1, high = n;
int pick = low + (high - low) / 2;
while(low <= high && guess(pick) != 0){
if (guess(pick) == 1) low = pick +1;
else high = pick -1;
pick = low + (high - low) / 2;
}
return pick;
}
}
减少调用guess(num)的次数,return那里返回low或high都可以,因为跳出循环的时候,low=high。
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1, high = n;
int pick;
int tip;
while(low < high){
pick = low + (high - low) / 2;
tip = guess(pick);
if(tip == 0) return pick;
else if (tip == 1) low = pick + 1;
else high = pick - 1;
}
return high;//or low
}
}
网友评论