LeetCode 69. Sqrt(x)(c++实现)
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.
解法:
使用了二分查找
定义left right mid
class Solution {
public:
int mySqrt(int x)
{
if (x <= 0)
return 0;
int left, right, mid;
left = 1;
right = x;
// mid = left + (right - left) / 2; //定义为加(left+right)/2则会出错 原因是整形溢出
while (left <= right)
{
mid = left + (right - left) / 2;
if (mid > x / mid)
right = mid - 1;
else if (mid < x / mid)
left = mid + 1;
else
return mid;
//mid = left + (right - left) / 2;
//mid =(left+right)/2;
}
return right;//注意必须为right
}
};
标准的二分法:
参考:【1】https://www.jianshu.com/p/f1d4a1a8efd2
【2】 https://blog.****.net/lu597203933/article/details/44851777
该解法不错:
二分
class Solution {
public:
int mySqrt(int x)
{
double begin = 0;
double end = x;
double result = 1;
double mid = 1;
while(abs(result-x) > 0.000001)
{
mid = (begin+end)/2;
result = mid*mid;
if(result > x) // 二分的范围
end = mid;
else
begin = mid;
}
return (int)mid;
}
};
牛顿迭代法:
设r是f(x) = 0的根,选取x0作为r初始近似值,过点(x0,f(x0))做曲线y = f(x)的切线L,L的方程为y = f(x0)+f'(x0)(x-x0),求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0),称x1为r的一次近似值。过点(x1,f(x1))做曲线y = f(x)的切线,并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1),称x2为r的二次近似值。重复以上过程,得r的近似值序列,其中x(n+1)=x(n)-f(x(n))/f'(x(n)),称为r的n+1次近似值,上式称为牛顿迭代公式。
定义问题,
设f(x)=x^2-x* 目标是让f(x)逼近0
由x(n+1)=x(n)-f(x(n))/f'(x(n))
可知:x(n+1)=x(n)-{x(n)^2-x*}/2x(n)
=x(n)/2+x*/2x(n)
其中的x*为本题的x(n)表示前一次的值
class Solution {
public:
int mySqrt(int x)
{
//*牛顿迭代法*/
double pre = 0;
double cur = x;
while(abs(cur - pre) > 0.000001)
{
pre = cur;
cur = (pre/2 + x/(2*pre));
}
return int(cur);
}
};