69.x的平方根 (平)(简单)

实现 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)牛顿迭代法。

上一篇:如何新建XCode项目


下一篇:[CareerCup] 14.3 Final Finally Finalize 关键字比较