知一的指纹

69. x 的平方根

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数,小数部分将被舍去。

思路

二分查找比较

需要注意的地方有两个

  1. 注意开始边界问题
  2. 注意类型长度越界

解答

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
public class MySqrt {
public static void main(String[] args) {
MySqrt mySqrt = new MySqrt();
System.out.println(mySqrt.mySqrt(2147395599));

}

// 边界问题
// 1. 0\1边界
// 类型长度越界
public int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
return mySqrt(x, 0, x);
}

public int mySqrt(long x, long left, long right) {
long cur = (right - left) / 2 + left;
long cur2 = cur * cur;
if (cur2 == x) {
return (int) cur;
} else if (right - left == 1) {
return (int) left;
}

if (cur2 < x) {
left = cur;
} else if (cur2 > x) {
right = cur;
} else {
return (int) cur;
}
return mySqrt(x, left, right);
}
}

扩展

牛顿迭代法


如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏