LeetCode刷题实战69：x 的平方根
共 1253字，需浏览 3分钟
·
2020-10-18 21:13
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 x 的平方根，我们先来看题面：
https://leetcode-cn.com/problems/sqrtx/
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
题意
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题
public class Solution {
public int mySqrt(int x) {
for (long i = 1; i <= x; i++) {
if(i * i > x) {
return (int)(i - 1);
}else if(i * i == x) {
return (int)i;
}
}
return 0;
}
}
public class Solution {
public int mySqrt(int x) {
int left = 0, right = x / 2 + 1;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid == x) {
return (int) mid;
} else if (mid * mid < x) {
left = (int) (mid + 1);
} else {
right = (int) (mid - 1);
}
}
return right;
}
}
上期推文：