Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

x的平方根

Posted on Edited on In , ,
Symbols count in article: 1.3k Reading time ≈ 1 mins.

来源Leetcode第69题x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 2:

输入: 8
输出: 2

不正经解法

最简单的就直接调用Math.sqrt()就行了，但这很明显不符合题意。
代码就一句:

1
return (int)Math.sqrt(x);

二分查找

利用x/mid 来比较是否接近目标

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int mySqrt(int x) {
    if(x == 0 || x == 1)    return x;
    int l = 0;//左边界
    int r = x;//右边界
    while (l <= r) {
        int mid =  (r + l) / 2;
        int s = x / mid; //用来判断mid大于目标还是小于目标，或等于目标
        int ss = x / (mid + 1);
        if (x / s == s) return s; //刚好是他的算术平方根
        if (s > mid && ss < mid + 1) return mid; //例如6 在2的平方以及 3的平方之间  答案为2
        if (s > mid) l = mid + 1; //调整边界
        if (s < mid) r = mid - 1;
    }
    return 0;
}

当然也有用double类型来提高精度的

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int mySqrt2(int x) {
    double mid = (double) x / 2;
    double left = 0;
    double right = x;
    while ((int)left <(int) right){
        if(mid * mid > x){
            right = mid;
            mid = (double) (left + right) / 2;
        }else {
            left = mid;
            mid = (double) (left + right) / 2;
        }
    }
    return (int)mid ;
}

牛顿迭代法

来源题解

关于牛顿迭代法

这种算法的原理很简单，我们仅仅是不断用 (x, f(x))的切线来逼近方程 x^2-a=0根。根号 a 实际上就是 x^2-a=0的一个正实根，这个函数的导数是 2x。也就是说，函数上任一点 (x,f(x)) 处的切线斜率是 2x。那么，x-f(x)/(2x)就是一个比 x 更接近的近似值。代入 f(x)=x^2-af得到 x-(x^2-a)/(2x)，也就是 (x+a/x)/2。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int s;
    
 public int mySqrt(int x) {
     s=x;
     if(x==0) return 0;
    return ((int)(sqrts(x)));
  }
    
    public double sqrts(double x){
      double res = (x + s / x) / 2;
    if (res == x) {
      return x;
    } else {
      return sqrts(res);
    }
    } 
}