leetCode-0069_x的平方根

Posted on | In |

题目描述

英文题目

  • Implement int sqrt(int x).

    Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

    Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

    Example 1:

    1
    2
    Input: 4
    Output: 2

    Example 2:

    1
    2
    3
    4
    Input: 8
    Output: 2
    Explanation: The square root of 8 is 2.82842..., and since 
                 the decimal part is truncated, 2 is returned.
中文题目

  • 实现 int sqrt(int x) 函数。

    计算并返回 x 的平方根，其中 x 是非负整数。

    由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

    示例 1:

    1
    2
    输入: 4
    输出: 2

    示例 2:

    1
    2
    3
    4
    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 
         由于返回类型是整数，小数部分将被舍去。

解决方法

方法一
  • 描述
  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <math.h>

int mySqrt(int x)
{
    int low = 0;
    int high = x;
    int ret = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (mid * mid <= x) {
            ret = mid;
            low = mid + 1;
        }
        else if (mid * mid > x) {
            high = mid - 1;
        }
    }
    return ret;
}

void test()
{
    int n = 1;
    int r = mySqrt(n);
    printf("%d\n",r);
}

题目来源

Sqrt(x)

x 的平方根