当前位置:网站首页>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)
牛顿迭代的式子需要理解它的原理,可以参考这篇解释的很详细的文章(写的很详细):
边栏推荐
- Alexa染料标记RNA核糖核酸|RNA-Alexa 514|RNA-Alexa 488|RNA-Alexa 430
- Benchmarking Lane-changing Decision-making for Deep Reinforcement Learning
- List类的超详细解析!(超2w+字)
- 演讲议题及嘉宾重磅揭晓,TDengine 开发者大会推动数据技术“破局”
- 【微信小程序2】事件传参与数据同步[03]
- 【飞控开发高级教程3】疯壳·开源编队无人机-定高、定点、悬停
- 8.3模拟赛总结
- Pytorch GPU 训练环境搭建
- 揭秘5名运维如何轻松管理数亿级流量系统
- PHP according to the longitude and latitude calculated distance two points
猜你喜欢
随机推荐
ES6-箭头函数
微导纳米IPO过会:年营收4.28亿 君联与高瓴是股东
622 设计循环队列——Leetcode天天刷【循环队列,数组模拟,双指针】(2022.8.2)
化算力为战力:宁夏中卫的数字化转型启示录
使用 ReportLab 绘制 PDF
嵌入式分享合集27
1161 最大层内元素和——Leetcode天天刷【BFS】(2022.7.31)
RNA核糖核酸修饰Alexa 568/[email protected] 594/[email prote
若依集成easyexcel实现excel表格增强
利用net-snmp的库实现snmpget,snmpset
RNA-ATTO 390|RNA-ATTO 425|RNA-ATTO 465|RNA-ATTO 488|RNA-ATTO 495|RNA-ATTO 520近红外荧光染料标记核糖核酸RNA
第三方验收测试报告有什么作用?如何获取权威软件测试报告?
基础软件与开发语言开源论坛| ChinaOSC
盲埋孔PCB叠孔设计的利与弊
高位套牢机构,用友网络的信任危机是如何产生的?
net-snmp私有mib动态加载到snmpd
PHP according to the longitude and latitude calculated distance two points
钱江摩托某型号产品ECU货不对版 消费者知情权应如何保障?
ERROR: You don‘t have the SNMP perl module installed.
收藏-即时通讯(IM)开源项目OpenIM-功能手册