跳至主要內容

Leetcode‘s Summary

Dale2025/5/14大约 10 分钟

常用算法思想

算法思想核心逻辑典型应用场景主要步骤
暴力枚举 (Brute Force)穷举所有可能，适合数据量小或无更优解法时使用子集、全排列、简单模拟列举所有可能 → 检查每种情况
递归 (Recursion)问题自我调用自身，分解为更小子问题树遍历、分治、回溯设定终止条件 → 递归调用自身 → 合并结果
回溯 (Backtracking)递归试探所有可能，遇到不合法就回退组合、排列、N皇后、数独尝试选择 → 递归探索 → 发现不行就回退（撤销选择）
分治（Divide & Conquer）拆解为子问题递归解决后合并结果归并排序、快速排序、最近点对拆分问题 → 递归求解 → 合并结果
双指针 (Two Pointers)用两个指针遍历或扫描序列区间、排序、去重、链表指针初始化 → 同步/异步移动 → 满足条件时处理
滑动窗口 (Sliding Window)维护一个区间窗口，动态调整窗口边界子串/子数组、最短区间扩大窗口 → 满足条件时收缩窗口 → 记录最优解
哈希 (Hashing)用哈希表快速查找、去重、计数等查重、计数、映射构建哈希表 → 查找/插入/删除 → 处理冲突
栈/队列 (Stack/Queue)先进后出/先进先出，辅助递归、遍历括号匹配、层序遍历、单调栈入栈/队 → 弹出/出队 → 处理元素
单调栈/队列 (Monotonic Stack/Queue)维护单调性，区间最值下一个更大元素、滑动窗口最大值入栈/队时维护单调 → 弹出不符元素 → 记录答案
并查集 (Union Find)处理集合合并与查询连通性、分组、朋友圈初始化集合 → 合并集合 → 查询根节点
拓扑排序 (Topological Sort)有向无环图排序任务调度、依赖关系统计入度 → 队列弹出入度为0节点 → 更新入度
贪心（Greedy）每一步选择局部最优区间调度、最小生成树、跳跃游戏按规则排序/选择 → 每步取最优 → 得到全局解
动态规划（DP）分解为重叠子问题，递推求解背包、最长子序列、股票买卖定义状态 → 状态转移 → 递推填表
记忆化搜索 (Memoization)递归+缓存子问题结果，避免重复计算递归DP、树形DP递归求解 → 查询/保存子问题结果 → 返回答案
二分查找 (Binary Search)有序区间每次折半查找有序数组、最值判定设定左右边界 → 取中间值 → 判断调整区间
位运算 (Bit Manipulation)用二进制位操作优化空间和速度状态压缩、子集枚举构造掩码 → 按位操作 → 组合/判断状态
树状数组/线段树 (BIT/Segment Tree)区间查询与修改，适合动态数据结构区间和、区间最值构建树结构 → 查询/修改区间 → 递归/迭代更新
有限状态机（FSM）定义状态和转移规则，按输入切换KMP、正则表达式解析设计状态 → 按输入转移 → 处理输出
随机化算法（Randomized）利用随机性加速或近似求解快速排序、素数测试随机选择/采样 → 多次尝试 → 统计/判断
Meet in the Middle分两半分别求解后合并结果超大背包、子集和拆分集合 → 分别枚举 → 合并统计
扫描线（Sweep Line）按顺序扫描事件处理区间重叠矩形面积并、航班统计排序事件 → 顺序扫描 → 动态维护区间
启发式搜索（Heuristic）用估价函数优先探索更优路径A*、八数码、路径规划设计估价函数 → 优先队列扩展 → 找到目标
模拟退火（Simulated Annealing）概率性接受次优解跳出局部最优TSP、参数优化初始解 → 随机扰动 → 接受/拒绝新解
遗传算法（Genetic Algorithm）模拟进化逼近最优解组合优化、超参数调优编码种群 → 选择/交叉/变异 → 迭代进化

数学与几何相关算法

算法思想核心逻辑典型应用场景主要步骤
数论（Number Theory）利用质数、模运算、同余等性质解决问题RSA加密、约瑟夫环分析性质 → 设计公式/递推 → 求解
计算几何（Computational Geometry）向量、叉积等处理几何图形凸包、最近点对、线段相交坐标建模 → 几何运算 → 判断/统计
线性代数（Linear Algebra）矩阵运算、特征值分解等高维问题PCA、SVD、图像处理构建矩阵 → 运算/分解 → 得到结果

字符串处理专项

算法思想核心逻辑典型应用场景主要步骤
KMP算法部分匹配表避免重复匹配字符串模式匹配构建next表 → 匹配时跳转 → 找到所有位置
Trie（前缀树）树形结构存储字符串，共享前缀自动补全、词频统计构建树结构 → 插入/查找 → 统计/输出
后缀自动机（SAM）压缩后缀信息高效处理子串最长重复子串、子串计数构建自动机 → 状态转移 → 统计答案
Rabin-Karp滚动哈希快速比较子串多模式匹配、查重计算哈希 → 滑动窗口 → 比较/确认

图论进阶算法

算法思想核心逻辑典型应用场景主要步骤
网络流（Network Flow）建模为流量网络，求最大流/最小割任务分配、二分图匹配建图 → 增广路/推流 → 统计最大流
欧拉回路/路径遍历所有边且不重复邮路、DNA组装统计度数 → DFS/栈遍历 → 记录路径
Tarjan算法DFS求强连通分量、割点/桥社区发现、电路设计DFS遍历 → 记录时间戳 → 标记分量
匈牙利算法增广路径求二分图最大匹配任务分配、约会匹配匹配初始化 → DFS/BFS增广 → 更新匹配

特殊场景优化算法

算法思想核心逻辑典型应用场景主要步骤
离线算法（Offline）预处理所有查询后统一处理区间统计、莫队算法收集所有查询 → 排序/分组 → 统一处理
增量算法（Incremental）逐步添加数据动态维护结果实时数据流处理初始化结构 → 每次插入/更新 → 维护答案
近似算法（Approximation）牺牲精度换取效率NP难问题工程解法设计近似规则 → 迭代优化 → 得到可行解

Python 语法基础

一、核心基础语法（算法题必用）

1. 列表/数组操作（最高频）

算法题里80%的场景会用到列表，这些操作能让你少写循环：

# 1. 列表推导式（替代多层循环，快速生成/过滤数据）
# 例：生成1-10的平方，且只保留偶数平方
squares = [x*x for x in range(1,11) if x%2 == 0]  # [4, 16, 36, 64, 100]

# 2. 切片（快速取子数组、反转、步长取值）
nums = [1,2,3,4,5]
nums[::-1]          # 反转：[5,4,3,2,1]
nums[1:4:2]         # 从索引1到3，步长2：[2,4]
nums[:3]            # 前3个元素：[1,2,3]

# 3. 快速初始化固定长度数组（动态规划/图论常用）
dp = [0] * 100     # 长度100，初始值全0
dp = [float('inf')] * n  # 初始化无穷大（最短路/DP常用）

# 4. 列表的栈/队列操作（不用手动写栈/队列类）
# 栈：append() + pop()（O(1)）
stack = []
stack.append(1); stack.pop()  # 弹出最后一个元素

# 队列：append() + pop(0)（O(n)，小数据可用）
# 大数据用deque（O(1)，必记！）
from collections import deque
q = deque([1,2,3])
q.append(4); q.popleft()     # 弹出第一个元素：1

2. 字典/集合（哈希表，O(1)查找，高频）

算法题里用于「去重」「快速查找」「计数」：

# 1. 字典默认值（避免KeyError，哈希表计数常用）
from collections import defaultdict
# 例：统计数组元素出现次数
count = defaultdict(int)
nums = [1,2,2,3]
for num in nums:
    count[num] += 1  # {1:1, 2:2, 3:1}

# 2. 集合去重/判断存在（两数之和/滑动窗口常用）
s = set([1,2,2,3])  # {1,2,3}
if 2 in s:  # O(1)判断，比列表的in快100倍+

# 3. 有序字典（LRU缓存/需要保留插入顺序的场景）
from collections import OrderedDict
od = OrderedDict()
od[1] = 1; od[2] = 2
od.popitem(last=False)  # 弹出第一个插入的元素

3. 排序（自定义规则，高频考点）

# 1. 基础排序（默认升序）
nums = [3,1,2]; nums.sort()  # 原地排序：[1,2,3]
sorted_nums = sorted(nums)   # 返回新列表，不修改原列表

# 2. 自定义排序键（核心！中高难度题必用）
# 例1：按元素的绝对值排序
nums = [-3,1,-2]
sorted(nums, key=lambda x: abs(x))  # [1,-2,-3]

# 例2：按元组的第二个元素降序排序（贪心/区间题常用）
intervals = [(1,3), (2,1), (3,2)]
sorted(intervals, key=lambda x: -x[1])  # [(1,3), (3,2), (2,1)]

# 例3：多条件排序（先按第一个元素升序，再按第二个降序）
sorted(intervals, key=lambda x: (x[0], -x[1]))

二、中高难度算法题专属语法

1. 递归/回溯（DFS/排列组合/子集常用）

# 递归函数+参数简化（避免全局变量）
# 例：全排列问题（中难度高频）
def permute(nums):
    res = []
    # 回溯函数（嵌套定义，直接访问外层的res/nums，不用传参）
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path.copy())  # 注意copy！否则会修改原列表
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path, used)
                # 回溯（撤销选择）
                path.pop()
                used[i] = False
    backtrack([], [False]*len(nums))
    return res

permute([1,2,3])  # 输出所有排列：[[1,2,3],[1,3,2],...]

2. 堆（优先队列，TopK/贪心/最短路径必用）

import heapq

# 1. 小顶堆（Python默认，取TopK大元素需转成负数）
# 例：找数组中前K大的元素（高难度高频）
def topKFrequent(nums, k):
    count = defaultdict(int)
    for num in nums:
        count[num] += 1
    # 堆中存（-次数，元素），用小顶堆模拟大顶堆
    heap = []
    for num, cnt in count.items():
        heapq.heappush(heap, (-cnt, num))
    # 取前k个
    res = []
    for _ in range(k):
        res.append(heapq.heappop(heap)[1])
    return res

# 2. 堆的初始化（O(n)，比逐个push快）
nums = [3,1,2]
heapq.heapify(nums)  # 原地转成小顶堆：[1,3,2]

3. 位运算（中高难度题技巧，比加减乘除快）

# 常用位运算（异或/与/左移，二进制题常用）
a, b = 5 (0b101), 3 (0b011)
a ^ b  # 异或：0b110=6（相同为0，不同为1，两数之和/找唯一数常用）
a & b  # 与：0b001=1（判断奇偶：x&1==1 是奇数）
a << 1 # 左移1位：10（等价于*2，更快）
a >> 1 # 右移1位：2（等价于//2，更快）

# 例：不用加减乘除做加法（高难度面试题）
def add(a, b):
    while b != 0:
        carry = (a & b) << 1  # 进位
        a = a ^ b             # 无进位和
        b = carry
    return a

4. 生成器（处理大数据/无限序列，避免内存溢出）

# 例：生成斐波那契数列（大数据场景不用存所有数）
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        yield a  # 生成器，每次返回一个值，不占内存
        a, b = b, a+b

# 用的时候迭代，只取需要的数
for num in fib(10):
    print(num)  # 0,1,1,2,3,...

三、避坑点（算法题常错）

  1. 列表引用问题：递归/回溯中，res.append(path) 会存引用，必须用 path.copy() 或 path[:]；
  2. 整数溢出：Python无溢出，但面试时要提「其他语言需要处理」；
  3. 时间复杂度：list.pop(0) 是O(n)，大数据用 deque.popleft()（O(1)）；
  4. 默认参数陷阱：递归函数默认参数不要用可变对象（如 def dfs(path=[])），会累积值。

总结

  1. 中高难度算法题核心语法：列表推导式+字典/集合+排序自定义key+堆+递归回溯+位运算；
  2. 性能优化重点：用 deque 代替列表做队列，用 heapq 实现优先队列，用集合/字典做O(1)查找；
  3. 避坑关键：注意列表引用、默认参数、时间复杂度，优先用Python内置高效数据结构。
最近更新:
贡献者: shyu216
A place to jot down the picked up.
Copyright © 2026 Dale