Leetcode -- x的平方根(69)

题目描述:实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例:输入 8    输出2

具体思路:

思路一:二分法。任何一个大于2的数x,其平方根一定小于x/2。因此使用二分法。

 1 class Solution:
 2     def mySqrt(self, x: int) -> int:
 3         if x < 2:
 4             return x
 5         left,right = 0,x
 6         while(left <= right):
 7             mid = (left+right)//2     #//向下取整除法
 8             if mid * mid == x:
 9                 return mid
10             if mid * mid > x:
11                 right = mid -1
12             else:
13                 left = mid + 1
14         return right
15             

时间复杂度:O(logn)    空间复杂度O(1)

思路二:以下思路均是参考了题解,比较偏向于数学。思路二采用递归方法+位运算。

Leetcode -- x的平方根(69)   这里用位运算来表示乘以2和除以2是十分巧妙的。

 

1 class Solution:
2     def mySqrt(self, x: int) -> int:
3         if x < 2:
4             return x
5         left = self.mySqrt(x >> 2) << 1    #在这里进行递归运算
6         right = left+1     #这里很容易忽视,报错后才想到这一点
7         return left if right * right > x else right
8             

思路三:牛顿法。怪巧妙的。

Leetcode -- x的平方根(69)

 

 

 1 class Solution:
 2     def mySqrt(self, x: int) -> int:
 3         if x < 2:
 4             return x
 5         x0 = x
 6         x1 = (x0 + x/x0) / 2
 7         while abs(x0-x1)>= 1:      #因为最后的结果为整数,不同整数至少相差1
 8             x0 = x1
 9             x1 = (x0 + x/x0) / 2    #迭代公式
10         return int(x1)

 

上一篇:2019年下半年信息系统项目管理师(高级)上午计算题-69


下一篇:[leetcode]69