1，问题描述
69. x 的平方根
难度：简单
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
示例 2：
1
2
3
| 输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
|
提示：
2，初步思考
三种解法：
1，袖珍计算器，本质就是利用数学公式推导的公式变形，将开方转变为其他计算形式
2，二分查找法，从0～x不断去逼近真实值
3，牛顿法求解：也是数学公式的变形
3，代码处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public class _69_x的平方根 {
public int mySqrt_pocket_calculator_algorithm(int x) {
if (x <= 1) return x;
int ans = (int) Math.exp(0.5 * Math.log(x));
return ((long) (ans + 1) * (ans + 1) <= x ? (ans + 1) : ans);
}
public int mySqrt_binary_search(int x) {
if (x <= 1) return x;
int left = 0, right = x, ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
public int mySqrt_newton_iteration(int x) {
if (x <= 1) return x;
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (Math.abs(x0 - xi) < 1e-7) break;
x0 = xi;
}
return (int) x0;
}
public static void main(String[] args) {
System.out.println(new _69_x的平方根().mySqrt_pocket_calculator_algorithm(8));
System.out.println(new _69_x的平方根().mySqrt_binary_search(8));
System.out.println(new _69_x的平方根().mySqrt_newton_iteration(8));
}
}
|