算法笔记

排序

算法	时间	空间	稳定
快排	O(n log n)	O(log n)	否
归并	O(n log n)	O(n)	是
堆排	O(n log n)	O(1)	否

二分查找

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

动态规划三步

1. 定义状态 dp[i] 的含义
2. 推导状态转移方程
3. 确定边界条件

常见题型

• 双指针（数组/字符串）
• 滑动窗口（子串/子数组）
• BFS/DFS（图/树遍历）
• 回溯（排列/组合）