LeetCode 69—— x 的平方根

本文主要是介绍LeetCode 69—— x 的平方根，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 解题思路一

二分查找法，对于整数 $i\in [0,x]$，我们判断 $i^2$ 和 $x$ 的关系，然后找到最后一个平方小于等于 $x$ 的整数即可。

需要注意，为了避免求平方的时候整数溢出，需要选用 long long 类型。

另外，$(\frac{x}{2}{)}^2=\frac{1}{4}{x}^2>x$，当 $x>4$ 的时候均成立，但由于我们这里求的是整数，所以则是当 $x>5$ 的时候我们可以将搜索区间缩短为 $i\in [0,x/2]$。

3. 代码实现一

class Solution {
public:int mySqrt(int x) {int left = 0;int right = x;if (x > 5) {right = x / 2;}while (left <= right) {int mid = left + (right - left) / 2;long long target = (long long)mid * mid;if (target < x) {left = mid + 1;} else if (target > x) {if ( (long long)(mid-1) * (mid-1) <= x) {return mid-1;} else {right = mid - 1;}} else {return mid;}}return right;}
};

4. 解题思路二

实际上，我们所求的即是方程 $f(a)=a^2-x=0$ 的值，我们可以用牛顿迭代法来求解。

假设初始值为 $a_0,f(a_0)=a_0^2-x$，切线斜率为 $2a_0$，那么切线的方程为：

$$y=2a_0(z-a_0)+(a_0^2-x)$$

切线与 $x$ 轴的交点为，$z=\frac{1}{2}{a}_0+\frac{x}{2a_0}$。

这样，我们继续在 $a_1=z$ 处作新的切线，如果两次切线与 $x$ 轴的交点足够接近，那么我们就得到方程的解了。

5. 代码实现二

class Solution {
public:int mySqrt(int x) {if (x == 0) {return 0;}double a0 = x;while (1) {double a1 = 0.5 * a0 + x / 2.0 / a0;if (fabs(a0 - a1) < 1e-7) {break;}a0 = a1;}return int(a0);}
};

这篇关于LeetCode 69—— x 的平方根的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---