北京永安市政建设投资有限公司网站,分享网站友情链接,长沙网络推广专员,加拿大网站后缀前言
今天学习了一句话“自己如果不努力#xff0c;屎都吃不上热乎的”#xff0c;话糙理不糙#xff0c;与君共勉
35. 搜索插入位置 - 力扣#xff08;LeetCode#xff09; 二分查找 class Solution:def searchInsert(self, nums: List[int], target: int) - int:n…前言
今天学习了一句话“自己如果不努力屎都吃不上热乎的”话糙理不糙与君共勉
35. 搜索插入位置 - 力扣LeetCode 二分查找 class Solution:def searchInsert(self, nums: List[int], target: int) - int:n len(nums)l, r 0, n - 1while l r: # 左闭右闭mid l (r - l) // 2if nums[mid] target:return midelif nums[mid] target:l mid 1else:r mid - 1return r 1 # 应该插入的位置
74. 搜索二维矩阵 - 力扣LeetCode 二分查找 class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:m, n len(matrix), len(matrix[0])l, r 0, m * n - 1while l r:mid l (r - l) // 2row mid // n # 转化成矩阵中的行坐标col mid % n # 转化成矩阵中的列坐标print(mid, row, col)if matrix[row][col] target: l mid 1elif matrix[row][col] target:r mid - 1else:return Truereturn False
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode 二分查找左右边界 class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:# 寻找[target,...,target]的左边界def leftBorder(nums, target):l, r 0, len(nums) - 1while l r:mid l (r - l) // 2if nums[mid] target:r mid - 1else:l mid 1return l# 寻找[target,...,target]的右边界def rightBorder(nums, target):l, r 0, len(nums) - 1while l r:mid l (r - l) // 2if nums[mid] target:l mid 1else:r mid - 1return rl_Border leftBorder(nums, target)r_Border rightBorder(nums, target)if l_Border r_Border:return [l_Border, r_Border]else: # 排除找不到target的情况return [-1, -1] 二分查找单边界滑动 class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:# 寻找[target,...,target]的左边界def leftBorder(nums, target):l, r 0, len(nums) - 1while l r:mid l (r - l) // 2if nums[mid] target:r mid - 1else:l mid 1return ln len(nums)l_Border leftBorder(nums, target)# 处理特殊情况找不到targetif l_Border n or nums[l_Border] ! target: return [-1,-1]# 允许范围内右边界向右滑动r_Border l_Borderwhile r_Border 1 n - 1 and nums[r_Border1] target:r_Border 1return [l_Border, r_Border]
33. 搜索旋转排序数组 - 力扣LeetCode 二分查找寻找有序 class Solution:def search(self, nums: List[int], target: int) - int:n len(nums)l, r 0, n - 1while l r:mid l (r - l) // 2# mid左侧包含mid为有序部分一个元素nums[0]nums[mid]也有序所以要if nums[0] nums[mid]:if nums[0] target nums[mid]:r mid - 1elif target nums[mid]:return midelse:l mid 1# mid右侧包含mid为有序部分else:if nums[mid] target nums[n - 1] :l mid 1elif target nums[mid]:return midelse:r mid - 1 return -1
153. 寻找旋转排序数组中的最小值 - 力扣LeetCode 二分查找寻找无序 class Solution:def findMin(self, nums: List[int]) - int:l, r 0, len(nums) - 1while l r:mid l (r - l) // 2# 左边有序右边无序去右边找if nums[0] nums[mid]: # 考虑[2,1]中lmid情况要往右找if mid 0 and nums[mid-1] nums[mid]: # 异常递减值return nums[mid]else:l mid 1# 右边有序左边无序去左边找else:if mid 0 and nums[mid-1] nums[mid]: # 异常递减值return nums[mid]else:r mid - 1return nums[0] # 找不到说明无旋转nums[0]就是最小# 简洁优化边界难处理
class Solution:def findMin(self, nums: List[int]) - int:l, r 0, len(nums) - 1if nums[l] nums[r]: # 本身有序返回第一个return nums[l]while l r:mid l (r - l) // 2if nums[0] nums[mid]: # 考虑[2,1]中lmid情况要往右找l mid 1 # 右边无序往右找else: r mid - 1 # 左边无序往左找return nums[l]
4. 寻找两个正序数组的中位数 - 力扣LeetCode
困难题要递归找两个有序数组的第k大数看思路讲解和代码实现 class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:给定两个排好序的数组求他们合并后的第k大数def findK(nums1, nums2, k):if len(nums1) 0: # 其中一个为空就返回另一个的第k大对应下标k-1return nums2[k-1]if len(nums2) 0:return nums1[k-1] if k 1: # 第1大就比较头两个数return min(nums1[0], nums2[0])k1 min(k//2, len(nums1)) # 划分给nums1的数量可能不够k2 min(k-k1, len(nums2)) # 剩余给nums2的数量可能不够if nums1[k1-1] nums2[k2-1]: # 小的数不可能是第k大了删除后递归去下一层return findK(nums1[k1:], nums2, k-k1)else: # 由于可能有不够的现象相等不意味着就是第k大还要继续分割return findK(nums1, nums2[k2:], k-k2)size len(nums1) len(nums2)if size % 2 0: # 偶数left findK(nums1, nums2, size // 2) # 10就是找第5right findK(nums1, nums2, size // 2 1) # 10就是找第6res (left right) / 2else: # 奇数res findK(nums1, nums2, size // 2 1) # 11就是找第6return res
后言
二分实现和记模板不难主要是要处理好边界多在草稿上演算一下就行
