leetcode69---x 的平方根

这篇具有很好参考价值的文章主要介绍了leetcode69---x 的平方根。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大家好,我是大唐,刚刷完了几道经典的leetcode题,今天给大家分享一道leetcode上面的二分查找经典题型---x 的平方根,我们往下看。

题目描述

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例

leetcode69---x 的平方根,力扣高频刷题宝典,leetcode,算法,数据结构

求解方法

这道问题要求非负整数 x 的平方根。如果遇到平方根不是整数的情况呢?只取整数部分。例如,输入 x = 8,输出为 2。8 的平方根也就是 target 值,是小数 2.82842…。2 是小于 target 的元素中、最接近 target 的元素。

因此,这道问题实际是要 查找 <= target 、且与 target 值最接近的元素。

可以用两种二分查找法来寻找:

方法一、标准二分查找法 while left <= right
这个方法应用标准二分查找法,只需改动 while 循环之后的语句 return -1为 return right。

为什么呢?我们来分析一下。当数组中没有值为 target 的元素时,因为 while 循环的条件是 left <= right,最后一次循环时搜寻区间有一个或两个元素,right = left 或 left +1。

对于本题要返回 < target、最接近 target 的元素索引的情况:

如果最后一次 while 循环时 middle > target,元素应该插入的位置是 middle - 1 ,而循环结束时 right = middle -1。

如果最后一次 while 循环时 middle < target,元素应该插入的位置是 middle。循环开始时只有 right = left = middle(如果 while 循环开始时 right = left + 1,而 middle < target,还会进入下一次循环,因此排除这种情况。),结束时 right = middle。

因此, 只需把标准二分查找代码中 while 循环之后的语句由 return -1 改为 return right 即可。

代码如下:文章来源地址https://www.toymoban.com/news/detail-841299.html

class Solution:
    def mySqrt(self, x: int) -> int:
        # x = 0 或 1 时,直接返回结果
        if x <= 1:
            return x

        left, right = 1, x
        while left <= right:
            middle = left + (right - left) // 2
            if middle ** 2 == x:
                return middle
            elif middle ** 2 > x:
                right = middle - 1
            else:
                left = middle + 1
        
        return right

方法二、另一种二分查找法 while left < right
方法一,也就是标准二分查找法,是通过不断缩小搜索范围来查找某个元素。但是我们解决这一类型问题时发现,target 的取值可能是介于两个元素中间,虽然 middle 不等于 target,也许它就是最接近 target 取值的元素。比如本题例子求 8 的平方根,middle = 2 时。

对于本题要返回 < target、最接近 target 的元素索引的情况,当 middle < target 时,middle 位置有可能是我们要找的,下一次搜寻区间应该包含 middle。因此,此时 left = middle。

与方法一不同,这里的 while 循环条件为 left < right,因此循环终止时有 left = right,这样搜寻区间还有一个元素。这就是 <= target、最接近 target 的元素,最终返回它的索引( left 或 right 都可以,两者相同)。

这里有一个小细节需要注意,因为 while 循环条件为 left < right,最后一次循环时搜寻区间有两个元素,当 left = right 时循环结束。但是我们求 middle 并不是精确的平均值,而是向下取整,这导致当搜寻区间只有两个元素时,middle 始终等于 left。 这样,当 middle < target 时,left = middle,下一次循环 middle = (left + right) /2 = left ,没有更新搜寻区间,循环无法停止。怎么办呢?

代码如下:

class Solution:
    def mySqrt(self, x: int) -> int:
        # x=0或1时,直接返回结果
        if x <= 1:
            return x

        left, right = 1, x
        while left < right:
            middle = left + (right - left) // 2 + 1
            if middle ** 2 == x:
                return middle
            elif middle ** 2 > x:
                right = middle - 1
            else:
                left =  middle
                
        return left

到了这里,关于leetcode69---x 的平方根的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   mySqrt ( self ,  x :   int )   -   int :       

    2024年02月04日
    浏览(65)
  • 平方根法、改进的平方根法解方程组

    本篇内容包含两个部分:平方根法、改进的平方根法。感觉这种题绝大部分是靠套公式,记住公式和解题思路,还是相当简单的。 1 平方根法 1.1 解题思路 1.2 核心公式 1.3 例题解析 由 Ly=b L^t*x=y 解得 2 改进的平方根法 2.1 为什么要使用改进的平方根法 2.2 改进的平方根法解题公

    2024年02月06日
    浏览(53)
  • Python求平方根

    Python求平方根的方法有很多种,但是在不同情况下使用也不同 方法一:常用的是math模块的sqrt()函数 方法二:math模块的pow()函数 方法三:使用内置函数pow() 有时候math模块无法使用,这时候就需要使用自带的内置函数pow() 方法四:使用指数运算符** 注:将其中的1/2换成1/3则是

    2024年02月05日
    浏览(38)
  • Python算法例4 求平方根

    实现int sqrt(int x)函数,计算并返回x的平方根。 sqrt(3)=1;sqrt(4)=2;sqrt(5)=2;sqrt(17)=4。 要实现计算整数x的平方根函数sqrt(x),可以使用二分查找法。 首先,我们定义一个变量left = 0用来表示搜索区间的左边界,以及一个变量right = x用来表示搜索区间的右边界。初

    2024年02月05日
    浏览(39)
  • FPGA verilog 简单的平方根求法

    用下面的平方根求法不需要乘法,只需简单的移位就能实现。 原理参照论文 A New Non-Restoring Square Root Algorithm and Its VLSI Implementations

    2024年02月04日
    浏览(35)
  • C语言—求平方根(sqrt函数)

            在数学当中,我们知道了平方根。那么在C语言当中求一个数的平方根是如何实现的呢?今天我们就来讲解。  sqrt()函数为库函数,所以要包含对应的头文件,这个头文件包含了sqrt()函数的定义  下图中,x为要计算平方根的参数,sqrt()函数返回的是x的平方根,返回值

    2024年01月22日
    浏览(36)
  • 数值分析——改进的平方根法(matlab实现)

    最近上数值分析学到了改进平方根法的原理,并最终借助matlab实现了运用该方法进行解题,浅浅的记录一下。 由于本人并非数学专业,不擅长公式的推导,在此仅将书中内容拍照整理,供大家参考,主要用的是图中圈的两个公式: 式中的D是正定矩阵,求解过程参考第一张图

    2024年02月11日
    浏览(123)
  • Java习题之实现平方根(sqrt)函数

    目录 前言 二分查找 牛顿迭代法 总结 🎁博主介绍:博客名为tq02,已学C语言、JavaSE,目前学了MySQL和JavaWeb 🎥学习专栏:  C语言        JavaSE      MySQL基础 🎄博主链接:tq02的博客_CSDN博客-C语言,Java,MySQL领域博主         可使用java.lang.Math类的 sqrt(double)方法 求平方根。

    2024年02月15日
    浏览(45)
  • 【算法专题突破】二分查找 - x 的平方根(18)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:69. x 的平方根 - 力扣(LeetCode) 这道题就是求算数平方根, 要注意的点是他只需要保留整数部分,小数部分会舍去 我们确定好一个区间 1 ~ x,数字 x 的算数平方根一定在这里面, 最简单的思路就是用暴力解法

    2024年02月07日
    浏览(39)
  • 数值分析·学习 | 平方根法和追赶法matlab实现

    目录 一、前言: 二、算法描述: 三、实现代码: 1、平方根法: 2、改进的平方根法: 3、追赶法: 四、总结: 个人学习内容分享 平方根法:         如果A为n阶对称正定矩阵,则存在一个实的非奇异下三角矩阵L,使,当限定L的对角元素为正时,这种分解是唯一的。      

    2023年04月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包