【力扣hot100】刷题笔记Day20

本文主要是介绍【力扣hot100】刷题笔记Day20，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

今天学习了一句话“自己如果不努力，屎都吃不上热乎的”，话糙理不糙，与君共勉

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_Border+1] == 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