leetcode69.x的平方根_leetcode 69. x 的平方根

leetcode69.x的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2
1
2

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

直接用库函数

想必这道题的目的肯定不是让我们用库函数。

class Solution {
public:
    int mySqrt(int x) {
        int res;
        res=sqrt(x);
        return res;
    }
};
1
2
3
4
5
6
7
8

用二分法实现

class Solution {
public:
    int mySqrt(int x) {
        long long left=0,right=x/2+1,mid;//定义成long long类型是因为在求mid平方的时候会出现越界
        
        while(left<right){
            mid=(left+right+1)/2;  //取右中位数，否则取左中位数会进入死循环 
            if(mid*mid>x){
                right=mid-1;
            }
            else{
                left=mid;
            }
          
        }
        return left;
    }
};
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) {
        long long left=0,right=x/2+1,mid;//定义成long long类型是因为在求mid平方的时候会出现越界
        
        while(left<=right){
            mid=(left+right)/2;  
            if(mid*mid==x)
                return mid;
            else if(mid*mid>x){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
          
        }
        return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二刷
这道题的解题思想是二分法，还有一点特别关键，就是处理越界的情况
注意下面中间值的计算方法，这样处理就可以避免 x 为INT_MAX时的越界的情况

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0)
            return x;
        int l = 1, r = x;
        int res;
        while(l <= r){
            //long long mid = (l + r) >> 1;
            long long mid = (r - l) / 2 + l;
            if(mid * mid < x){
                l = mid + 1;
            }
            else if(mid * mid > x){
                r = mid - 1;
            }
            else
                return mid;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在评论区看到一种处理 mid * mid 越界的情况的处理方法是采用 x / mid除法的形式

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0)
            return x;
        int l = 1, r = x;
        int res;
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if(x / mid > mid){
                l = mid + 1;
            }
            else if(x / mid < mid){
                r = mid - 1;
            }
            else
                return mid;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考官方题解还有牛顿法，数学方法
数学方法：$$\sqrt{x}=e^{ln\sqrt{x}}=e^{\frac{1}{2}lnx}$$

ans = exp(0.5 * log(x))
1

最终的结果要么是 ans,要么是ans + 1,这里直接取整数会有误差。注意：如果（ans + 1）* (ans + 1) <= x ,那么取ans + 1; 否则取 ans。
这里在求（ans + 1）* (ans + 1) 可能会出现越界，那么在定义的时候将ans 定义成long long型

class Solution {
public:
    int mySqrt(int x) {
        if(x < 2)
            return x;
        long long ans;
        ans = exp(0.5 * log(x));
        return (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
};
1
2
3
4
5
6
7
8
9
10

牛顿法：
将该问题转化为求方程的零点，假设求a的平方根
定义方程：$$f(x)=x^2-a$$
那么$$f(x)=0的解就是a的平方根$$
利用牛顿法求该方程的零点，首先找出迭代关系式：
令初始值$$x_0=a$$
在该点的切线方程为$$y=f(x_0)+(x-x_0)f^{\prime }(x_0)$$
切线方程与x轴的交点的横坐标为方程的零点,当然并不是一开始求得的结果就是目标解，而是说逐渐迭代，当相邻两次的解小于某个值时，我们就把当前值作为目标解，在该问题中可用当前结果的平方是否小于等于a来判断。
那分析到这里，我们来看迭代关系式：$$x=x_0-\frac{-f(x_0)}{f^{\prime }(x_0)}=x_0-\frac{x_0^2-a}{2x_0}=\frac{1}{2}(x_0+\frac{a}{x_0})$$

class Solution {
public:
    int mySqrt(int a) {
        if(a < 2)
            return a;
        long long x0 = a;
        while(x0 * x0 > a)
            x0 = 0.5 * (x0 + a / x0);
        return x0;
    }
};
1
2
3
4
5
6
7
8
9
10
11