友情提示:本文共有 868 个字,阅读大概需要 2 分钟。
“Leetcode 69 - x的平方根”是一道经典的数学问题,考察了数值计算和二分查找算法。该问题要求实现一个函数来计算非负整数x的平方根。采用二分查找算法可以在时间复杂度O(logn)内找到精确的平方根。这道题目对于算法和数据结构的理解有很大帮助,不仅考察了对最基本的运算的理解,还锻炼了对二分查找算法的掌握。在Leetcode的算法题库中,这道题目是一个很好的练习题,也是理解二分查找思想的绝佳案例。
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
直接用JDK方法
publicstaticintmySqrt(intx){
return (int) Math.sqrt(x);
}
防止溢出,使用long类型保存数字
public static int mySqrt2(int x) {
long x0 = x;
while (x0 * x0 > x) {
x0 = (x0 + x / x0) / 2;
}
return (int) x0;
}
使用二分法计算
public static int mySqrt(int x) {
if (x / 2 == 0) return x;
int left = 1, right = x / 2, res = 0;
while (left <= right) {
long mid = left + (right - left) / 2;
long temp = mid * mid;
if (temp == x) {
return (int) mid;
} else if (temp > x) {
right = (int) mid - 1;
} else {
res = (int) mid;
left = (int) mid + 1;
}
}
return res;
}
收集不易,本文《LeetCode-69: 计算 x 的平方根》知识如果对你有帮助,请点赞收藏并留下你的评论。