leetcode [#374]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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.

---

解决方案

/* 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); */
   @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 i = 1, j = n;
        while(i < j) {
            int mid = i + (j - i) / 2;
            if(guess(mid) == 0) {
                return mid;
            } else if(guess(mid) == 1) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }
}

---

注意事项

1. 要清楚理解题意。待实现方法guessNumber()需要一个参数：即1~n的n，但是整个功能需要传入两个参数：数据范围、出题人选择的数字。其中，n传递给guessNumber()，而选择的数字pick则在solution类实例化时通过在其构造函数中调用父类构造函数来传入。因此，在本地测试时要加上guess()方法的实现，整体代码如下：

   package task374;
   
   /** * Created by gaochang on 2016/11/24. */
    * Created by gaochang on 2016/11/24.
    */
   public class solution extends GuessGame{
       public solution(int pick){
           super(pick);
       }
       public int guessNumber(int n) {
           int i = 1, j = n;
           while(i < j) {
               int mid = i + (j - i) / 2;
               if(guess(mid) == 0) {
                   return mid;
               } else if(guess(mid) == 1) {
                   i = mid + 1;
               } else {
                   j = mid - 1;
               }
           }
           return i;
       }
       public static void main(String[] args){
           int pick = 6;
           int n = 10;
           solution s = new solution(pick);
           int re = s.guessNumber(n);
           System.out.println(re);
       }
   }
   class GuessGame {
       private int res;
   
       public GuessGame(int val){
           this.res = val;
       }
       public int guess(int num) {
           if(res > num) {
               return 1;
           } else if(res == num){
               return 0;
           } else {
               return -1;
           }
       }
   }

2. 在1~n的范围内，对pick进行二分查找即可。