Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Sqrt(x)

Leetcode algorithms 第 69 题:Sqrt(x) 。

题目

Implement int sqrt(int x).

Compute and return the square root of x.

解答1

求x的平方根,可以使用pow函数int(pow(double(x), 0.5)),直接得到答案。但这显然不是想要的答案。

首先可以使用二分法,每次根据中间位置的元素判断答案所在的区间。

注意x不一定有整数平方根,最后需要根据平方与x的大小关系判断答案是否要减一。

具体代码如下:

class Solution {
public:
    int sqrt(int x) {
        if (x == 0) return 0;
        
        unsigned long long st = 0, ed = x, mid, tem;
        while (st < ed)
        {
            mid = st + ((ed - st) >> 1);
            if ((tem = mid * mid) == x) return mid; //平方根为正数
            else if(x > tem) st = mid + 1;
            else ed = mid - 1;
        }
        if ((tem = st * st) > x) return st - 1; //太大
        else return st;
    }
};

解答2

另外也可以使用牛顿法进行求解,求x^2=n可以转化为求f(x)=x^2-n的根.

对于曲线上的任意一点(xn, f(xn)),做经过该点的切线,即

f(x) = f(xn) + f’(xn) * (x – xn)

令切线方程等于0,可得

xn+1 = xn – f(xn) / f’(xn)

这里代入f(x)的具体表达式,可得

xn+1 = xn – (xn^2 – n) / (2*xn) = xn – xn / 2 + n / (2*xn) = xn / 2 + n / (2*xn) = (xn + n / xn) / 2

于是可以根据这个迭代公式进行迭代,当两代之间的距离足够小时可以认为找到答案。

具体代码如下:

class Solution {
public:
    int sqrt(int x) {
        if (x == 0) return 0;

        double pre = -1, cur = 1; //分别为xn和xn+1
        while (fabs(cur - pre) > 1e-6)
            pre = cur, cur = x / (2 * cur) + cur / 2;
        return int(cur);
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论