LeetCode 70. Climbing Stairs.jpg
LeetCode 70. Climbing Stairs
Description
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
描述
实现int sqrt（int x）.
计算并返回x的平方根，其中x保证为非负整数.
由于返回类型是整数，因此将截断十进制数字，并仅返回结果的整数部分.
思路
- 对一个数实现开方，并返回其整数部分
- 此题目使用二分法.
- 我们初始化left,right,middle = 0,x,x>>1(位运算，等同于x/2，位运算速度更快).
- 如果middle*middle < x,说明sqrt(x)在[middle,right]之间，我们更新left==middle，middle == left + ((right - left)>>1).
- 如果middle*middle > x，说明sqrt(x)在[left,middle]之间，我们更新right == millde,middle = left + ((right - left)>>1).
- 结束条件:当middlemiddle <= x <(middle+1)(midddle+1)时，返回middle.
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
# 如果输入是1，则直接返回1
if x == 1:
return 1
# 左边界，右边界，中间值，注意位运算9>>1=4,为整型
left, right, middle = 0, x, x >> 1
while True:
# 对中间的值求平方
multi = middle*middle
# 如果平方小于x，说明sqrt(x)在[middle,right]之间
if multi < x:
left = middle
# 如果平方大于x，说明sqrt(x)在[left,middle]之间
elif multi > x:
right = middle
# 求middle+1的平方
intmultib = (middle+1)*(middle+1)
# 如果x落在了[middle,middle+1)之间，结束循环，返回middle
if multi <= x < intmultib:
return middle
middle = left+((right-left) >> 1)
if __name__ == "__main__":
so = Solution()
res = so.mySqrt(190983754751)
print(res)
