算法leetcode｜69. x 的平方根（rust重拳出击）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法leetcode｜69. x 的平方根（rust重拳出击）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

69. x 的平方根：

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

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

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

样例 1：

输入：
	
	x = 4
	
输出：
	
	2

样例 2：

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

提示：

0 <= x <= 2³¹ - 1

分析：

面对这道算法题目，二当家的再次陷入了沉思。
要开平方，但是不允许使用内置的指数函数，这是故意难为我胖虎。
暴力破解，反正只要整数，从 1 到 x ，一个一个试，就能找到最接近的解，很简单，但是过于简单了，一定还有更好的办法。
答案只要整数，从线性连续的数值里找最优，想到可以用二分查找法，不断尝试，二分查找的效率很高，每次都能减少一半的数据量，已经可以满意了。
但是还有一个更好的办法，答案要的是近似的整数，所以还可以使用 牛顿迭代法 ，非常适合高效找到近似解，听说效率比二分查找还高。
感觉数学还是厉害啊，很多东西都是可以用数学的方法高效解决的，虽然计算机已经很快了，但是很多时候用数学的方式去解决，可以快上加快，很想学好数学。
下面的题解都是使用 牛顿迭代法，因为是找近似解，所以需要有个度，一个停止继续的点，一般认为两次连续求得的解的差非常小的时候，就是应该停止继续循环的时候，我们这里使用 e^-7 作为两次求解的检查。
官方还有一种叫做 袖珍计算器算法 的方式，也是数学方法，这里就不赘述了。

题解：

rust：

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }

        let (c, mut x0) = (x as f64, x as f64);
        loop {
            let xi = 0.5 * (x0 + c / x0);
            if (x0 - xi).abs() < 1e-7 {
                break;
            }
            x0 = xi;
        }

        return x0 as i32;
    }
}

go：

func mySqrt(x int) int {
    if x == 0 {
		return 0
	}

	c, x0 := float64(x), float64(x)
	for {
		xi := 0.5 * (x0 + c/x0)
		if math.Abs(x0-xi) < 1e-7 {
			break
		}
		x0 = xi
	}

	return int(x0)
}

c++：

class Solution {
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 (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }

        return int(x0);
    }
};

python：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        c, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + c / x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi

        return int(x0)

java：

class Solution {
    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://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-640193.html

到了这里，关于算法leetcode｜69. x 的平方根（rust重拳出击）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！