开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode 69. x 的平方根

简介: LeetCode 69. x 的平方根
+关注继续查看

69. x 的平方根


https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/


实现 int sqrt(int x) 函数。


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


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


示例 1:


输入: 4
输出: 2


示例 2:


输入: 8
输出: 2


说明: 8 的平方根是 2.82842…,由于返回类型是整数,小数部分将被舍去。


题解


方法一:牛顿迭代法


下面这种方法可以很有效地求出根号 aa 的近似值:首先随便猜一个近似值 xx,然后不断令 xx 等于 xx 和 a/xa/x 的平均数,迭代个六七次后 xx 的值就已经相当精确了。


例如,我想求根号 22 等于多少。假如我猜测的结果为 44,虽然错的离谱,但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 22 了:


( 4 + 2/ 4 ) / 2 = 2.25


( 2.25 + 2/ 2.25 ) / 2 = 1.56944…


( 1.56944…+ 2/1.56944…) / 2 = 1.42189…


( 1.42189…+ 2/1.42189…) / 2 = 1.41423…


….


如果所示:


image


image


代码


(ps:一开始不要脸的写了个math中的 sqrt函数 看了大佬写的题解,感觉几年数学白学 T^T)


class Solution {
public:
    int s;
    int mySqrt(int x) {
        s=x;
        if(x==0) 
            return 0;
        return ((int)(Sqrt(x)));
    }
    double Sqrt(double x){
        double res=(x+s/x)/2;
        if(res==x)
            return x;
        else
            return Sqrt(res);
    }
};


简写:


int mySqrt(int a) {
    long x = a;
    while (x * x > a) {
        x = (x + a / x) / 2;
    }
    return x;
}


方法二:二分法


image


int mySqrt(int a) {
    if (a == 0) 
        return a;
    int l = 1, r = a, mid, sqrt;
    while (l <= r) {
        mid = l + (r - l) / 2;
        sqrt = a / mid;
        if (sqrt == mid) {
            return mid;
        } else if (mid > sqrt) {
            r = mid - 1;
        } else {
            l = mid + 1;
        } 
    }
    return r;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode-69. x的平方根(day15)
LeetCode-69. x的平方根(day15)
35 0
LeetCode刷题1929-简单-数组串联
LeetCode刷题1929-简单-数组串联
48 0
【LeetCode16】最接近的三数之和(双指针)
和leetcode15三数之和类似,三层循环时间复杂度O ( n 3 ) O(n^3)O(n 3 )过高,使用双指针虽说不能马上降到O ( n ) O(n)O(n),但就是这类题的常用套路: 遍历一遍数组元素,当前元素为num[i];
18 0
Leetcode --- 数组(双指针)
Leetcode --- 数组(双指针)
22 0
LeetCode刷题(13)【简单】最大子序和(C++)
LeetCode刷题(13)【简单】最大子序和(C++)
24 0
【小Y学算法】⚡️每日LeetCode打卡⚡️——21.x 的平方根
📢前言 🌲原题样例 🌻C#方法:二分查找 🌻Java 方法一:二分法 🌻Java 方法二:牛顿迭代 💬总结 🚀往期优质文章分享
33 0
【LeetCode328】奇偶链表
时间复杂度O(n)即遍历一遍链表,奇偶指针odd循环链表,奇数指针不断串连奇数节点,偶数指针even不断串连偶数节点,最后奇数指针的结尾连接偶数节点的开始。
14 0
【LeetCode328】奇偶链表
时间复杂度O(n)即遍历一遍链表,奇偶指针odd循环链表,奇数指针不断串连奇数节点,偶数指针even不断串连偶数节点,最后奇数指针的结尾连接偶数节点的开始。
18 0
「LeetCode」JavaScript-插入排序⚡️
「LeetCode」JavaScript-插入排序⚡️
15 0
「LeetCode」78-子集⚡️
「LeetCode」78-子集⚡️
22 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载