美文网首页
374-猜数字大小

374-猜数字大小

作者: 饮酒醉回忆 | 来源:发表于2019-07-12 10:59 被阅读0次

    猜数字大小

    题目

    我们正在玩一个猜数字游戏。 游戏规则如下:
    我从1到n选择一个数字。 你需要猜我选择了哪个数字。
    每次你猜错了,我会告诉你这个数字是大了还是小了。
    你调用一个预先定义好的接口guess(int num),它会返回 3 个可能的结果(-1,1或 0):

    -1 : 我的数字比较小
    1 : 我的数字比较大
    0 : 恭喜!你猜对了!
    示例 :

    输入: n = 10, pick = 6
    输出: 6

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/guess-number-higher-or-lower
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路

    这个题的想法就是查找数字,暴力法就是1-n去遍历查询.但这样效率太低.因此应该使用二分法去比较.这里有个问题就是题目说的我的数字比较小,是说你应该再向小了猜.

    代码

    /* 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 left = 1;
            int right = n;
            while(left <= right){
                int mid = left + (right - left)/2;
                int result = guess(mid);
                if(result == 0){
                    return mid;
                }
                if(result == -1){
                    right = mid-1;
                }
                if(result == 1){
                    left = mid+1;
                }
            }
            return -1;
        }
    }
    

    相关文章

      网友评论

          本文标题:374-猜数字大小

          本文链接:https://www.haomeiwen.com/subject/wyqekctx.html