[LeetCode]Sqrt(x)

题目描述:

Implement int sqrt(int x).

Compute and return the square root of x.

题目大意:

实现函数 int sqrt(int x).

计算并返回x的平方根(整型)

解题思路:

题目并不要求计算sqrt(x)的精确值,只需返回小于等于sqrt(x)的最大整数即可。

方法I:二分法

Python代码:

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        low, high, mid = 0, x, x / 2
        while low <= high:
            if mid * mid > x:
                high = mid - 1
            else:
                low = mid + 1
            mid = (low + high) / 2
        return mid

方法II:牛顿迭代

参考博文:牛顿迭代法快速寻找平方根 (http://www.matrix67.com/blog/archives/361)

令f(t) = t2 - x,则sqrt(x)等价于求f(t)的根

初始假设答案t = x

每一次迭代,令t = t / 2 + x / (2 * t)

新的t值为当前t值对应的函数切线与x轴的交点横坐标,这就是牛顿迭代的本质

Python代码:

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        t = x
        while t * t > x:
            t = int(t / 2.0 + x / (2.0 * t))
        return t

 

本文链接:http://bookshadow.com/weblog/2015/08/29/leetcode-sqrtx/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码