leetcode x 的平方根 python
2021-07-03 08:06
标签：思想 查找 class python tran tco 说明 ati 示例 实现 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 示例 2: leetcode x 的平方根 python 标签：思想 查找 class python tran tco 说明 ati 示例 原文地址：https://www.cnblogs.com/Lin-Yi/p/9623590.htmlint sqrt(int x) 函数。输入: 4
输出: 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 x
11 else:
12 pass
13
14 def search(self, start, end, x):
15 mid = int((start + end) / 2)
16 mid2 = mid * mid
17 mid22 = (mid + 1) * (mid + 1)
18 if mid2 mid22:
19 return mid
20 elif mid2 > x:
21 return self.search(start, mid, x)
22 else:
23 return self.search(mid, end, x)