每周一道算法题(五十二)

上周题目难度Hard，就没做。本周题目难度'Easy'，使用语言'Python'

题目：求一个数的平方根，精确到整数即可。

思路：追求简单的直接return int(math.sqrt(x))就行了，这里我们用牛顿迭代法来做。原则就是Xn与Xn+1的差值小于0.00001(不同的精度数值不一样)即可。Xn与Xn+1的关系是Xn+1 = Xn * 0.5 + X / (2 * Xn)，知道这两条就很简单了。

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if (x <= 1): return x
        # 定义Xn与Xn+1
        x1 = 1
        x2 = x1 * 0.5 + x / (2 * x1)
        # 满足精度返回结果即可
        while(abs(x1 - x2) > 0.00001):
            x1 = x2
            x2 = x1 * 0.5 + x / (2 * x1)
        return int(x1)

效率尚可，这题还可以用二分法，泰勒展开等来做。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!