实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
自我解答:
首先拿到题目想到的用m*m=x的方式获取平方根,然后返回m。
但是问题是不知道从什么地方开始遍历。
分析所有的平方根,除了1和0,之外,其他所有的平方根都小于该数,所以思路如下:
使用for循环遍历从0到x的整数,将每个整数都与自己相乘,如果大于,或等于x,返回该数。
但是题目要求向下取整,所以结果应该是小于x的,所以需要再结果上-1,
而恰好有整数平方根的整数就不能得到正确的平方根,所以在判断条件上去掉=,算法如下:
class Solution:
def mySqrt(self, x: int) -> int:
if x==0:
return 0
if x==1:
return 1
for i in range(x+1):
if i * i>x:
return i-1
实际解答:
这道题目的标签是数字,二分法,所以正确解答应该是使用二分法。
在x-0中,频繁使用中间数的向下取整数的平方与x对比(原作者是x/m<m),大于则将中间数赋值给max,小则赋值给min,直到两数相差为1时,输出其min。
class Solution:
def mySqrt(self, x):
if x ==1:
return 1
min = 0
max = x
while max-min > 1:
m = (max + min)//2
if m *m >x:
max = m
else:
min = m
return min
未理解:
(1)0x5f3759df
(2)牛顿迭代法。