题解 | #求平方根#

我的评价是坑人题

关键是结果向下取整，不能使用浮点数。

牛顿迭代法（Newton's method），也称为牛顿-拉弗森方法（Newton-Raphson method），是一种在实数域和复数域上求函数零点的迭代方法。在求解平方根时，牛顿迭代法可以被用来不断逼近真实值。

对于求解 sqrt(x)，牛顿迭代公式可以表示为：

其中，y_n 是当前迭代的猜测值，x 是我们要计算平方根的数。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param x int整型 
# @return int整型
#
class Solution:
    def sqrt(self , x: int) -> int:
        # write code here
        if x == 0 or x == 1:
            return x
        if x == 2:
            return 1
        
        y = x
        # 用2.0过不了后三个
        while y > x/y:
            y = (y + x // y) // 2
        return y