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

本文主要是介绍【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《博主简介》

小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~
👍感谢小伙伴们点赞、关注!

X的平方根

class Solution:

    def mySqrt(self, x: int) -> int:

        l, r, ans = 0, x, -1

        while l <= r:

            mid = (l + r) // 2

            if mid * mid <= x:

                ans = mid

                l = mid + 1

            else:

                r = mid - 1

        return ans

有效完全平方数

class Solution:

    def isPerfectSquare(self, num: int) -> bool:

        l = 0

        r = num

        while l <= r:

            mid = (l+r)//2

            if mid * mid == num:

                return True

            elif mid * mid < num:

                l = mid + 1

            else:

                r = mid - 1

        return False

搜索旋转排序数组

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        if not nums:

            return -1

        # 二分法

        n = len(nums)

        left = 0

        right = n - 1

        while left <= right:

            mid = (left + right) // 2

            if nums[mid] == target:

                return mid

            if nums[0] <= nums[mid]:

                # 说明左边有序

                if nums[0] <= target < nums[mid]:

                    right = mid - 1

                else:

                    left = mid + 1

            else:

                # 右边有序

                if nums[mid] < target <= nums[n-1]:

                    left = mid + 1

                else:

                    right = mid - 1

        return -1

搜索二位矩阵

class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        if not matrix:

            return False

        # 二分查找 row = index // n ; col = index % n

        m = len(matrix)

        n = len(matrix[0])

        left = 0

        right = m * n - 1

        while left <= right:

            mid = (left + right) // 2

            cur_m = mid // n

            cur_n = mid % n

            if matrix[cur_m][cur_n] == target:

                return True

            elif matrix[cur_m][cur_n] > target:

                right = mid - 1

            else:

                left = mid + 1

        return False

搜索二维矩阵2

   def searchMatrix(self, matrix, target):

        """

        :type matrix: List[List[int]]

        :type target: int

        :rtype: bool

        """

        # 1.暴力法 for i in range(m) for j in range(n)   O(mn)

        # 2.剪枝搜索,假设从左下角开始搜索O(m+n)

        if not matrix:

            return False

        m = len(matrix)

        n = len(matrix[0])

        row = m - 1

        col = 0

        while row >= 0 and col < n:

            if matrix[row][col] > target:

                row -= 1

            elif matrix[row][col] < target:

                col += 1

            else:

                return True

        return False

寻找旋转排序数组中的最小值

class Solution:

    def findMin(self, nums: List[int]) -> int:

        if len(nums) == 1:

            return nums[0]

        left = 0

        right = len(nums) - 1

        while left < right:

            mid = (left + right) // 2

            if nums[mid] < nums[right]:

                # mid可能是最小值

                right = mid

            else:

                # mid一定不是最小值

                left = mid + 1

        return nums[left]

关于本篇文章大家有任何建议或意见,欢迎在评论区留言交流!

觉得不错的小伙伴,感谢点赞、关注加收藏哦!

欢迎关注下方GZH:阿旭算法与机器学习,共同学习交流~

这篇关于【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/518578

相关文章

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

Kali Linux安装实现教程(亲测有效)

《KaliLinux安装实现教程(亲测有效)》:本文主要介绍KaliLinux安装实现教程(亲测有效),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、下载二、安装总结一、下载1、点http://www.chinasem.cn击链接 Get Kali | Kal

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删