-
Notifications
You must be signed in to change notification settings - Fork 1
/
SqrtX.java
70 lines (64 loc) · 1.67 KB
/
SqrtX.java
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package com.hncboy;
/**
* @author hncboy
* @date 2019/9/19 12:23
* 69.x 的平方根
*
* 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
* 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
* 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
*
* 示例 1:
* 输入:x = 4
* 输出:2
* 示例 2:
*
* 输入:x = 8
* 输出:2
* 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
*
* 提示:
* 0 <= x <= 231 - 1
* 通过次数 432,911 提交次数 1,108,145
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/sqrtx
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class SqrtX {
private int n;
public static void main(String[] args) {
System.out.println(new SqrtX().mySqrt2(20));
}
/**
* 二分查找法
*/
public int mySqrt2(int x) {
long left = 0;
long right = x;
while (left < right) {
long mid = (left + right + 1) / 2;
long square = mid * mid;
if (square > x) {
right = mid - 1;
} else {
left = mid;
}
}
return (int) left;
}
/**
* 牛顿迭代法
*/
public int mySqrt1(int x) {
if (x == 0) {
return 0;
}
n = x;
return ((int) (sqrt(x)));
}
private double sqrt(double x) {
double result = (x + n / x) / 2;
return result == x ? x : sqrt(result);
}
}