x的平方根

一、题目

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 231 - 1

二、题解

题解一（直接使用库函数）

1
2
3
public static int mySqrt(int x) {
    return (int)Math.sqrt(x);
}

!image-20241213161013631

题解二（二分法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int mySqrt(int x) {
    if (x < 2) {
        return x; // 处理特殊情况 0 和 1
    }
    int left = 1, right = x / 2;
    int result = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((long) mid * mid <= x) {
            result = mid; // 更新结果
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

image-20241213161841926

题解三（牛顿迭代）

完全看不懂，等后面再看吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }

    double C = x, x0 = x;
    while (true) {
        double xi = 0.5 * (x0 + C / x0);
        if (Math.abs(x0 - xi) < 1e-7) {
            break;
        }
        x0 = xi;
    }
    return (int) x0;
}
/*
作者：力扣官方题解
链接：https://leetcode.cn/problems/sqrtx/solutions/238553/x-de-ping-fang-gen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

三、总结

还是Jdk自带的牛逼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class MySqrt {

    public static void main(String[] args) {
        int result = mySqrt(8);
        System.out.println(result);
    }

    public static int mySqrt1(int x) {
       return (int)Math.sqrt(x);
    }


    public static int mySqrt(int x) {
        if (x < 2) {
            return x; // 处理特殊情况 0 和 1
        }
        int left = 1, right = x / 2;
        int result = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((long) mid * mid <= x) {
                result = mid; // 更新结果
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}