给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sqrtx
# x的算术平方根 class Solution: # 二分法 def sqrtx(self, x: int) -> int: if x < 0: return -1 left, right, ans = 0, x, x while left <= right: mid = left + ((right-left)>>1) if mid*mid > x: right = mid - 1 else: ans = mid left = mid + 1 return ans # 牛顿-拉夫逊迭代 def sqrtx_newton(self, x: int) -> int: if x < 0: return -1 elif x == 0: return 0 C, x0 = float(x), float(x) while True: xi = 0.5 * (x0 + C/x0) if abs(x0-xi) < 1e-7: break x0 = xi return int(x0) if __name__ == "__main__": x = 256 test = Solution() print(test.sqrtx(x)) print(test.sqrtx_newton(x))
package main import ( "fmt" "math" ) func main() { var x int = 656 fmt.Println(sqrtx(x)) fmt.Println(sqrtxNewton(x)) } func sqrtx(x int) int { if x < 0 { return -1 } var left int = 0 var right int = x var ans int = -1 for left <= right { var mid int = left + ((right - left) >> 1) if mid*mid > x { right = mid - 1 } else { ans = mid left = mid + 1 } } return ans } func sqrtxNewton(x int) int { if x < 0 { return -1 } else if x == 0 { return 0 } C := float64(x) x0 := float64(x) for { xi := 0.5 * (x0 + C/x0) if math.Abs(x0 - xi) < 1e-7 { break } x0 = xi } return int(x0) }