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

2023-12-19 05:25:16

《博主简介》

小伙伴们好,我是阿旭。专注于人工智能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:阿旭算法与机器学习,共同学习交流~

文章来源:https://blog.csdn.net/qq_42589613/article/details/135074015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。