【 Sqrt(x) 】cpp
2024-09-05 07:09:13
题目：
Implement int sqrt(int x).
Compute and return the square root of x.
代码：
class Solution {
public:
int mySqrt(int x)
{
if (x<) return x;
int l = ;
int r = x/;
while (l<=r)
{
int mid = (l+r)/;
if ( x / mid < mid )
{
r = mid - ;
}
else if ( x / mid > mid )
{
l = mid + ;
}
else
{
return mid;
}
}
return l-;
}
};
tips：
这个题一开始拿到感觉怪怪的，直接看的solution。
比如输入400，记录mid的结果如下：
100
50
25
12
18
21
19
20
这种虽然产生了震荡，但是震荡必然越来越小，而且每次变化的长度至少是上一次的一半，时间复杂度也确实是O(logn).
有个细节，如果没有整数的平方数，最后会推出循环；而退出循环时，一定是从l - r = 1，因此取l-1返回即可。
=====================================================
第一次过的时候有误区，binary search本来就是震荡的过程，第二次过按照第一次的代码写了一遍。
class Solution {
public:
int mySqrt(int x) {
if ( x< ) return x;
int l = ;
int r = x/;
while ( l<=r )
{
int mid = (l+r)/;
if ( x/mid == mid )
{
return mid;
}
else if ( x/mid > mid )
{
l = mid+;
}
else
{
r = mid-;
}
}
return l-;
}
};
最新文章
- java基础学习总结-接口
- slave IO流程之一：mysql登陆过程（mysql_real_connect）
- 让服务器iis支持.apk文件下载的设置方法
- .net版本发展历史
- matlab之meshgrid()函数
- javaee添加验证码
- Wireshark - 过滤规则
- cubietruck+ vncserver+source+wlan0 分类： cubieboard 2014-11-08 17:25 159人阅读 评论(0) 收藏
- Mybatis中javaType和jdbcType对应和CRUD例子
- css y轴溢出滚动条，x轴溢出显示
- window下maven的环境搭建
- Hbase学习03
- hdu 1276士兵队列问题【queue】
- mysql中建立索引的一些原则
- LVS基础知识
- html 之 padding,margin
- leetcode-algorithms-17 Letter Combinations of a Phone Number
- css实现图片横向排列滚动
- 【Eclipse】eclipse生成类图、类交互图、包依赖图
- 源码编译运行android emulator