LeetCode 69. x 的平方根 | Python
2021-01-25 22:14
标签：sha 高效 个数 来源 ext 死循环 text color log 题目来源：https://leetcode-cn.com/problems/sqrtx 实现?int sqrt(int x)?函数。 计算并返回?x?的平方根，其中?x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 示例 2: 思路：二分查找 二分查找，也叫折半查找，相信从一个例子中能很好的理解这个概念。【猜数字】，可能很多人都接触过这个游戏。这里面就能够用二分查找进行实现。 当告知在谜底数字在一定的范围内，如何能够高效的猜中数字？那么二分查找这个方法在这里，就应该从这个范围内的中间开始猜测。当告知猜测的数字比谜底数字大或者小，进而判断谜底落在这个猜测数字的左侧还是右侧，再次确定范围后，又从中间开始猜测，循环直至猜出谜底数字。 题目中说明，x 为非负整数，从这个的角度来看，平方根是一定不会超过自身。同样，一个数的平方根与一个数的一半相比，数的平方根同样不会超过数的一半。 这里表示，如果数的一半的平方大于自身，那么这个数的取值范围。 可以看出这个边界值是 4，那么就对 0，1，2，3，单独进行计算。由于题目要求返回整数，小数部分将被舍去，那么对应的平方根依次是 0,1,1,1。 具体代码如下。 以上就是使用二分查找的方法，解决《69. x 的平方根》问题的主要内容。 欢迎关注微信公众号《书所集录》 LeetCode 69. x 的平方根 | Python 标签：sha 高效 个数 来源 ext 死循环 text color log 原文地址：https://www.cnblogs.com/yiluolion/p/12859372.html69. x 的平方根
题目
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
? 由于返回类型是整数，小数部分将被舍去。
解题思路
代码实现
class Solution:
def mySqrt(self, x: int) -> int:
# 注意边界 0, 1
left = 0
right = x // 2 + 1
# 根据上面的公式进行计算
# 开始进行二分查找
while left x:
right = mid - 1
else:
left = mid
return left
实现结果
下一篇：java 反射的学习实践2
文章标题：LeetCode 69. x 的平方根 | Python
文章链接：http://soscw.com/index.php/essay/46987.html