leetcode 69. x 的平方根

佚名 6年前 (2019-04-17) 随笔 1772人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

牛顿法：这个方法更快，但是有两点注意：

1）牛顿法的原理：

2）更新值时溢出的问题：

牛顿法的前提：这个表达式在至少求解范围是单调递增的；

溢出减少就是使计算式的数字尽量小，尽量先做差再做和，或者先创造差，再做和；

class Solution {
public:
    int mySqrt(int x) {
        if(x==0 || x==1) return x;
        int r=x;
        while(r>x/r){
            r=x/r+(r-x/r)/2;
        }
        return r;
    }
};

二分法：

class Solution {
public:
    int mySqrt(int x) {
        if(x==0 || x==1) return x;
        int l=0,r=x,res;
        while(l<=r){
            int m=(l+r)/2;
            if(m==x/m) return m;
            if(m>x/m)
                r=m-1;
            else{
                l=m+1;
                res=m;
            }
        }
        return res;
    }
};