算法思路与模板

官方文档：https://leetcode.cn/ | https://oi-wiki.org/
适用范围：LeetCode 刷题、算法面试（2026-05-07 整理）

二分查找

二分查找要求序列有序，每次将搜索范围缩减一半，时间复杂度 O(log n)。

左闭右闭 [left, right]

def binary_search(nums, target):
    left, right = 0, len(nums) - 1  # 右端点可取到

    while left <= right:             # 区间非空条件
        mid = left + (right - left) // 2  # 避免大数溢出（Python 无此问题，但习惯写法）
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

左闭右开 [left, right)

def binary_search_open(nums, target):
    left, right = 0, len(nums)  # 右端点不可取到

    while left < right:          # 区间非空条件
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid          # 不是 mid - 1

    return -1

查找左边界（第一个 >= target 的位置）

def lower_bound(nums, target):
    """
    返回 nums 中第一个 >= target 的索引。
    若所有元素 < target，返回 len(nums)。
    等价于 bisect.bisect_left(nums, target)。
    """
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid  # 可能是答案，但继续收缩右边界

    return left

查找右边界（最后一个 <= target 的位置）

def upper_bound(nums, target):
    """
    返回 nums 中第一个 > target 的索引。
    等价于 bisect.bisect_right(nums, target)。
    最后一个 <= target 的位置为 upper_bound - 1。
    """
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left

Python bisect 模块

import bisect

nums = [1, 3, 3, 5, 7]
bisect.bisect_left(nums, 3)   # 1，第一个 3 的位置
bisect.bisect_right(nums, 3)  # 3，最后一个 3 右侧的位置
bisect.insort_left(nums, 4)   # 原地插入，保持有序

二分查找的常见变体

• 在旋转排序数组中查找：先判断哪半段有序，再决定收缩方向
• 查找峰值：转化为"找第一个比右侧大的元素"
• 最小化最大值 / 最大化最小值：答案具有单调性时可二分答案

双指针

对向双指针

两个指针从两端向中间收缩，常用于有序数组。

def two_sum_sorted(nums, target):
    """有序数组中找两数之和"""
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []


def is_palindrome(s):
    """判断字符串是否为回文"""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

同向双指针（快慢指针）

def remove_duplicates(nums):
    """原地删除有序数组中的重复元素，返回新长度"""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1


def find_middle(head):
    """链表找中间节点（快慢指针）"""
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # 偶数长度时返回右中间节点

滑动窗口模板

滑动窗口维护一个满足条件的区间 [left, right]，right 不断向右扩张，条件不满足时收缩 left。

from collections import defaultdict

def sliding_window(s, pattern):
    """
    找到 s 中包含 pattern 所有字符的最小子串（最小覆盖子串）。
    时间复杂度 O(n)。
    """
    need = defaultdict(int)
    for c in pattern:
        need[c] += 1

    window = defaultdict(int)
    left = right = 0
    valid = 0          # window 中满足 need 条件的字符数
    start, min_len = 0, float('inf')

    while right < len(s):
        # 扩张窗口
        c = s[right]
        right += 1
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1

        # 收缩窗口
        while valid == len(need):
            if right - left < min_len:
                start = left
                min_len = right - left
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return s[start:start + min_len] if min_len != float('inf') else ""

滑动窗口通用框架：

def sliding_window_template(nums):
    left = 0
    window_state = {}   # 记录窗口内状态
    result = ...        # 根据题目初始化

    for right in range(len(nums)):
        # 1. 将 nums[right] 加入窗口
        # window_state 更新

        # 2. 判断是否需要收缩左边界
        while window_invalid(window_state):
            # 将 nums[left] 移出窗口
            # window_state 更新
            left += 1

        # 3. 更新答案
        # result = update(result, right - left + 1)

    return result

动态规划

状态定义思路

1. 确定"子问题"：原问题可以分解为哪些规模更小的同类问题
2. 定义 dp[i] 或 dp[i][j] 的含义，要足够清晰
3. 推导状态转移方程
4. 确定初始状态（边界条件）
5. 确定计算顺序（确保依赖的子问题先计算）

线性 DP

def longest_increasing_subsequence(nums):
    """
    最长递增子序列（LIS），O(n²) 版本。
    dp[i] = 以 nums[i] 结尾的 LIS 长度。
    """
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


def longest_common_subsequence(text1, text2):
    """
    最长公共子序列（LCS），O(m*n)。
    dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度。
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

背包问题

01 背包

每件物品最多选一次。dp[j] = 容量为 j 时的最大价值，逆序遍历容量防止重复选取。

def knapsack_01(weights, values, capacity):
    """
    dp[j] = 容量恰好为 j（或至多为 j）时的最大价值。
    """
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        # 逆序遍历：确保每件物品只被选一次
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

完全背包

每件物品可选无限次，正序遍历容量。

def knapsack_complete(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        # 正序遍历：允许重复选取
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

区间 DP

区间 DP 的状态为区间 [i, j]，通常先枚举区间长度，再枚举左端点。

def matrix_chain_multiplication(dims):
    """
    矩阵链乘法：dims[i-1] x dims[i] 为第 i 个矩阵的尺寸。
    dp[i][j] = 计算矩阵 i 到 j 的最小乘法次数。
    """
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):         # 枚举区间长度
        for i in range(n - length + 1):    # 枚举左端点
            j = i + length - 1             # 右端点
            dp[i][j] = float('inf')
            for k in range(i, j):          # 枚举分割点
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

状态压缩 DP

当状态集合规模不大（通常 n <= 20）时，用整数的二进制位表示子集。

def traveling_salesman(dist):
    """
    旅行商问题（TSP），dp[mask][i] = 访问了 mask 表示的城市子集，
    当前在城市 i 时的最短路径。
    """
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 只访问了城市 0，在城市 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask >> u & 1):
                continue
            for v in range(n):
                if mask >> v & 1:  # v 已访问
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

    full_mask = (1 << n) - 1
    return min(dp[full_mask][i] + dist[i][0] for i in range(n))

空间优化（滚动数组）

当 dp[i] 只依赖 dp[i-1] 时，可将二维数组压缩为一维（01背包已展示）。

依赖前两行时用两个交替数组：

# dp[i][j] 依赖 dp[i-1][...] 时
prev = [0] * (n + 1)
curr = [0] * (n + 1)

for i in range(1, m + 1):
    for j in range(1, n + 1):
        curr[j] = ...  # 使用 prev[j], prev[j-1], curr[j-1]
    prev, curr = curr, prev  # 交换

回溯

回溯是在决策树上的 DFS，通过"选择 -> 递归 -> 撤销选择"枚举所有可能。

通用模板

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])  # 注意深拷贝
        return

    for choice in choices:
        if is_valid(choice, path):
            path.append(choice)        # 做选择
            backtrack(path, new_choices)
            path.pop()                 # 撤销选择

排列

def permutations(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result

组合

def combinations(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        # 剪枝：剩余元素不足以填满 path 时停止
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

子集

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # 每个状态都是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

剪枝策略

贪心

适用场景判断

贪心策略成立需要满足贪心选择性质：每一步的局部最优选择不影响后续子问题的最优性。

常见贪心问题特征：

判断贪心是否正确：可用数学归纳法或反证法证明，或构造反例推翻。无法证明时考虑 DP。

排序算法

时间/空间复杂度与稳定性

Python 内置 sorted() 和 list.sort() 使用 Timsort，实际使用中直接调用即可。

快速排序

import random

def quick_sort(nums, left, right):
    if left >= right:
        return
    pivot_idx = partition(nums, left, right)
    quick_sort(nums, left, pivot_idx - 1)
    quick_sort(nums, pivot_idx + 1, right)


def partition(nums, left, right):
    # 随机化 pivot，规避最坏情况
    rand_idx = random.randint(left, right)
    nums[rand_idx], nums[right] = nums[right], nums[rand_idx]

    pivot = nums[right]
    i = left - 1  # i 指向小于 pivot 区域的右边界

    for j in range(left, right):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]

    nums[i + 1], nums[right] = nums[right], nums[i + 1]
    return i + 1

快速选择（第 K 大元素）：

def find_kth_largest(nums, k):
    """
    平均 O(n) 找第 k 大元素（1-indexed）。
    """
    def quick_select(left, right, target_idx):
        if left == right:
            return nums[left]
        pivot_idx = partition(nums, left, right)
        if pivot_idx == target_idx:
            return nums[pivot_idx]
        elif pivot_idx < target_idx:
            return quick_select(pivot_idx + 1, right, target_idx)
        else:
            return quick_select(left, pivot_idx - 1, target_idx)

    return quick_select(0, len(nums) - 1, len(nums) - k)

归并排序

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

LeetCode 高频题分类

数组

字符串

树

from collections import deque

def level_order(root):
    """层序遍历，返回每层节点值的列表"""
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

动态规划高频题

图（拓扑/最短路）

踩坑与注意事项

• Python 整数无溢出，但浮点数比较应用 math.isclose，不要直接 ==。
• 回溯将列表加入结果时必须 result.append(path[:])，不能直接 append(path)，否则所有结果指向同一列表。
• 动态规划初始化二维数组用列表推导 [[0]*n for _ in range(m)]，不能用 [[0]*n]*m（所有行共享引用）。
• 二分查找中 mid = (left + right) // 2 可能导致其他语言整数溢出，Python 不受影响，但养成写 left + (right - left) // 2 的习惯便于跨语言复用。
• 快速排序最坏情况为 O(n²)（已排序数组 + 固定 pivot），面试实现时务必加随机化 pivot。
• 记忆化搜索（自顶向下 DP）可直接用 @functools.lru_cache(maxsize=None) 装饰递归函数，避免手动维护缓存字典。

最佳实践

解题框架：拿到题先问自己这几个问题

1. 数据规模：n 是多少？决定允许的时间复杂度（n≤20 → 指数；n≤1000 → O(n²)；n≤10⁶ → O(n log n) 或 O(n)）
2. 问最优还是计数？最优值 → 动态规划；可行性 → 贪心/BFS；计数 → 组合数学/DP
3. 数据是否有序？有序 → 二分；无序且频繁查找 → 排序或哈希
4. 是否需要回溯？求所有解/排列组合 → 回溯；子集类问题 → 位运算枚举

算法选型速查

DP 状态设计套路

dp[i]    = 考虑前 i 个元素时的最优解（线性 DP）
dp[i][j] = 考虑前 i 个、前 j 个时的最优解（区间/匹配 DP）
dp[mask] = 集合状态为 mask 时的最优解（状压 DP）

转移方程写法：先定义"最后一步做了什么"，再枚举最后一步的所有可能。

面试代码规范

• 先用简单示例手动验证思路，再写代码
• 边界条件：空输入、单元素、全相同元素
• 命名清晰：用 left/right 而非 i/j、用 result 而非 res（面试可用缩写）
• 复杂度分析：写完代码后主动说时间和空间复杂度

常见陷阱

陷阱：回溯时直接 append(path) 导致结果全为空

现象： 回溯搜索完成后，result 中所有子列表都是空的（或内容相同），明明打印过正确路径却没有保存下来。

原因： Python 列表是引用类型，result.append(path) 保存的是同一个 path 对象的引用。回溯过程中 path 被反复修改，所有已保存的引用最终指向同一个空（或最终状态）列表。

解决： 加入结果时拷贝一份：result.append(path[:])。

def backtrack(path, start):
    if condition:
        result.append(path[:])  # 浅拷贝，不是 append(path)
        return
    for i in range(start, n):
        path.append(nums[i])
        backtrack(path, i + 1)
        path.pop()

陷阱：二维 DP 数组用乘法初始化导致所有行共享引用

现象： 修改 dp[0][0] 后，dp[1][0]、dp[2][0] 等也随之改变，DP 结果完全错误。

原因： [[0] * n] * m 创建的是 m 个指向同一子列表的引用，不是 m 个独立的列表。

解决： 用列表推导式创建二维数组。

# 错误：所有行共享同一内存
dp = [[0] * n] * m

# 正确：每行独立
dp = [[0] * n for _ in range(m)]

陷阱：二分查找死循环（循环条件或 mid 计算错误）

现象： while left <= right 的二分搜索死循环；或找到目标但返回了错误的索引。

原因： 最常见的两种错误：① 边界更新写成 left = mid 或 right = mid（不含 +1/-1 步进）导致死循环；② 混用开/闭区间模板（半开区间 [left, right) 与闭区间 [left, right] 的终止条件和边界更新不同）。

解决： 选一种模板并严格遵守。最常用的闭区间模板：

left, right = 0, len(nums) - 1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        left = mid + 1   # 必须 +1
    else:
        right = mid - 1  # 必须 -1
return -1

参见

• 数据结构完全参考 — 链表、树、图、堆的实现与操作
• Python高级面试题 — 算法题 Python 实现技巧
• itertools与functools完全指南 — lru_cache、reduce、combinations 等工具