我要招人

去企业版

首页 > 试题广场 >

求平方根

[编程题]求平方根

热度指数：158545 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现函数 int mysqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： $0 <= x < 2^{31}-1$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logx)$

示例1

输入

输出

示例2

输入

2143195649

输出

算法知识视频讲解

查看答案及解析

Python

木子梨丶

import math
class Solution:
    def mysqrt(self , x ):
        # write code here
        return int(math.mysqrt(x))

发表于 2022-08-04 17:27:37 回复(0)

Python

牛客961048420号

#
#
# @param x int整型
# @return int整型
#
class Solution:
def mysqrt(self , x ):
# write code here
y=x**0.5
return int(y)

发表于 2022-04-02 23:22:06 回复(0)

Python

wengJJ

Python

牛顿法求平方根公式：

$x_{k+1}=\frac{1}{2}(x_k+\frac{n}{x_k})$ 其中x为目标平方根, n为输入数

#
# 
# @param x int整型 
# @return int整型
#
class Solution:
    def mysqrt(self , x ):
        # write code here
#         二分查找
#         if x==1 or x==0:
#             return x
#         high = x
#         low = 0
#         mid = (high+low)/2
#         while abs(mid*mid - x) > 0.01:
#             if mid*mid>x:
#                 high,mid = mid,(high+low)/2
#             else:
#                 low,mid = mid,(high+low)/2
#         return int(mid)
#         牛顿法
        if x==1 or x==0:
            return x
        sqr = x/2
        while abs(sqr*sqr - x)>0.01:
            sqr = (sqr+x/sqr)/2
        return int(sqr)

编辑于 2021-04-19 12:13:25 回复(0)

Python

贝贝201903021107589

# 
# @param x int整型 
# @return int整型
#牛顿迭代法求平方根
class Solution:
    def mysqrt(self , x ):
        # write code here
        a=1.0
        while abs(a*a-x)>1e-6:
            a=(a+x/a)/2
        return a

# @param x int整型 
# @return int整型
#不知道可不可以的直接法
class Solution:
    def mysqrt(self , x ):
        # write code here
        a=int(x**(1/2))
        return a

编辑于 2021-04-07 20:45:29 回复(0)

Python

牛客208065635号

python 解法：牛顿迭代法

class Solution:
    def mysqrt(self , x ):
        # write code here
        n = 1
        while abs(n ** 2 - x) > 1e-5:
            n = n - (n ** 2 - x) / (2 * n)
        return int(n)

编辑于 2021-03-13 17:43:58 回复(0)

Python

Leo_Ye

class Solution:
    def mysqrt(self , x ):
        # write code here
        return int(x**0.5)

偷偷问一句，这样算不算作弊？一句返回值。。

发表于 2021-02-24 13:10:36 回复(0)

Python

崔崔呀

看了一圈很少有用python求解的，而且步骤很简洁的，那我就来贡献下啦：

根据，平方数的性质-连续n个奇数相加的结果一定是n的平方数。so

我们代码入下：

class Solution:
def mysqrt(self , x ):
# write code here
#根据平方数的性质-连续n个奇数相加的结果一定是n的平方数
k=1
num=0
while (x>=0):
x-=k
k+=2
num+=1
return num-1

发表于 2021-01-23 22:32:01 回复(0)

Python

fromnow

pycharm 运行没问题啊~这里测试不通过，error：mysqrt() takes 1 positional argument but 2 were given，求大神指点

def mysqrt(x):

l = 0
r = x
mid = (r+l)/2
while abs(mid**2 - x) > 0.0001:
if mid**2 - x >0:
r = mid
mid = (l+r)/2
else:
l = mid
mid = (l+r)/2
if (int(mid)+1)**2 == x:
return int(mid)+1
else:
return int(mid)

发表于 2020-12-10 14:00:16 回复(0)

Python

牛客344478146号

牛顿迭代法

class Solution:
def mysqrt(self , x ):
# write code here
if x==0:
return 0
C,x0=x,x
while True :
xi=0.5*(x0+C/x0)
if abs(x0-xi)<1e-7 :
break
x0=xi
return int(x0)

编辑于 2020-11-07 16:56:43 回复(0)

Python

黄沙遮天

分治法就是二分法的思想解决问题，通过进行判断所求值和mid的关系，来进行左右的递归查找，只是在最后返回结果中需要注意，因为low对应的值可能也大于我们要求的值，所以最后还有一个判断，如果大于的话，a就减去1作为根值

class Solution:
    def equal(self,low,high,m):
        if low>=high:
            return low
        mid=(high-low)//2+low
        if mid**2==m:
            return mid
        elif mid**2<m:
            return self.equal(mid + 1, high, m)
        else:
            return self.equal(low, mid - 1, m)
    def mysqrt(self , x ):
        # write code here
        if x<=0:
            return 0
        low=1
        high=x
        a=self.equal(low,high,x)
        if a**2>x:
            a-=1
        return a

发表于 2020-07-18 21:07:59 回复(0)