LeetCode 69. x 的平方根

深碍√TFBOYSˉ_ 2022-03-26 14:48 357阅读 0赞
  1. x 的平方根

题目

  1. 实现 int sqrt(int x) 函数。
  3. 计算并返回 x 的平方根，其中 x 是非负整数。
  5. 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
  7. 示例 1:
  9. 输入: 4
  10. 输出: 2
  11. 示例 2:
  13. 输入: 8
  14. 输出: 2
  15. 说明: 8 的平方根是 2.82842..., 
  16.      由于返回类型是整数，小数部分将被舍去。

解法

  1. 二分法，求到 left-right < 你想要的精确度，本题结果需要 返回int

    class Solution:

    1. def mySqrt(self, x):
    2.     if x ==0 : return  0
    3.     left, right = 1,x
    4.     while left <= right:
    5.         mid =  float((left + right) / 2)
    6.         print(mid)
    7.         if mid * mid == x or abs(left - right) <= 0.001:
    8.             return  mid
    9.         elif mid * mid < x:
    10.             left = mid
    11.         else:
    12.             right = mid

  2. 由 牛顿迭代公式 可得 r = (r + x // r ) // 2 ，r在5，6次后就会趋向 y=x2 的根

    class Solution:

    1. def mySqrt(self, x):
    2.     if x == 0 or x == 1: return  x
    3.     r = x 
    4.     while r  > x / r:
    5.         r = (r + x // r ) // 2
    6.     return int(r)

提交记录

执行用时: 68 ms, 在Sqrt(x)的Python3提交中击败了89.87% 的用户

发表评论

表情：
评论列表 （有 0 条评论，357人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode69 x的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1:

    朱雀朱雀/ 0 赞/ 246 阅读

    相关 【LeetCode 69】x的平方根

    题目描述 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

    怼烎@怼烎@/ 0 赞/ 187 阅读