代码语言：javascript复制
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
主要使用二分法。可以多看看网上大佬的题解思路。。。 牛顿法我之前有点懵逼，不过确实厉害，学习了
代码语言：javascript复制/**
* X的平方根
* @Author: lixj
* @Date: 2020/9/10 14:36
*/
public class SqrtX {
/**
* 1、二分法
* @param x
* @return
*/
public int mySqrt(int x) {
int left = 0;
int right = x;
while(left <= right) {
// 使用long类型，防止超出界限
long mid = (left right) >> 1;
if ( mid * mid == x) {
return (int) mid;
} else if (mid * mid < x) {
left = (int) mid 1;
} else {
right = (int) mid -1;
}
}
return right;
}
int s;
/**
* 牛顿迭代法
* @param x
* @return
*/
public int mySqrt1(int x) {
s=x;
if(x==0) return 0;
return ((int)(sqrts(x)));
}
public double sqrts(double x){
double res = (x s / x) / 2;
if (res == x) {
return x;
} else {
return sqrts(res);
}
}
/**
* 二分查找，
* @param x
* @return
*/
public int mySqrt2(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links: https://lixj.fun/archives/leetcode进阶之路-69x的平方根
