已解答
简单
相关标签
相关企业
提示
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
class Solution {
public:
int mySqrt(int x) {
return pow(x, 0.5);
}
};class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: #检查输入的 x 是否为 0。如果是，直接返回 0，因为 0 的平方根是 0。
return 0
ans = int(math.exp(0.5 * math.log(x))) # 使用数学公式计算 x 的平方根的整数部分。这里使用了自然对数 math.log(x) 和指数函数 math.exp()。公式 math.exp(0.5 * math.log(x)) 等价于根号x，然后使用 int() 函数取整数部分。
return ans + 1 if (ans + 1 )**2<=x else ans #检查计算出的整数部分 ans 是否需要加 1。如果 (ans+1)*(ans+1) 小于等于 x，则返回 ans + 1，否则返回 ans。这是因为我们需要找到不大于 x 的最大整数平方根。class Solution:
def mySqrt(self, x: int) -> int:
l,r,ans = 0,x,-1 # 初始化变量 l 为 0，这是二分查找的左边界 初始化变量 r 为 x，这是二分查找的右边界
while l<=r:#开始一个循环，只要左边界 l 小于等于右边界 r，循环就会继续。
mid = (l+r)//2 #计算中间值 mid，这是 l 和 r 的平均值，使用右移一位的操作来实现除以 2，这是一种位运算的优化。
if mid * mid <=x: #如果 mid 的平方小于等于 x，则说明 x 的平方根可能大于 mid。
ans = mid #更新左边界 l 为 mid + 1，因为我们知道 mid 可能是 x 的平方根的一个低估。
l= mid +1 #更新左边界 l 为 mid + 1，因为我们知道 mid 可能是 x 的平方根的一个低估。
else:#如果 mid 的平方大于 x，则说明 x 的平方根可能小于 mid。
r = mid -1 #更新右边界 r 为 mid - 1，因为我们知道 mid 可能是 x 的平方根的一个高估。
return ans