二分法
思路:
从0到x不断二分尝试。
代码:
class Solution: def mySqrt(self, x: int) -> int: l, r, ans = 0, x, -1 while l <= r: mid = (l + r) // 2 if mid * mid <= x: ans = mid l = mid + 1 else: r = mid - 1 return ans
牛顿法
思路:
做方程y = x2 - C,C为题目中的非负整数x,则题目变为求方程图像在x正半轴上的交点xi的值。从xi=C开始,做当前点切线与x轴交点为xi+1,当xi和xi+1差值逼近于一个足够小的值时,xi+1为所求答案,否则xi=xi+1,继续迭代。
代码:
class Solution: def mySqrt(self, x: int) -> int: if 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)
原文:https://www.cnblogs.com/nilhxzcode/p/13081526.html