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

上周题目难度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 原创出品，欢迎转载，转载时请注明出处!