每天一道编程题

• 题目描述
• 样例
• python解法
• C++语言解法

题目描述

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!
题目大意：在[1, n]之间选择一个数字，然后写程序猜测选择的是哪个数字，给定一个API guess，guess返回1时表示踩的数字小了，返回-1表示猜的数字大了，0表示猜中。

样例

Example :

Input: n = 10, pick = 6
Output: 6

python解法

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while True:
            global g
            mid = l + (r-l)/2
            g = guess(mid)
            if g == 0:
                return mid
            elif g > 0:
                l = mid + 1
            else:
                r = mid - 1
        return -1

执行用时 :20 ms
内存消耗 :11.7 MB

题后反思：

C++语言解法

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int mid, l =1, r = n, g;
        while(true)
        {
            mid = l + (r - l)/2;
            g = guess(mid);
            if (g == 0)
            {
                break;
            }
            else if (g > 0)
            {
                l = mid + 1;
            }
            else 
            {
                r = mid - 1;
            }
        }
        return mid;
    }
};

执行用时 :4 ms
内存消耗 :8.1 MB

题后反思：

1. 两个数的中间值也可以用两数相加除以2，但是在计算机中要防止超出int型数据可表示整数的范围，所以使用左值加距离的一半求两个数的中间值。

文中都是我个人的理解，如有错误的地方欢迎下方评论告诉我，我及时更正，大家共同进步