leetcode 072. 求平方根

╰半橙微兮° 2023-09-28 17:49 36阅读 0赞

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4  
输出: 2  
示例 2:

输入: x = 8  
输出: 2  
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

提示:

0 <= x <= 231\-1

思路：二分

c++

class Solution {
        
    public:
        int mySqrt(int x) {
        
            long long left=0,right=x,ans,mid;
            while(left<=right){
        
                mid=left+(right-left)/2; //和 mid=(right+left)/2 等价，但是 left+right 可能会溢出
                if((long long)mid*mid<=x){
          //mid*mid 也可能会溢出，所以用 long long
                    ans=mid;
                    left=mid+1;
                }
                else
                    right=mid-1;
            }
            return ans;
        }
    };

python

class Solution:
        def mySqrt(self, x: int) -> int:
            left,right,ans=0,x,0
            while left<=right:
                mid=(left+right)//2
                if mid**2<=x:
                    ans=mid
                    left=mid+1
                else:
                    right=mid-1
            return ans

牛顿迭代：

c++:

class Solution {
        
    public:
        int mySqrt(int x) {
        
            if(x==0)  //避免后面出现分母为0的情况
                return 0;
            double x0=x,c=x,xi;
            while(1){
        
                xi=(x0+c/x0)/2;
                if(fabs(x0-xi)<1e-7)
                    break;
                x0=xi;
            }
            return x0;
        }
    };

python:

class Solution:
        def mySqrt(self, x: int) -> int:
            if x==0:
                return 0
            x0,c=float(x),float(x)
            while 1:
                xi=(x0+c/x0)/2
                if abs(xi-x0)<1e-7:
                    break
                x0=xi
            return int(x0)

牛顿迭代的式子需要理解它的原理，可以参考这篇解释的很详细的文章（写的很详细）：

[如何通俗易懂地讲解牛顿迭代法？][Link 1]

[Link 1]: https://blog.csdn.net/ccnt_2012/article/details/81837154