题目: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这个数字是不是正确答案。