x 的平方根
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4输出: 2
示例 2:
输入: 8输出: 2说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。 这道题如果用python的开方函数那就没有意思了。所以我手动实现了一下。 我觉着这道题的思想是一个二分查找。
1 class Solution(object): 2 def mySqrt(self, x): 3 """ 4 :type x: int 5 :rtype: int 6 """ 7 if x > 1: 8 return self.search(0, x, x) 9 elif x == 1 or x == 0:10 return x11 else:12 pass13 14 def search(self, start, end, x):15 mid = int((start + end) / 2)16 mid2 = mid * mid17 mid22 = (mid + 1) * (mid + 1)18 if mid2 <= x < mid22:19 return mid20 elif mid2 > x:21 return self.search(start, mid, x)22 else:23 return self.search(mid, end, x)