def searchRange(nums: list[int], target: int) -> list[int]: n = len(nums) # 边界问题 1：提前处理空数组 if n == 0: return [-1, -1]
def binary_search_l(left, right, target): while left + 1 != right: mid = (left + right) // 2 if nums[mid] < target: left = mid else: right = mid # 边界问题 2：right 可能越界到达 n，需要先判断 right != n if right != n and nums[right] == target: return right return -1
def binary_search_r(left, right, target): while left + 1 != right: mid = (left + right) // 2 if nums[mid] <= target: left = mid else: right = mid # 边界问题 3：left 可能越界到达 -1，需要先判断 left != -1 if left != -1 and nums[left] == target: return left return -1
from typing import List import random def sortArray(nums: List[int]) -> List[int]: def half_sort(nums,left,right): #优化1：在 left 和 right 之间随机生成一个索引 index=random.randint(left, right) nums[left],nums[index]=nums[index],nums[left] pivot=nums[left] while left<right: # 1. 从右向左找，找到第一个小于 pivot 的数 while left < right and nums[right] >= pivot: right -= 1 nums[left] = nums[right] # 把这个数填到左边的坑里，右边形成新坑
# 2. 从左向右找，找到第一个大于 pivot 的数 while left < right and nums[left] <= pivot: left += 1 nums[right] = nums[left] # 把这个数填到右边的坑里，左边形成新坑
# 3. 当 left == right 时，循环结束，把 pivot 填入最后的坑中 nums[left] = pivot return left def quick_sort(nums,left,right): if right-left<=0: return pivot_index=half_sort(nums,left,right) quick_sort(nums,left,pivot_index-1) quick_sort(nums,pivot_index+1,right) quick_sort(nums,0,len(nums)-1) return nums if __name__ == '__main__': print(sortArray([2,2,2,2])) print(sortArray([5,1,1,2,0,0]))
from typing import List import random def sortArray(nums: List[int]) -> List[int]: def half_sort(nums,left,right): index=random.randint(left, right) nums[left],nums[index]=nums[index],nums[left] pivot=nums[left] i,j=left-1,right+1 while 1: i+=1#i，j要先移动是防止相同元素交换后还是一样，造成死循环 while nums[i]<pivot:#保证i右边的数>=pivot i+=1 j-=1 while nums[j]>pivot:#保证h左边的数<=pivot j-=1 if i>=j: return j nums[i],nums[j]=nums[j],nums[i]
def quick_sort(nums,left,right): if right-left<=0: return pivot_index=half_sort(nums,left,right) quick_sort(nums,left,pivot_index) quick_sort(nums,pivot_index+1,right) quick_sort(nums,0,len(nums)-1) return nums if __name__ == '__main__': print(sortArray([2,2,2,2])) print(sortArray([5,1,1,2,0,0]))
from typing import List import random def sortArray(nums: List[int]) -> List[int]: ans=[0]*len(nums) def merge_sort(nums,left,right): if left>=right:return mid=(left+right)//2 merge_sort(nums,left,mid) merge_sort(nums,mid+1,right) index=left i,j=left,mid+1 while i<=mid and j<=right: if nums[i]>nums[j]: ans[index]=nums[j] index+=1 j+=1 else: ans[index]=nums[i] index+=1 i+=1 if i<=mid: ans[index:right+1]=nums[i:mid+1] else: ans[index:right+1]=nums[j:right+1] nums[left:right+1]=ans[left:right+1] merge_sort(nums,0,len(nums)-1) return ans
# if left<n and nums[left]>nums[index]: # nums[left],nums[index]=nums[index],nums[left] # heap(left,nums) # 先找左右节点哪个最大 if left<n and nums[left]>nums[maxindex]: maxindex=left if right<n and nums[right]>nums[maxindex]: maxindex=right if maxindex!=index: #说明有变化，换位置，然后递归 nums[maxindex],nums[index]=nums[index],nums[maxindex] heap(maxindex,nums,n) def heap_sort(nums): n=len(nums) #建堆,从最后一个非叶子节点开始，往下维护大根堆 for i in range(n//2-1,-1,-1): heap(i,nums,n) #排序，建堆后，第一个位置一定最大，移动到最后，然后再对第一个建堆维护 for i in range(n-1,0,-1): nums[0],nums[i]=nums[i],nums[0] heap(0,nums,i) return nums return heap_sort(nums)
class minheap: def __init__(self,arr=None): self.heap=[] if arr: self.heapify(arr)
def __heapdown(self,index:int,n:int): left=index*2+1 right=index*2+2 minindex=index if right<n and self.heap[right]<self.heap[minindex]: minindex=right if left<n and self.heap[left]<self.heap[minindex]: minindex=left if minindex!=index: self.heap[minindex],self.heap[index]=self.heap[index],self.heap[minindex] self.__heapdown(minindex,n) def heapify(self,arr:list): self.heap=arr[:] n = len(self.heap) # 从最后一个非叶子节点开始，逆序遍历，依次下沉 for i in range(n // 2 - 1, -1, -1): self.__heapdown(i, n)
def heappop(self): if not self.heap: # ✅ 添加空堆检查 return None if len(self.heap) == 1: # ✅ 只有一个元素时直接弹出 return self.heap.pop() #先和最后一个元素交换，然后pop，再下沉操作 n=len(self.heap)-1 self.heap[0],self.heap[n]=self.heap[n],self.heap[0] #下沉操作 self.__heapdown(0,n)# ✅ 修正：传入 n 而不是 n-1，这个n是数量，不是下标
#返回最大值并弹出 return self.heap.pop() def heappush(self,num:int): self.heap.append(num) #进行上浮操作，以此比较父亲节点 index=len(self.heap)-1 while index>0: parent=(index-1)//2 if self.heap[index]<self.heap[parent]: self.heap[index],self.heap[parent]=self.heap[parent],self.heap[index] index=parent else: break
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: #递归版 def preorderTraversal(root: Optional[TreeNode]) -> List[int]: ans=[] def dfs(node:TreeNode): if not node: return ans.append(node.val) if node.left:dfs(node.left) if node.right:dfs(node.right) dfs(root) return ans #栈 def preorderTraversal_stack(root: Optional[TreeNode]) -> List[int]: ans=[] stack=[] stack.append(root) while stack: node:TreeNode=stack.pop() if not node: continue ans.append(node.val) if node.right:stack.append(node.right)#注意和dfs的差别 if node.left:stack.append(node.left) return ans
class Solution: def levelOrder(root: Optional[TreeNode]) -> List[List[int]]: ans=[] queue=deque() if not root:return ans queue.append(root) while queue: n=len(queue) temp=[] for _ in range(n): node:TreeNode=queue.popleft() if not node:continue temp.append(node.val) if node.left:queue.append(node.left) if node.right:queue.append(node.right) ans.append(temp) return ans
class Solution: def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder and not inorder: return None hashmap={} for index,val in enumerate(inorder): hashmap[val]=index n=len(preorder) def dfs(in_left,in_right,pre_left,pre_right): if in_right-in_left<0: return None pivot_index=hashmap[preorder[pre_left]] node=TreeNode() node.val=preorder[pre_left] size=pivot_index-in_left node.left=dfs(in_left,pivot_index-1,pre_left+1,pre_left+size) node.right=dfs(pivot_index+1,in_right,pre_left+size+1,pre_right)
