AlgoPressAppearance
0069-x的平方根
https://leetcode.cn/problems/sqrtx
给你一个非负整数 x ，计算并返回x的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
思路
二分查找，特别要注意两个数字相乘判断的时候，一定要使用更大的数据类型，如 long ，否则会变成负数，判断失败。 注意每个数字都要加上 (long) 强转
参考代码
csharp
public class Solution {
public int MySqrt(int x) {
int left = 0;
int right = x;
while(left < right){
int mid = left + (right - left) / 2;
long square = (long)mid * (long)mid;
if(square > x){
right = mid;
}
else if(square < x){
left = mid+1;
}
else{
return mid;
}
}
if((long)left * (long)left > x){
return left - 1;
}
return left;
}
}
java
class Solution {
public int mySqrt(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;
}
}
参考代码：优化
注意中间每次 mid * mid <=x 的时候，就记录 ans 当 mid * mid > x 的时候，循环也结束了，最后一次计算的 mid 就是结果，注意不是 left
csharp
public class Solution{
public int MySqrt(int x){
int left = 0, right = x, ans = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if((long) mid * mid <= x){
ans = mid;
left = mid +1;
}
else{
right = mid - 1;
}
}
return ans;
}
}
复习：2022-04-30
csharp
public class Solution {
public int MySqrt(int x) {
//二分查找法
int index = -1;
int left = 0;
int right = x;
while(left <= right){
int mid = left + (right - left) / 2;
if((long)mid * mid <= x){
index = mid;
left = mid + 1;
}
else{
right = mid - 1;
}
}
return index;
}
}
牛顿迭代
n^2 = x 求 n , x / n = n 举例，目标数字 x = 12, x可以有以下几个数相乘构成 1 * 12 2 * 6 3 * 4 √￣12 * √￣12 4 * 3 6 * 2 12 * 1
x 和 n/x 就是 12 的两个因子，当这两个值相等的时候，意味着 n = √￣x
举例：2 * 6 目标值是 √￣12 2 和 6 的平均值将更加趋近于 √￣12 解释：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
csharp
public class Solution {
public int MySqrt(int x) {
//牛顿迭代，不能除以0
if(x == 0){
return 0;
}
return (int)mySqrt(x,x);
}
public double mySqrt(double n, double x){
// 牛顿迭代 n^2 = x, --> n = x / n, 这两个值的均值(n + x/n)/2，比这两个值更加逼近 x
double res = (n + x/n)/2;
if(res == n){ //当前精度下相等，是判断等于 n
return res;
}
return mySqrt(res,x);
}
}