374. 猜数字大小

题目:https://leetcode-cn.com/problems/guess-number-higher-or-lower/

代码:

/* 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) {
        if(guess(1)==0){
            return 1;
        }
        int minNum = 1;
        int maxNum = n;
        int guessNum;
        int guessRes;
        while(true){
            guessNum = (int)(((long)minNum+(long)maxNum)/2);
            guessNum = guessNum==minNum?maxNum:guessNum;
            guessRes = guess(guessNum);
            // System.out.println(guessNum+" "+minNum+"~"+maxNum);
            if(guessRes == -1){
                maxNum = guessNum;
            }else if(guessRes == 1){
                minNum = guessNum;
            }else{
                return guessNum;
            }
        }
    }
}

思路:这是个猜数字的游戏,每次调用题目中给出的guess方法题目都会告诉你猜的数字是大了还是小了。我回想起小时候看的一个叫《购物街》的综艺节目,里面就有类似的猜价格的游戏。解决方法就是每次取中间的数字猜。这样速度最快。

注意:

1、给定的数字太大,我在计算最小的数跟最大的数中间那个数的时候,超出了int的范围,导致出现了负数的情况,所以我在代码中计算的时候进行的long类型的转换。

guessNum = (int)(((long)minNum+(long)maxNum)/2);

2、在代码中,int类型的除法是舍去的取整方法。所以在遇到(5+6)/2这种类似情况时,会一直得到猜的数字是5,但实际应该是6,导致程序死循环,所以为了解决这个问题,当发现guessNum计算出来的数字是 minNum的时候,直接猜maxNum的值就对了。所以有如下这样代码。

guessNum = guessNum==minNum?maxNum:guessNum;

3、因为有第2点的存在,所以如果答案就是最开始的最小值1呢?因为第2点的错在程序就会进入死循环,所以我们干脆一上来先猜测一下1这个数字是不是正确答案。