首页 > 代码库 > leetcode第一刷_Sqrt(x)

leetcode第一刷_Sqrt(x)

这道题乍看下来非常简单,实际上要注意的问题非常多。

注意看给出来的函数的接口,返回的是int值,也就是计算结果是个近似值。怎样求呢?难道是从2开始往上算?直到某个值正好接近x?当然不行,肯定超时了。再仔细想一下,对了,有二分法,从最大的开始,每次计算一下平方,如果结果比x大,那么缩短上界,否则提高下界。

思想很正确,下面的问题是最大的那个值是多少?你会毫不犹豫的说出是x啊,x的平方根肯定比x小吧。好,那如果x是INT_MAX呢,你想用什么类型来存储这个平方的结果?而且这样每次减半,也得好一会儿才能收敛,毕竟INT_MAX太大了。再仔细想一下,其实最大值并不是x啊,而应该是x的平方根,对吧,因为我们求的就是平方根啊。

剩下还有两个问题,第一个,怎样判定这个值和x够近了呢?看看它的平方跟x之间的差小于某个阈值?相信这个阈值不应该是个定值,而是变化的,毕竟如果本来数小的话,小的差值也说明差别很大。那么有没有更简洁一些的方法?当然有,因为返回的是int嘛,只要算一下a的平方比x小,而(a+1)的平方比x大就可以了嘛,而且求(a+1)的平方时可以直接用a的平方的结果。那么好,第二个问题,用什么类型来存储a和(a+1)的平方呢?用int?肯定溢出啦,因为a的最大值是sqrt(INT_MAX),(a+1)的平方肯定溢出int了,应该用long long啊亲。

代码还是很简单的:

class Solution {
public:
    int sqrt(int x) {
        if(x == 1)
            return 1;
        int MAX = 46340;
        int middle, start = 0, end = x;
        while(start<=end){
            middle = min(MAX, start+(end-start)/2);
            long long tp1 = middle*middle;
            long long tp2 = tp1+2*middle+1;
            if(tp1<=x&&tp2>x)
                return middle;
            if(tp1>x)
                end = middle-1;
            else
                start = middle+1;
        }
        return 0;
    }
};