374_猜数字大小

风扫地

1. 
   
2. /*
   
3. 们正在玩一个猜数字游戏。 游戏规则如下：
   
4. 我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
   
5. 每次你猜错了，我会告诉你这个数字是大了还是小了。
   
6. 你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：
   
7. 
   
8. -1 : 我的数字比较小
   
9. 1 : 我的数字比较大
   
10. 0 : 恭喜！你猜对了！
    
11. 示例 :
    
12. 输入: n = 10, pick = 6
    
13. 输出: 6
    
14. */
    

复制代码

风扫地

基本思路：二分查找
注意事项：防止加法溢出。

1. // Forward declaration of guess API.
   
2. // @param num, your guess
   
3. // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
   
4. int guess(int num);
   
5. 
   
6. class Solution {
   
7. public:
   
8.     int guessNumber(int n)
   
9.     {
   
10.         int ret_val = 0;
    
11.         int left  = 1;
    
12.         int right = n;
    
13.         int mid = 0;
    
14.         
    
15.         while(left <= right)
    
16.         {
    
17.             mid = left + (right-left)/2; /* 经典的两个正整数相加取平均数防溢出的写法 */
    
18.             ret_val = guess(mid);
    
19.             if(ret_val==0)
    
20.             {
    
21.                 ret_val = mid;
    
22.                 break;
    
23.             }
    
24.             else if(ret_val < 0 )
    
25.             {
    
26.                 right = mid - 1;
    
27.             }
    
28.             else
    
29.             {
    
30.                  left = mid + 1;
    
31.             }
    
32.         }
    
33.         
    
34.         
    
35.         return ret_val;
    
36.     }
    
37. };
    
38. 
    
39. 
    
40. 
    
41. /*
    
42. 执行结果：
    
43. 通过
    
44. 显示详情
    
45. 执行用时 :8 ms, 在所有 C++ 提交中击败了34.75% 的用户
    
46. 内存消耗 :8.1 MB, 在所有 C++ 提交中击败了64.30%的用户
    
47. */

复制代码