69. Sqrt(x)

题目描述和难度

  • 题目描述:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842..., 

     由于返回类型是整数,小数部分将被舍去。

思路分析

求解关键:

参考解答

参考解答1:使用二分查找,特别注意:应该返回右边端点。

class Solution:
    # 二分法
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        r = x // 2 + 1
        while l <= r:
            m = l + (r - l) // 2
            s = m * m
            if s == x:
                return m
            elif s < x:
                l = m + 1
            else:
                r = m - 1
        # 注意返回 l 和返回 r 的区别,应该返回 r
        # 【因为返回的是不超过,所要把右边界返回回去】
        return r
class Solution:
    # 二分法
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 1:
            return 1
        l = 0
        r = x // 2
        while l <= r:
            m = l + (r - l) // 2
            s = m * m
            if s == x:
                return m
            elif s < x:
                l = m + 1
            else:
                r = m - 1
        return r

参考解答2:使用牛顿法,我个人比较推荐牛顿法,更简单,返回值向下取整,就能符合题要求。

class Solution:
    # 牛顿法
    # 与系统函数作比较

    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0

        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return cur

    # 这个解直接提交到 LeetCode 上就可以了
    def mySqrt1(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0
        # 起始的时候在 1 ,这可以比较随意设置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)


if __name__ == '__main__':
    import numpy as np

    nums = np.linspace(0, 999, 100)
    solution = Solution()
    for num in nums:
        a = solution.mySqrt(num)
        b = np.sqrt(num)
        print("牛顿法:{} \t NumPy:{}\t 差距:{}".format(a, b, a - b))