Leetcode(69) Sqrt(x)

发表于 | 分类于

Description

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.

解法

这道题就是自己实现开方的函数，最开始的想法是硬碰撞，从0一直试到x/2+1，如果出现了乘积大于等于结果的情况则返回值，这里需要注意整型数范围问题，所以乘积用long型数表示

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int mySqrt(int x) {
        for (int i = 0; i <= x / 2 + 1; i++) {
            long res = (long) i * i;
            if (res == x) {
                return i;
            }
            if (res > x) {
                return i - 1;
            }
        }
        return -1;
    }
}

然后看到网上的思路发现还可以用二分法解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int left = 1;
        int right = x;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (x / mid >= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right - 1;
    }
}