LeetCode0069.Sqrt(x)squarerootofx【易】【Python】【两点】问题LeetCode实现intsqrt(intx).计算并返回平方x的根，其中x保证为非负整数。由于返回类型是整数，小数部分被截断，只返回结果的整数部分。示例1：输入：4输出：2示例2：输入：8输出：2解释：8的平方根为2.82842...，由于小数部分被截断，因此返回2。问题是实现intsqrt(intx)函数。计算并返回x的平方根，其中x是一个非负整数。由于返回类型是整数，结果中只保留整数部分，小数部分将被舍弃。示例1：输入：4输出：2示例2：输入：8输出：2解释：8的平方根为2.82842...，由于返回类型为整数，因此小数部分将被四舍五入。思路一：二分查找典型二分题。请注意，返回值应该是一个整数。方法二：牛顿迭代法的详细介绍可以看这篇文章：牛顿迭代法快速求平方根。设f(res)=res^2-x，则sqrt(x)等价于求f(res)的根每次迭代的初始假设答案res=x，设res=(res+x/res)/2newres的res值是当前res值对应的函数切线与x轴的交点的横坐标，这就是牛顿迭代的本质。方法三：直接使用库函数。时间复杂度：O(logn)空间复杂度：O(1)PythoncodeclassSolution(object):defmySqrt(self,x):""":typex:int:rtype:int"""#solutionone:binary搜索low,high,mid=0,x,x/2whilelow<=high:ifmid**2>x:high=mid-1else:low=mid+1mid=(low+high)/2returnint(mid)##解决方案二：牛顿法#res=x#whileres*res>x:#res=(res+x/res)/2#returnint(res)##解决方案三：math#importmath#returnint(math.sqrt(x))代码地址GitHub链接
