合肥的网站建设公司哪家好,企业网站建设报价单,python个人网站开发,北京公司注册虚拟地址1 问题
给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。
由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。
注意#xff1a;不允许使用任何内置指数函数和算符#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4 输出2
示例 2
输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。
2 答案
这题直接不会
官方解实际上是一道搜索题
库函数最简单的可以用math库
class Solution(object):def mySqrt(self, x):return int(math.sqrt(x))暴力
class Solution(object):def mySqrt(self, x):sqrt 1while sqrt * sqrt x:sqrt 1return sqrt - 1
蓝红二分搜索法该法模板见 https://blog.csdn.net/CSDNLHCC/article/details/133893219?spm1001.2014.3001.5501 class Solution(object):def mySqrt(self, x):l -1r x 1while l 1 r: # 注意 这里是 l 1 rmid l (r-l)//2if mid ** 2 x: # 这里小于等于然后返回 r-1 即可 l midelse:r midreturn r - 1牛顿法 设num为输入x为所求 问题转化为求f(x)num - x ^ 2的零点 牛顿法递推公式 Xn1 Xn - f(Xn)/f(Xn) 带入f(x) -2x 得 Xn1 Xn (num - Xn ^ 2)/2Xn (num Xn ^ 2) / 2Xn (num / Xn Xn) / 2
class Solution:def mySqrt(self, num: int) - int:x numwhile x*x num:x (num // x x) // 2 # 据说用整除可以提高效率return xhttps://leetcode.cn/problems/sqrtx/solutions/238682/jing-dian-ti-mu-yi-ti-duo-jie-si-chong-fang-fa-jie/
