leetcode 69 求平方根

二分查找,不过查找过程中的判断条件更细一些,比如会判断mid以及mid+1的正确性,贴代码

class Solution {
public:
    int mySqrt(int x) 
    {
        if(x == 0)
        return 0;
        if(x == 1)
        return 1;
        long long x_temp = x;
        long left = 1;
        long right = x_temp-1;
        while(left<=right)
        {
            long long mid = (left + right)/2;
            if(mid*mid == x_temp)
            return mid;
            else if(mid*mid > x_temp)
            {
                right = mid - 1;
            }
            else
            {
                if((mid+1)*(mid+1) > x_temp)
                return mid;
                else if((mid+1)*(mid+1) == x_temp)
                return mid+1;
                else
                {
                    left = mid + 1;
                }
            }
        }
        return 0;
    }
};

牛顿迭代法,需要数学方面的推导,设定一个函数y = x^2 -c,C开根号值即为该函数正零点,然后通过每一点的切线与x轴的交点不断逼近目标值。贴代码

 1 class Solution {
 2 public:
 3     int mySqrt(int x) 
 4     {
 5         if(x == 0)
 6         return 0;
 7         double C = x;
 8         double x0 = x;
 9         while(1)
10         {
11             double x_temp = 0.5*(x0 + C/x0);
12             if(fabs(x_temp-x0)<1e-7)
13             break;
14             x0 = x_temp;
15         }
16         return x0;
17     }
18 };

 

上一篇:辐轮王土拨鼠69万世界10大碳纤维自行车哪个牌子好耐用质量好


下一篇:找出小于100点能够被3整除的正整数。