首页 > 其他 > 详细

leetcode 每日一题 69. x 的平方根

时间:2020-06-09 23:39:10      阅读:40      评论:0      收藏:0      [点我收藏+]

技术分享图片

二分法

思路:

从0到x不断二分尝试。

代码:

 

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

 

牛顿法

思路:

做方程y = x2 - C,C为题目中的非负整数x,则题目变为求方程图像在x正半轴上的交点xi的值。从xi=C开始,做当前点切线与x轴交点为xi+1,当xi和xi+1差值逼近于一个足够小的值时,xi+1为所求答案,否则xi=xi+1,继续迭代。

 

代码:

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        
        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C / x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi
        
        return int(x0)

  

 

leetcode 每日一题 69. x 的平方根

原文:https://www.cnblogs.com/nilhxzcode/p/13081526.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!