LeetCode|LeetCode 69. x 的平方根(Sqrt(x)) LeetCode69.x的平方根(Sqrt(x))

文章图片
LeetCode.jpg 69. x 的平方根实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
【LeetCode|LeetCode 69. x 的平方根(Sqrt(x))】示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
Python3实现二分查找

# @author:leacoder # @des: 二分查找 , x 的平方根class Solution: def mySqrt(self, x: int) -> int: if x == 1 or x == 0: return x left,right,res = 0,x,0 while left <= right: mid = int((left + right)/2) if mid * mid > x: right = mid - 1 elif mid *mid < x: left = mid + 1 res = mid else: return int(mid) return int(res)

牛顿迭代

# @author:leacoder # @des: 牛顿迭代 , x 的平方根 # 参看 https://www.cnblogs.com/qlky/p/7735145.htmlclass Solution: def mySqrt(self, x: int) -> int: if x <= 1: return x r = x while r * r > x: r = int((r + x / r) /2) return r

神秘的常数 0x5f3759df 0x5f375a86

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

GitHub链接：
https://github.com/lichangke/LeetCode
知乎个人首页：
https://www.zhihu.com/people/lichangke/
个人首页：
https://www.jianshu.com/u/3e95c7555dc7
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习