Sqrt(x)

题目描述

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

解题思路

有一个避免溢出的方法 避免溢出的小技巧，就是把mid*mid == x写成mid == x/mid。

对于一个非负整数，它的平方根不会超过 n/2，遍历实现

代码

class Solution {
    public int mySqrt(int x) {
      //对于一个非负整数，它的平方根不会超过 n/2
      if(x<=0)
          return 0;
      int res = 1;
      for(int i=1;i<=x/2;i++){
          if(i==x/i)
              res = i;
          else if(i>x/i){
              res = i-1;
              break;
          }

      }
        return res;
    }
}

第二种解法：可以使用二分搜索的方法

class Solution {
    public int mySqrt(int x) {
        if (x <= 0) 
            return 0;

        int left = 1;
        int right = x;     
        while (left <= right) {
            int mid = (right +left) / 2;
            if (mid == x / mid) 
                return mid;
            else if(mid > x / mid)                
                 right = mid - 1;
               else 
                 left = mid + 1;
        }
        return right;
    }
}

第三种解法：使用牛顿法来实现 ？？？？？

计算x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，如上图所示。

首先取x0，如果x0不是解，做一个经过(x0,f(x0))这个点的切线，与x轴的交点为x1。

同样的道理，如果x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。

以此类推。。。

最后

以上就是多情鞋垫为你收集整理的Sqrt(x)的全部内容，希望文章能够帮你解决Sqrt(x)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。