p374

发表于 | 分类于 |

LeetCode p374 Guess Number Higher or Lower 题解

1.题目：

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.

题意：

根据所给的api,输出要猜的那个数。

2.解题思路:

二分

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
/* 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) {
        return search(1,n);
    }
    public int search(int left,int right){
        int mid = left /2 + right / 2 + left % 2;
        if (guess(mid) == 0) return mid;
        if (guess(mid) == 1) return search(mid + 1,right);
        else return search(left,mid - 1);
    }
}

4.一些总结：