算法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 <= 231 - 1

分析：

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

题解：

rust：

implSolution{pubfnmy_sqrt(x:i32)->i32{if x ==0{return0;}let(c,mut x0)=(x asf64, x asf64);loop{let xi =0.5*(x0 + c / x0);if(x0 - xi).abs()<1e-7{break;}
            x0 = xi;}return x0 asi32;}}

go：

funcmySqrt(x int)int{if x ==0{return0}

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

c++：

classSolution{public:intmySqrt(int x){if(x ==0){return0;}double c = x, x0 = x;while(true){double xi =0.5*(x0 + c / x0);if(fabs(x0 - xi)<1e-7){break;}
            x0 = xi;}returnint(x0);}};

python：

classSolution:defmySqrt(self, x:int)->int:if x ==0:return0

        c, x0 =float(x),float(x)whileTrue:
            xi =0.5*(x0 + c / x0)ifabs(x0 - xi)<1e-7:break
            x0 = xi

        returnint(x0)

java：

classSolution{publicintmySqrt(int x){if(x ==0){return0;}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/ 博客原创~