LeetCode之Sqrt(x)
1、题目
Implement int sqrt(int x)
.
Compute and return the square root of x.
Subscribe to see which companies asked this question.
2、代码实现
public class Solution {
public int mySqrt(int x) {
if (x < 0)
return -1;
if (x == 0)
return 0;
if (x == 1)
return 1;
int max = x / 2 + 1;
int min = 1;
while (min <= max) {
int mid = (min + max) / 2;
if (mid <= x / mid && x / (mid + 1) < mid + 1)
return mid;
if (mid > x / mid)
max = mid - 1;
else
min = mid + 1;
}
return 0;
}
}
3、注意的地方
1)、第一要记得判断条件是
mid * mid <= x && (mid + 1) * (mid + 1) >x
2)、第二要防止数据超过整形数据范围,所以需要把条件转化为
mid <= x / mid && x / (mid + 1) < mid + 1
3)、逻辑要清晰,先求max,min, next we will get mid, and condition is mid * mid <= x && (mid + 1) * (mid + 1) > x, and by condition ,do not remember max = mid -1, min = mid +1 or max = mid, min = mid;
赞 (0)