[LeetCode] 69. Sqrt(x) 求平方根
Implement int sqrt(int x)
.
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
这道题要求我们求平方根,我们能想到的方法就是算一个候选值的平方,然后和x比较大小,为了缩短查找时间,我们采用二分搜索法来找平方根,这里属于博主之前总结的 LeetCode Binary Search Summary 二分搜索法小结 中的第三类的变形,找最后一个不大于目标值的数,这里细心的童鞋可能会有疑问,在总结贴中第三类博主的 right 用的是开区间,那么这里为啥 right 初始化为x,而不是 x+1 呢?因为总结帖里的 left 和 right 都是数组下标,这里的 left 和 right 直接就是数字本身了,一个数字的平方根是不可能比起本身还大的,所以不用加1,还有就是这里若x是整型最大值,再加1就会溢出。最后就是返回值是 right-1,因为题目中说了要把小数部分减去,只有减1才能得到正确的值,代码如下:
解法一:
class Solution {
public:
int mySqrt(int x) {
if (x <= ) return x;
int left = , right = x;
while (left < right) {
int mid = left + (right - left) / ;
if (x / mid >= mid) left = mid + ;
else right = mid;
}
return right - ;
}
};
这道题还有另一种解法,是利用牛顿迭代法,记得高数中好像讲到过这个方法,是用逼近法求方程根的神器,在这里也可以借用一下,可参见网友 Annie Kim's Blog的博客,因为要求 x2 = n 的解,令 f(x)=x2-n,相当于求解 f(x)=0 的解,可以求出递推式如下:
xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2
解法二:
class Solution {
public:
int mySqrt(int x) {
if (x == ) return ;
double res = , pre = ;
while (abs(res - pre) > 1e-) {
pre = res;
res = (res + x / res) / ;
}
return int(res);
}
};
也是牛顿迭代法,写法更加简洁一些,注意为了防止越界,声明为长整型,参见代码如下:
解法三:
class Solution {
public:
int mySqrt(int x) {
long res = x;
while (res * res > x) {
res = (res + x / res) / ;
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/69
类似题目:
参考资料:
https://leetcode.com/problems/sqrtx/description/
https://leetcode.com/problems/sqrtx/discuss/25130/My-clean-C++-code-8ms
https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution
https://leetcode.com/problems/sqrtx/discuss/25057/3-4-short-lines-Integer-Newton-Every-Language
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- 【.net 深呼吸】细说CodeDom(8):分支与循环
- android源码环境下用mmm/mm编译模块,输出编译log到文件的方法
- [Android]仿新版QQ的tab下面拖拽标记为已读的效果
- zip文件jQuery工作地点选择城市代码
- Javascript基础系列之(五)条件语句(if条件语句)
- ytu 2030: 求实数绝对值(水题)
- 20145235 《Java程序设计》第8周学习总结
- Labview实现频率调制(FM)
- 在windows下用FTP命令上传文件到Linux
- js中的this怎么理解
- statspack系列4
- 今天给大家分享一下Android中的资源与国际化的问题
- iOS监听电话事件
- jquery事件之event.target用法详解
- infiniband学习总结
- Docker入门之五数据管理
- vue数组语法兼容问题
- 关于new Date()
- NET4.6下的UTC时间转换
- 我是如何用redis做实时订阅推送的
热门文章
- oracle聚合函数XMLAGG用法简介
- 使用selenium爬虫抓取数据
- CSS选择器[attribute | = value] 和 [attribute ^ = value]的区别
- vuex源码分析(二) state及strict属性 详解
- redis命令之 ----List(列表)
- Java &; PHP RSA 互通密钥、签名、验签、加密、解密
- CD 基金会、Jenkins、Jenkins X、Spinnaker 和 Tekton 的常问问题
- C++回调,函数指针
- ArcGIS Server JavaScript API中ESRI字体下载
- ASP.NET MVC 中的过滤器