【Leetcode】【Medium】Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

解题思路1,o(log(n)):

像这种从初始遍历查找匹配的任务,往往可以使用二分法逐渐缩小范围;

初始从0~x/2 + 1,然后逐渐以二分思想缩小查找范围。

解题思路2:

牛顿迭代法(百度百科

一些小优化:

1、不需要等到Ni * Ni 无限接近于x时,再确定Ni是返回值。

  根据牛顿迭代法图解发现,Ni+1 和 Ni不断迭代求解过程中,差距越来越小。

  当int(Ni+1) == int(Ni)时,说明迭代结果永远会处于int(Ni+1)和int(Ni+1)+1之间;

  因此,由于转换类型自动向下取整,就已经可以确定int(Ni+1)是要求的返回值;

2、初始不必设置为N0 = X,可以从N0 = X/2+1,开始迭代。注意保持N0*N0 > X,否则不仅增加了迭代次数,并且不利于编程;

 class Solution {
public:
int mySqrt(int x) {
double ans = x / + ;
int pre = int(ans);
while (ans * ans > x) {
ans = x / ( * ans) + ans / ;
if (pre == int(ans))
break;
else
pre = ans;
}
return pre;
}
};

其他注意点:

1、往往对于int间求值,多考虑int越界问题;

2、遍历查找,多考虑二分的方法;

上一篇:Android 利用内容观察者实现短信窃听


下一篇:【eclipse】mybatis配置文件创建与mapper接口文件创建