题目

点击查看原题

给你一个非负整数x,计算并返回x算术平方根
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被舍去
注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)或者x ** 0.5

示例 1:

输入:x = 4
输出:2

示例 2:

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

提示:
0 <= x <= 2^31 - 1

方法1 二分查找

思路

二分查找解题思路

代码

class Solution {
public:
    int mySqrt(int x) {
        int l=0,r=x,ans=-1;//声明变量  left=0;right=x最大值,ans答案设置为-1
        while(l<=r)//循环判断left永远小于等于right
        {
            int mid=(r-l)/2 + l;//获取中点的值
            if((long long)mid*mid <=x) //判断每一个中点的平方是否小于等于x,若小于x则中点变为left然后继续取中点判断,直到中点的平方等于x时跳出while。  此处mid*mid只能小于等于x,不能大于等于x,因为mid是取整之后的值,是丢掉小数部分的值,所以计算结果一定比x小,如果这里写成大于等于x,则会出现错误结果比正确结果大1的情况。
            {
                ans = mid;//中点赋值给答案
                l=mid+1;//进入if说明mid平方小于或等于x,所以抛弃mid当前值,从他的下一个值继续计算,所以+1
            }
            else
            {
                r=mid-1;//进入else说明mid平方大于x,所以抛弃mid当前值,从他的前一个值继续计算,所以-1
            }
        }
         return ans;//返回循环后的结果
    }
};

方法2 牛顿迭代法

思路

牛顿迭代法思路
思路作者:LOAFER
源链接:https://leetcode.cn/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/

代码

class Solution {
public:
    int s; //定义一个保存原始数据的变量

    int mySqrt(int x) {
        s=x;//将输入的值复制一份存到s中
        if(x==0) return 0;//如果输入0,则直接输出结果
        return ((int)sqrt(x));//使用递归,直到找到答案才返回结果
    }

    double sqrt(double x) 
    {
        double res = (x+s/x)/2;//根据函数公式进行计算res的值
        if(res==x) return res;//若res等于x,则返回结果
        else return sqrt(res);//否则继续递归
    }
};
End

本文标题:LeetCode 第69题 x的平方根

本文链接:http://chisato.cn/index.php/archives/193/

除非另有说明,本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

声明:转载请注明文章来源。

最后修改:2022 年 07 月 24 日 06 : 46 PM
如果觉得我的文章对你有用,请随意赞赏