欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode: sqrtx [x 的平方根] 二分法、递归法

程序员文章站 2022-06-17 19:21:34
...
'''
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。
'''

看到这个题目,好像没啥思路,然后去 Google 了一下求平方根的算法:

For a natural number x (i.e. x ∈ {0,1,2,3,...}),
the integer square root of x is defined as the natural number r such that r**2 ≤ x < (r + 1)**2.
It is the greatest r such that r**2 ≤ x, or equivalently, the least r such that (r + 1)**2 > x.

我第一想到的是用 二分法 来实现,我的解法:

# Python3
class Solution:
    def average(self, x, y):
        return (x + y) / 2

    def mySqrt(self, x: int) -> int:
        smaller, bigger = 1, x
        middle = self.average(smaller, bigger)
        while True:
            if middle ** 2 > x:
                bigger = middle
                middle = self.average(smaller, middle)
            else:
                smaller = middle
                middle = self.average(middle, bigger)
            if x <= middle ** 2 < x + 1:
                break
        return middle // 1

if __name__ == '__main__':
    s = Solution()
    assert s.mySqrt(1) == 1
    assert s.mySqrt(4) == 2
    assert s.mySqrt(8) == 2
    assert s.mySqrt(9) == 3

在leetcode上提交结果:
leetcode: sqrtx [x 的平方根] 二分法、递归法


搜索到另一种方法,通过推理发现规律,然后使用递归法:
leetcode: sqrtx [x 的平方根] 二分法、递归法
可以看出,x 的平方根和 x-1 的平方根有关系,有时候它们相同,有时候后者比前者多1。因此,可以写一个递归算法。(不过此算法在leetcode上提交后超时了)

# Python3
class Solution:
    def mySqrt(self, x):
        if x == 0:
            return 0
        else:
            r2 = self.mySqrt(x - 1)
            r3 = r2 + 1
            if x < r3 ** 2:
                return r2
            else:
                return r3

还有其他更优的方法,能力有限,看不懂了,毕竟是 Cornell University 的网站上的。

Reference (需要能使用Google才能访问,so …)