69. x 的 平方根
easy
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
示例 1：
示例 2：
1
2
3
| 输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
|
二分法
x 平方根的整数部分 ans 是满足 k^2^ ≤ x
的最大 kk 值
不多 bb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func mySqrt(x int) int {
low, high := 0, x
for low <= high {
mid := low + (high-low)>>1
if mid*mid < x {
if (mid+1)*(mid+1) > x {
// 找到最后一个小于x的mid
return mid
}
low = mid + 1
} else if mid*mid > x {
high = mid - 1
} else {
return mid
}
}
return -1
}
|
袖珍计算器算法
1
2
3
4
5
6
7
8
9
10
| func mySqrt(x int) int {
if x == 0 {
return 0
}
ans := int(math.Exp(0.5 * math.Log(float64(x))))
if (ans + 1) * (ans + 1) <= x {
return ans + 1
}
return ans
}
|
