leetcode.69:x的平方根

简介: leetcode.69:x的平方根

题目描述:


实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


示例1:


输入: 4
输出: 2


示例2:


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


题目难度:简单


分析:


对于牛顿迭代法百度百科是这么介绍的:


牛顿迭代法(Newton’s method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。


这里就不细说了,感兴趣的可以自己查查资料。


代码如下:


java:


class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        long sqrt = x;
        while (sqrt * sqrt > x){
            sqrt = (sqrt + x / sqrt) / 2;
        }
        return (int)sqrt;
    }
}


python:


class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        c = x
        while c * c > x:
            c = (c + x // c) // 2
        return c


总结:


题目不是很难,如果知道这个方法就比较简单,如果不知道也可以用笨方法:取n=1,然后平方看看是否大于x,如大于就返回n-1,如小于等于就n++即可,代码就不写了。

目录
相关文章
|
1月前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
1月前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
12 1
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
2月前
【力扣】69. x 的平方根
【力扣】69. x 的平方根
|
9月前
【Leetcode-67. 二进制求和-69.x的平方根】
【Leetcode-67. 二进制求和-69.x的平方根】
26 0
|
2月前
leetcode-69:x 的平方根
leetcode-69:x 的平方根
41 0
|
10月前
|
存储
leetcode:69. x 的平方根
利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。
65 0
YI
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
71 0
力扣69x的平方根
力扣69x的平方根
44 0
|
前端开发 Go 对象存储
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串
【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串