LeetCode 每日一题 [29] x 的平方根

LeetCode x 的平方根 [简单]

实现 int sqrt(int x) 函数

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。

题目分析：

在JDK底层，Math.sqrt(x);使用的时本地方法

解法1

使用JDK的API解决

解法2

对数据的一半整除进行迭代 如果相等则返回，如果大于了，则-1返回，迭代完成都没有，则返回i 但是小数没问题，大数据就挂了

解法3

二分查找法 x的平方根时满足 k*k <= x 的最大值

解法4

转换为数学运算

解法5

牛顿迭代

代码实现

public class LeetCode_28_MySqrt {
    public static void main(String[] args) {
        test2();
    }

    public static void test2() {
        int i;
        for (i = 0; i < 2147483647; i++) {
            if (trueResult(i) != mySqrt3(i)) {
                System.out.println(trueResult(i));
                System.out.println(mySqrt(i));
                break;
            }
        }
        System.out.println("-----------");
        System.out.println(i);
    }

    public static void test1() {
        int i;
        for (i = 0; i < 2147483647; i++) {
            if (trueResult(i) != mySqrt2(i)) {
                System.out.println(trueResult(i));
                System.out.println(mySqrt(i));
                break;
            }
        }
        System.out.println("-----------");
        System.out.println(i);
    }

    public static void test() {
        int i;
        for (i = 0; i < 50000000; i++) {
            if (trueResult(i) != mySqrt(i)) {
                System.out.println(trueResult(i));
                System.out.println(mySqrt(i));
                break;
            }
        }
        System.out.println("-----------");
        System.out.println(i);
    }

    public static int mySqrt4(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;
    }

    public static int mySqrt3(int x) {
        if (x == 0) {
            return 0;
        }
        int l = 0, r = x, ans = -1;
        while (l < r) {
            int mid = 1 + (r - 1) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public static int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }

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

    public static int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        if (x <= 3) {
            return 1;
        }
        for (int i = 0; i <= (int) x / 2; i++) {
            if (i * i == x) {
                return i;
            } else if (i * i > x) {
                return i - 1;
            } else if (i == (int) x / 2) {
                return i;
            }
        }
        return 0;
    }
}