一、二分查找
1、搜索插入位置
- 初始化左右边界：
left指向数组的起始位置，right指向数组的末尾。 - 二分查找过程：不断计算中间位置
mid，根据nums[mid]与目标值target的比较结果，调整left和right，从而缩小搜索范围。 - 返回结果：当
left超过right时，搜索结束，返回left，它是目标值应当插入的位置。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left,right=0,len(nums)-1
while left<=right:
mid=(left+right)//2
if nums[mid]==target:
return mid
elif nums[mid]<target:
left=mid+1
else:
right=mid-1
return left2、搜索二维矩阵
①双指针法（前面有）
由题意可得，矩阵的每一行和每一列都按升序排列，因此可以从矩阵的右上角开始，通过逐步排除不符合条件的行或列来缩小查找范围。最终要么找到目标值，要么确定它不存在。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n,m=len(matrix),len(matrix[0])
i=0;j=m-1
while i<n and j>=0:
if matrix[i][j]==target:
return True
elif matrix[i][j]>target:
j-=1
else:
i+=1
return False②二分法
由于矩阵整体上是有序的，我们可以将二维矩阵视为一个一维有序数组，然后对其进行二分查找。
索引映射关系：
- 一维到二维索引
- 行号：
row = index // n，其中n是列数。 - 列号：
col = index % n。
- 行号：
- 二维索引到一维索引：
index = row * n + col。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n,m=len(matrix),len(matrix[0])
left,right=0,n*m-1
while left<=right:
mid=(left+right)//2
if matrix[mid//m][mid%m]==target:
return True
elif matrix[mid//m][mid%m]>target:
right=mid-1
else:
left=mid+1
return False
3、在排序数组中查找元素的第一个和最后一个位置
-
mid=(left+right)//2：这种方式计算的mid更偏向于左侧。这是因为当left+right为偶数时，它会精确地取中间；而当它为奇数时，mid会向左侧靠拢。通常用这种方式来查找目标值的第一个位置。 -
mid=(left+mid+1)//2（偏右）：通过在mid的基础上加 1，使得在偶数的情况下mid向右侧靠拢。这通常用于寻找目标值的最后一个位置，因为它倾向于偏向右侧的搜索区域。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1,-1]
left,right=0,len(nums)-1
ans=[]
while left<right:
mid=(left+right)//2
if nums[mid]>=target:
right=mid
else:
left=mid+1
if nums[left]!=target:
return [-1,-1]
else:
ans.append(left)
left,right=0,len(nums)-1
while left<right:
mid=(left+right+1)//2
if nums[mid]<=target:
left=mid
else:
right=mid-1
ans.append(left)
return ans4、搜索旋转排序数组
题意：
分两步走：
- 第一步是找到数组中的旋转点，也就是最小元素的位置（456123中1就是旋转点）。找到旋转点以后，可以修正下面二分查找中mid的值。
- 第二步是在旋转后的数组中进行二分查找，返回目标值的位置。
详细点说：
步骤 1：找到旋转点（最小元素的位置）
- 目的：我们需要找到数组中的最小值，这个最小值就是数组旋转的起点。
- 思路：利用二分查找的思想，如果中间值
nums[mid]小于或等于右边界值nums[right]，说明最小值在当前中间值的左边或中间值本身；否则，最小值在右边。通过不断缩小搜索范围，最终找到最小值的索引。
步骤 2：在旋转后的数组中查找目标值
- 目的：在经过旋转的数组中，使用二分查找来找到目标值。
- 思路：由于数组是经过旋转的，直接对整个数组进行二分查找可能无法得到正确结果。所以我们使用一个技巧，通过旋转点的索引来调整搜索的中间索引，从而在实际旋转后的数组中正确地进行二分查找。
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left,right=0,len(nums)-1
while left<right:
mid=(left+right)//2
if nums[mid]<=nums[right]:
right=mid
else:
left=mid+1
pos=left
left,right=0,len(nums)-1
while left<=right:
mid=(left+right)//2
real_mid=(mid+pos)%len(nums)
if nums[real_mid]==target:
return real_mid
elif nums[real_mid]<target:
left=mid+1
else:
right=mid-1
return -15、搜索旋转排序数组中的最小值
参考4。
class Solution:
def findMin(self, nums: List[int]) -> int:
left,right=0,len(nums)-1
while left<right:
mid=(left+right)//2
if nums[mid]<=nums[right]:
right=mid
else:
left=mid+1
return nums[left]6、寻找两个正序数组中的中位数
具体思路：
-
定义两个数组的分割： 假设
nums1和nums2分别有m和n个元素，分割的意思是把这两个数组分成两部分：- 左半部分的元素为：
nums1的前i个元素和nums2的前j个元素。 - 右半部分的元素为：
nums1的后m - i个元素和nums2的后n - j个元素。
- 左半部分的元素为：
-
分割后的性质： 为了使得合并后数组的中位数可以通过分割直接得出，我们需要满足以下条件：
nums1[i-1] <= nums2[j]和nums2[j-1] <= nums1[i]，这保证了左半部分所有元素都小于等于右半部分的元素。 -
通过二分查找确定分割位置： 我们可以在较短的数组
nums1上使用二分查找来找到合适的i值（分割位置），然后j的值通过j = (m + n + 1) // 2 - i确定。 -
判断中位数：
- 如果
m + n是奇数，那么中位数就是左半部分的最大值。 - 如果
m + n是偶数，那么中位数是左半部分最大值和右半部分最小值的平均值。
- 如果
-
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1)>len(nums2): nums1,nums2=nums2,nums1 m,n=len(nums1),len(nums2) left,right=0,m half_len=(m+n+1)//2 while left<=right: i=(left+right)//2 j=half_len-i if i<m and nums1[i]<nums2[j-1]: left=i+1 elif i>0 and nums1[i-1]>nums2[j]: right=i-1 else: max_left=0 if i==0: max_left=nums2[j-1] elif j==0: max_left=nums1[i-1] else: max_left=max(nums1[i-1],nums2[j-1]) if (m+n)%2==1: return max_left min_right=0 if i==m: min_right=nums2[j] elif j==n: min_right=nums1[i] else: min_right=min(nums1[i],nums2[j]) return (max_left+min_right)/2.0
二、栈
1、有效的括号
- 初始化栈：使用一个空的
list作为栈。 - 遍历字符串：循环遍历字符串中的每个字符。
- 如果遇到左括号
(、{、[，则将相应的右括号)、}、]压入栈中。 - 如果遇到右括号，则检查栈是否为空，如果栈为空或者栈顶元素与当前右括号不匹配，返回
False。
- 如果遇到左括号
- 最终检查：如果遍历完字符串后栈为空，则说明括号匹配成功，返回
True；否则返回False。
class Solution:
def isValid(self, s: str) -> bool:
if not s:
return True
stk=[]
for ch in s:
if ch=='(':
stk.append(')')
elif ch=='[':
stk.append(']')
elif ch=='{':
stk.append('}')
elif not stk or ch!=stk.pop():
return False
return not stk2、最小栈
class MinStack:
def __init__(self):
self.stk=[]
def push(self, val: int) -> None:
if not self.stk:
self.stk.append((val,val))
else:
self.stk.append((val,min(val,min(val,self.stk[-1][1]))))
def pop(self) -> None:
self.stk.pop()
def top(self) -> int:
return self.stk[-1][0]
def getMin(self) -> int:
return self.stk[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()3、字符串解码
整体思路：
- 遇到 [ ：入栈，存储当前的multi和res。再将res和multi重置，因为进入新的括号后，新的字符串部分需要重新计算重复次数
multi，并且res需要开始记录当前括号内的内容。- 存储当前的
multi，表示在当前的[ ]内的字符串需要重复的次数。例如，在3[a2[c]]中，multi最初是3，它表明最外层括号内的内容需要重复 3 次。 - 当前的
res表示在当前[前已经解码出来的部分字符串。它需要暂时保存起来，等待括号内的字符串解码完成后再拼接回去。例如，3[a2[c]]中，当我们处理到[时，res是空的，进入括号后，会处理括号内的部分。），当遇到[时将当前状态保存进栈，遇到]时弹出栈恢复状态。
- 存储当前的
-
遇到 ] 出栈：获取上一个保存的
multi和res。- 出栈操作恢复到上一个
[前的状态。通过stack.pop()，我们可以得到上一个multi和res，分别是括号之前的字符串以及重复次数。 - 更新res：res=已经解码部分字符串+当前括号内字符串重复次数*当前括号内字符串
- 出栈操作恢复到上一个
- 遇到字符：与前面进行拼接。
class Solution:
def decodeString(self, s: str) -> str:
stk=[]
res=""
multi=0
for ch in s:
if ch=='[':
stk.append((multi,res))
res,multi="",0
elif ch==']':
cur_multi,last_res=stk.pop()
res=last_res+cur_multi*res
elif '0'<=ch<='9':
multi=multi*10+int(ch)
else:
res+=ch
return res
