网站增加域名备案,创业网站建设,课件ppt模板免费下载,网站开发子账号需求
给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。 注意#xff1a;不允许使用任何内置指数函数和算符#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1#…需求
给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1 输入x 4 输出2 示例 2 输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。
分析
可以使用二分查找的思路来求解算术平方根。 首先设定搜索范围最小值为0最大值为x。 然后通过二分查找的方式逼近算术平方根。 每次选取中间值mid计算mid的平方。如果平方小于等于x说明mid可能是答案的一部分更新最小值为mid继续搜索mid右边的范围。 如果mid的平方大于x说明mid不是答案的一部分更新最大值为mid。 当搜索范围缩小到最小值和最大值相等时返回最小值即可。
代码
class Solution:def x_sqrt(self,x):left0rightxwhile leftright:mid(leftright)//2if mid*mid x (mid1)*(mid1):return midelif mid*midx:leftmid1else:rightmid-1if __name__ __main__:callSolution()x8print(call.x_sqrt(x))运行结果
