374 Guess Number Higher or Lower 猜數(shù)字大小
Description:
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 :
Input: n = 10, pick = 6
Output: 6
題目描述:
我們正在玩一個(gè)猜數(shù)字游戲惑惶。 游戲規(guī)則如下：
我從 1 到 n 選擇一個(gè)數(shù)字。 你需要猜我選擇了哪個(gè)數(shù)字耗跛。
每次你猜錯(cuò)了，我會(huì)告訴你這個(gè)數(shù)字是大了還是小了已艰。
你調(diào)用一個(gè)預(yù)先定義好的接口 guess(int num)曼氛，它會(huì)返回 3 個(gè)可能的結(jié)果（-1，1 或 0）：
-1 : 我的數(shù)字比較小
1 : 我的數(shù)字比較大
0 : 恭喜庶橱！你猜對(duì)了痒蓬！
示例 :
輸入: n = 10, pick = 6
輸出: 6
思路:
二分法
時(shí)間復(fù)雜度O(logn), 空間復(fù)雜度O(1)
代碼:
C++:
// 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 low = 1;
while (low <= n)
{
int mid = low + ((n - low) >> 1);
if (!guess(mid)) return mid;
else if (guess(mid) > 0) low = mid + 1;
else n = mid - 1;
}
return low;
}
};
Java:
/* 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;
while (low <= n) {
int mid = low + ((n - low) >> 1);
if (guess(mid) == 0) return mid;
else if (guess(mid) > 0) low = mid + 1;
else n = mid - 1;
}
return low;
}
}
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: int) -> int:
low = 1
while low <= n:
mid = low + ((n - low) >> 1)
if not guess(mid):
return mid
elif guess(mid) > 0:
low = mid + 1
else:
n = mid - 1
return low
