河南网站建设优化推广,佛山+客户端官网,在线画流程图的网站,seo搜索引擎优化薪酬阅读目录 1. 题目2. 解题思路一3. 代码实现一4. 解题思路二5. 代码实现二 1. 题目 2. 解题思路一
二分查找法#xff0c;对于整数 i ∈ [ 0 , x ] i \in [0,x] i∈[0,x]#xff0c;我们判断 i 2 i^2 i2 和 x x x 的关系#xff0c;然后找到最后一个平方小于等于 x x x … 阅读目录 1. 题目2. 解题思路一3. 代码实现一4. 解题思路二5. 代码实现二 1. 题目 2. 解题思路一
二分查找法对于整数 i ∈ [ 0 , x ] i \in [0,x] i∈[0,x]我们判断 i 2 i^2 i2 和 x x x 的关系然后找到最后一个平方小于等于 x x x 的整数即可。
需要注意为了避免求平方的时候整数溢出需要选用 long long 类型。
另外 ( x 2 ) 2 1 4 x 2 x (\frac{x}{2})^2\frac{1}{4}x^2 x (2x)241x2x当 x 4 x 4 x4 的时候均成立但由于我们这里求的是整数所以则是当 x 5 x 5 x5 的时候我们可以将搜索区间缩短为 i ∈ [ 0 , x / 2 ] i \in [0,x/2] i∈[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 f(a)a^2-x0 f(a)a2−x0 的值我们可以用牛顿迭代法来求解。
假设初始值为 a 0 , f ( a 0 ) a 0 2 − x a_0, f(a_0)a_0^2-x a0,f(a0)a02−x切线斜率为 2 a 0 2a_0 2a0那么切线的方程为 y 2 a 0 ( z − a 0 ) ( a 0 2 − x ) y2a_0(z-a_0)(a_0^2-x) y2a0(z−a0)(a02−x)
切线与 x x x 轴的交点为 z 1 2 a 0 x 2 a 0 z\frac{1}{2}a_0\frac{x}{2a_0} z21a02a0x。
这样我们继续在 a 1 z a_1z a1z 处作新的切线如果两次切线与 x x 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);}
};
