当前位置:网站首页>leetcode 072. 求平方根
leetcode 072. 求平方根
2022-08-03 20:06:00 【会编程的露娜】
给定一个非负整数 x ,计算并返回 x 的平方根,即实现 int sqrt(int x) 函数。
正数的平方根有两个,只输出其中的正数平方根。
如果平方根不是整数,输出只保留整数的部分,小数部分将被舍去。
示例 1:
输入: x = 4
输出: 2
示例 2:
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…,由于小数部分将被舍去,所以返回 2
提示:
0 <= x <= 231-1
思路:二分
c++
class Solution {
public:
int mySqrt(int x) {
long long left=0,right=x,ans,mid;
while(left<=right){
mid=left+(right-left)/2; //和 mid=(right+left)/2 等价,但是 left+right 可能会溢出
if((long long)mid*mid<=x){
//mid*mid 也可能会溢出,所以用 long long
ans=mid;
left=mid+1;
}
else
right=mid-1;
}
return ans;
}
};
python
class Solution:
def mySqrt(self, x: int) -> int:
left,right,ans=0,x,0
while left<=right:
mid=(left+right)//2
if mid**2<=x:
ans=mid
left=mid+1
else:
right=mid-1
return ans
牛顿迭代:
c++:
class Solution {
public:
int mySqrt(int x) {
if(x==0) //避免后面出现分母为0的情况
return 0;
double x0=x,c=x,xi;
while(1){
xi=(x0+c/x0)/2;
if(fabs(x0-xi)<1e-7)
break;
x0=xi;
}
return x0;
}
};
python:
class Solution:
def mySqrt(self, x: int) -> int:
if x==0:
return 0
x0,c=float(x),float(x)
while 1:
xi=(x0+c/x0)/2
if abs(xi-x0)<1e-7:
break
x0=xi
return int(x0)
牛顿迭代的式子需要理解它的原理,可以参考这篇解释的很详细的文章(写的很详细):
边栏推荐
猜你喜欢
随机推荐
WPF .cs中使用资源文件中的ControlTemplate或Style并找到控件
若依集成browscap读取浏览器用户代理
ARMuseum
边缘盒子+时序数据库,美的数字化平台 iBuilding 背后的技术选型
子树的大小
Internet Download Manager简介及下载安装包,IDM序列号注册问题解决方法
开源生态研究与实践| ChinaOSC
力扣203-移除链表元素——链表
CLIP论文解读
详解AST抽象语法树
ESP8266-Arduino编程实例-MCP4725数模转换器驱动
子结点的数量(2)
LeetCode 622. 设计循环队列
ES6-箭头函数
使用 ReportLab 绘制 PDF
高并发,你真的理解透彻了吗?
YARN功能介绍、交互流程及调度策略
JWT详解
Pytorch GPU 训练环境搭建
EasyCVR平台海康摄像头语音对讲功能配置的3个注意事项