[力扣] 分类题集 (月频更新)
天赐细莲
6634
2022.08.15
2024.06.03
发布于 未知归属地
C++周赛数据结构与算法每日一题双周赛题集学习分享

  1. 🎊前言

    1. ☠️说明

    2. ☠️相关连接

      1. 🔖题单

        1. 🕹️DB专题
        2. 🕹️数据结构
        3. 🕹️图论
        4. 🕹️其他

      2. 🔖个人文章

      3. 🔖官方资讯

      4. 🔖扣友文章

  2. 🏷️枚举

  3. 🏷️数组

    1. 常规
    2. 反转数组
    3. 矩阵
    4. 分组循环

  4. 🏷️数学

    1. 公式类
    2. 容斥原理
    3. 进制转换
    4. 乘法原理
    5. 幂的运算
    6. 同余原理
    7. 计数相关
    8. 阶乘相关
    9. 对数相关
    10. 计算贡献
    11. 质数/素数
    12. gcd
    13. lcm
    14. 贝祖定理
    15. 简单规律
    16. 经典模型
    17. 取模
    18. 浮点精度

  5. 🏷️二分查找

    1. 裸二分
    2. 经典应用
    3. 最大值最小 & 最小值最大
    4. 有序矩阵的二分
    5. 树的二分
    6. 特殊的二分
    7. 三分
    8. 其他

  6. 🏷️位运算

    1. 简单基础应用
    2. 异或
    3. 与
    4. lowbit
    5. 二进制枚举
    6. 状态压缩
    7. 大范围化为for 32/64
    8. 杂七杂八
    9. 前辈的经验

  7. 🏷️倍增

    1. ST表
    2. 树上倍增

  8. 🏷️滑动窗口

    1. 定长窗口
    2. 不定长窗口

  9. 🏷️多指针

  10. 🏷️双指针

    1. 单数组追逐 (块慢指针)
    2. 左右往中间追逐
    3. 双数组追逐

  11. 🏷️滑动窗口

    1. 定长窗口
    2. 不定长窗口

  12. 🏷️分治

    1. 典型分治的思想
    2. 字符串相关
    3. 矩阵快速幂
    4. 位运算分治

  13. 🏷️搜索

    1. 传统搜索
    2. 树的搜索
    3. 借助单调性

  14. 🏷️搜索(BFS)

    1. 杂
    2. 双向bfs
    3. 启发式搜索
    4. 多源bfs
    5. 其他

  15. 🏷️搜索(DFS)

    1. 经典例题
    2. 记忆化搜索
    3. 经典应用
    4. 多个dfs互套
    5. 永远想不到
    6. 递归<=>动归
    7. 时间戳
    8. 回溯

  16. 🏷️(DP)动态规划

    1. 经典dp
    2. 简单dp练习
    3. 最长递增子序列
    4. 线性dp
    5. 状态机dp
    6. 序列dp
    7. 矩阵形
    8. 以第i位截止的状态
    9. 辅助技巧细节
    10. 借助dp处理
    11. 转移点的搜索
    12. 将数组分割为 m 段
    13. 一些巧妙的题
    14. 永远想不到的dp

  17. 🏷️前缀和

    1. 基础
    2. 二维前缀和
    3. 多方向
    4. 前缀乘积
    5. 前缀树
    6. 前缀和贡献
    7. 异或前缀和

  18. 🏷️差分

    1. 线性累计
    2. 有序集合
    3. 逆向差分
    4. 二维差分

  19. 🏷️链表

    1. 基本功
    2. 各种应用
    3. 快慢指针
    4. 双向链表
    5. std::list

  20. 🏷️栈

    1. 基础应用
    2. 单调栈
    3. 对顶栈
    4. 其他技巧

  21. 🏷️队列

    1. 循环队列
    2. 单调队列
    3. 二维单调队列
    4. 双端队列

  22. 🏷️串

    1. KMP
    2. 扩展KMP (Z函数)
    3. manacher 算法
    4. 最小表示法
    5. Rabin-Karp 字符串哈希
    6. AC自动机
    7. 中心扩展法
    8. 破环成链
    9. 其他

  23. 🏷️树

    1. 经典应用
    2. 二叉搜寻树
    3. 完美二叉树
    4. 从边的角度分析
    5. LCA祖先
    6. 基环树
    7. 其他

  24. 🏷️堆

    1. 多路归并
    2. 堆模拟
    3. multiset
    4. 其他

  25. 🏷️图

    1. 拓扑排序
    2. 最短路
    3. 联通分量
    4. 费用流
    5. Tarjan 算法
    6. 二分图
    7. 欧拉回路

  26. 🏷️分块

  27. 🏷️哈希

    1. 自定义哈希
    2. 下标映射
    3. 链地址
    4. 离散化
    5. 哈希记录前缀状态

  28. 🏷️排序

  29. 🏷️思维

  30. 🏷️贪心

    1. 经典贪心
    2. 奇偶贪心
    3. 栈-贪心
    4. 堆-贪心
    5. 中值贪心
    6. 取最大贡献
    7. 排序和大小比较
    8. 体系平衡
    9. 反悔贪心
    10. 逆序遍历
    11. 其他

  31. 🏷️脑筋急转弯

    1. 逆向思维
    2. 构造
    3. 稳态

  32. 🏷️博弈

    1. 经典博弈
    2. 数值大小问题
    3. 能取问题

  33. 🏷️几何

    1. 杂
    2. 向量积
    3. 投影+容斥
    4. 直线的截距表示法

  34. 🏷️排列组合

  35. 🏷️随机与概率

    1. 随机
    2. 概率
    3. 随机水题

  36. 🏷️优化复杂度

    1. 置换
    2. 摩尔投票
    3. 一次遍历
    4. 原地哈希

  37. 🏷️统计类

    1. 公式变形

  38. 🏷️其他算法

    1. 操作系统
    2. 人工智能
    3. 括号类
    4. 枚举
    5. 序列化
    6. RMQ
    7. 逆序对
    8. 区间覆盖
    9. 扫描
    10. 分组讨论
    11. 子序列
    12. 贡献
    13. 路径生成
    14. 离线算法

  39. 🏷️模拟

    1. 分类讨论
    2. 构造
    3. 矩阵
    4. 周期
    5. 容器运用
    6. 环状
    7. 其他

  40. 🏷️找规律

  41. 🏷️读题题

  42. 🏷️一题多解（好题）

  43. 🏷️API

  44. END

🎊前言

☠️说明

本文链接较多，容易被审核噶掉，需要查看的可以私聊我或者看我的个人简介。

☠️相关连接

🔖题单

🕹️DB专题

🕹️数据结构

🕹️图论

🕹️其他

🔖个人文章

力扣题集：

🔖官方资讯

🔖扣友文章

🏷️枚举

题目备注
970. 强整数双指针枚举
2437. 有效时间的数目枚举所有case判断是否合法
1016. 子串能表示从 1 到 N 数字的二进制串枚举可构造的所有情况
447. 回旋镖的数量枚举配对

🏷️数组

常规

题目备注
1093. 大样本统计多状态模拟
2352. 相等行列对矩阵行列遍历
LCP 41. 黑白翻转棋矩阵8方向遍历

反转数组

题目备注
189. 轮转数组分割两端，分别反转
gcd分桶，每个桶自循环

矩阵

最讨厌矩阵排序类

题目备注
1572. 矩阵对角线元素的和对角线遍历
1329. 将矩阵按对角线排序对角线遍历

分组循环

题目备注
228. 汇总区间官解评论下，灵神有题单
56. 合并区间区间型
2760. 最长奇偶子数组多条件限制

🏷️数学

公式类

题目备注
1185. 一周中的第几天蔡勒（Zeller）公式
507. 完美数完美数
对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
258. 各位相加数根_百度百科 (baidu.com)
同余原理
319. 灯泡开关[1~n] 中完全平方数的个数
2485. 找出中枢整数简单公式解方程
1954. 收集足够苹果的最小花园周长规律型公式推导
2739. 总行驶距离贡献类推公式

容斥原理

题目备注
435. 无重叠区间排序+端点容斥
223. 矩形面积IOU（数学术语）_百度百科
2409. 统计共同度过的日子数日期累计
2652. 倍数求和公因数，公倍数

进制转换

题目备注
504. 七进制数10转R进制
405. 数字转换为十六进制数补码
2396. 严格回文的数字相邻进制的差异
1663. 具有给定数值的最小字符串尾部贪心
1017. 负二进制转换负二进制
1073. 负二进制数相加负二进制

乘法原理

题目备注
828. 统计子串中的唯一字符字串个数
172. 阶乘后的零统计5的个数
907. 子数组的最小值之和划分为左右两侧

幂的运算

题目备注
372. 超级次方扩展欧拉定理

同余原理

题目备注
258. 各位相加数根
2310. 个位数字为 K 的整数之和位数为k的数即 ai*10+k
6203. 矩阵中和能被 K 整除的路径矩阵搜索 借助同余压缩空间
1015. 可被 K 整除的最小整数周期性同余

计数相关

题目备注
856. 括号的分数考虑最初始的贡献和层数
1785. 构成特定和需要添加的最少元素向上取整
1419. 数青蛙多字符顺序计数
1054. 距离相等的条形码贪心计数
2661. 找出叠涂元素二维计数

阶乘相关

题目备注
793. 阶乘函数后 K 个零规律或者二分

对数相关

题目备注
713. 乘积小于 K 的子数组借助对数防止累乘溢出

计算贡献

题目备注
891. 子序列宽度之和无序集合->有序
1759. 统计同构子字符串的数目显示的统计化为单字母对前面累计的贡献
2171. 拿出最少数目的魔法豆从几何平面的角度来说就是抹平
还有这是典型的没说顺序有关就无脑排序

质数/素数

题目备注
6279. 数组乘积中的不同质因数数目分解质因数
6280. 范围内最接近的两个质数质数筛

gcd

题目备注
1979. 找出数组的最大公约数模板题
914. 卡牌分组gcd算分组大小
1447. 最简分数gcd(分子，分母) == 1 判断是否是最简分数
189. 轮转数组gcd分桶，每个桶自循环
1819. 序列中不同最大公约数的数目gcd分组
子序列
2427. 公因子的数目公因子的数目

lcm

题目备注
878. 第 N 个神奇数字lcm
容斥
2513. 最小化两个数组中的最大值lcm
容斥
二分
2455. 可被三整除的偶数的平均值(x%a && x%b) => (x%lcm(a,b))

贝祖定理

贝祖定理 裴蜀定理

ax + by = gcd(a, b) 必存在正数解x,y使得等式成立

扩展1 =>

ax + by = c 若 gcd(a, b) | c 成立,则原式成立

x|y => x是y的因数

扩展2 =>

Σ ai\*xi = gcd(a1 ··· ai) = S

题目备注
365. 水壶问题典型的倒水问题
1234. 替换子串得到平衡字符串sum(xa) = 0

简单规律

题目备注
1138. 字母板上的路径直角坐标步长
670. 最大交换数位的贡献贪心

经典模型

题目备注
1240. 铺瓷砖Minimum tiling of a rectangle by squares
1276. 不浪费原料的汉堡制作方案鸡兔同笼

取模

题目备注
2575. 找出字符串的可整除数组经典取模迭代

浮点精度

题目备注
1883. 准时抵达会议现场的最小跳过休息次数动态规划

🏷️二分查找

裸二分

题目备注
704. 二分查找最基础的裸模板
35. 搜索插入位置查找位置
34. 在排序数组中查找元素的第一个和最后一个位置查找位置

经典应用

题目备注
278. 第一个错误的版本题解：(二分) 逼近类二分搜索 (模板题) - 第一个错误的版本 - 力扣（LeetCode）
69. x 的平方根自己实现sqrt

最大值最小 & 最小值最大

题目备注
2439. 最小化数组中的最大值纯按照题意模拟
410. 分割数组的最大值经典最大值最小
1760. 袋子里最少数目的球经典最大值最小
2594. 修车的最少时间这种题容易往背包想

有序矩阵的二分

378. 有序矩阵中第 K 小的元素

题目备注
378. 有序矩阵中第 K 小的元素划分矩阵
668. 乘法表中第k小的数乘法表的特殊性
719. 找出第 K 小的数对距离爬楼梯式检测

树的二分

一半在二叉搜索树中比较多

题目备注
面试题 04.06. 后继者根据BST性质，直接二分找答案

特殊的二分

题目备注
面试题 04.06. 后继者基于树的二分
792. 匹配子序列的单词数根据下标的递增性，分组二分

三分

题目备注
462. 最少移动次数使数组元素相等 II无限区间找最值

其他

题目备注
1234. 替换子串得到平衡字符串前缀和+二分
滑动窗口
2517. 礼盒的最大甜蜜度check构造，有序递增
2258. 逃离火灾基于图论搜索的二分
2300. 咒语和药水的成功对数普通线性二分+贡献

🏷️位运算

简单基础应用

题目备注
1812. 判断国际象棋棋盘中一个格子的颜色奇偶判断
1780. 判断一个数字是否可以表示成三的幂的和三进制
191. 位1的个数二进制1的个数
int cnt = __builtin_popcount(x);
231. 2 的幂n = n &(n-1); //消去最后一个1

异或

题目备注
6201. 找出前缀异或的原始数组异或移项，即等式两边同时异或
2424. 最长上传前缀看总贡献
982. 按位与为零的三元组确定两个数，枚举第三个数的贡献

与

题目备注
2401. 最长优雅子数组两两可与，全部累计与

lowbit

lowbit(x) return x & -x;

n&(~n+1) == n&-n //补码

题目备注
191. 位1的个数直接消尾1
231. 2 的幂消一次尾1判断
2438. 二的幂数组中查询范围内的乘积统计二进制每位的大小

二进制枚举

题目备注
2044. 统计按位或能得到最大值的子集数目模板题，纯按题意模拟
2397. 被列覆盖的最多行数矩阵遍历
1601. 最多可达成的换楼请求数目
805. 数组的均值分割折半搜索+数学

状态压缩

题目备注
1815. 得到新鲜甜甜圈的最多组数状压搜索

大范围化为for 32/64

题目备注
2317. 操作后的最大异或和考虑每一位的贡献
2354. 优质数对的数目累计1个数分组
2311. 小于等于 K 的最长二进制子序列贪心每个1的贡献

杂七杂八

题目备注
2401. 最长优雅子数组每两个数and为0，则这堆数字总的各个位最多只有一个1
xor相当于弹栈
1969. 数组元素的最小非零乘积对称性质（非常难转化思路和发现）

前辈的经验

题目备注
89. 格雷编码格雷码_百度百科 (baidu.com)
1238. 循环码排列格雷码
779. 第K个语法符号01排布前后，上下规律
面试题 05.02. 二进制数转字符串浮点数内存表示

🏷️倍增

ST表

题目备注
239. 滑动窗口最大值求RMQ

树上倍增

题目备注
1483. 树节点的第 K 个祖先参见个人主页站外博客

🏷️滑动窗口

定长窗口

题目备注
239. 滑动窗口最大值经典RMQ
1652. 拆炸弹环形窗口
2009. 使数组连续的最少操作数排序去重预处理
1052. 爱生气的书店老板标准定长窗口

不定长窗口

题目备注
2401. 最长优雅子数组双重判断
2379. 得到 K 个黑块的最少涂色次数简单计数

🏷️多指针

题目备注
2367. 算术三元组的数目三指针划分区域
927. 三等分三指针计数划分区域
264. 丑数 II类似多路归并
792. 匹配子序列的单词数多路递增

🏷️双指针

单数组追逐 (块慢指针)

题目备注
283. 移动零O(n)原地分离两个状态
905. 按奇偶排序数组O(n)原地分离两个状态

左右往中间追逐

题目备注
1616. 分割两个字符串得到回文串回文串变体
1574. 删除最短的子数组使剩余数组有序分成前中后三块区域
再二分搜索删除

双数组追逐

题目备注
777. 在LR字符串中交换相邻字符计数判断
2337. 移动片段得到字符串改编777
777. 在LR字符串中交换相邻字符相对先后关系
1023. 驼峰式匹配检验子序列
1031. 两个非重叠子数组的最大和双区间追逐
826. 安排工作以达到最大收益贪心维护最值

🏷️滑动窗口

定长窗口

题目备注
239. 滑动窗口最大值
567. 字符串的排列
219. 存在重复元素 II

不定长窗口

题目备注
2444. 统计定界子数组的数目划区域 + 计数
904. 水果成篮元素计数类

🏷️分治

典型分治的思想

题目备注
761. 特殊的二进制序列抽象成括号匹配
372. 超级次方配合了一些幂运算的性质

字符串相关

基本步骤

  1. 根据题意找出串中不符合条件的点（下标）
  2. 遍历点集（下标）（这就是分界点）
    1. 将串从该点分割左右两个字串
    2. 递归搜索两个字串
题目备注
1763. 最长的美好子字符串
395. 至少有 K 个重复字符的最长子串
856. 括号的分数括号匹配，去外层括号

矩阵快速幂

其实一半的线性dp都能写成矩阵快速幂

题目备注
剑指 Offer 64. 求1+2+…+n快速乘
50. Pow(x, n)快速幂
1220. 统计元音字母序列的数目矩阵快速幂

斐波那契矩阵递推公式

回归到最初的起始条件

位运算分治

题目备注
190. 颠倒二进制位分治反转二进制

🏷️搜索

传统搜索

题目备注
854. 相似度为 K 的字符串回溯+剪枝+启发式
886. 可能的二分法染色法分组标记
698. 划分为k个相等的子集排序剪枝

树的搜索

题目备注
779. 第K个语法符号01树 + 自底向上

借助单调性

题目备注
6202. 使用机器人打印字典序最小的字符串字母的单调增
2424. 最长上传前缀有序队列的单调性

🏷️搜索(BFS)

杂

题目备注
864. 获取所有钥匙的最短路径vis添加状压属性
1129. 颜色交替的最短路径有限制的nex点
1210. 穿过迷宫的最少移动次数状态非单个点
不难，耐心和基本功
1377. T 秒后青蛙的位置常规bfs维护可达点的概率
1654. 到家的最少跳跃次数证明边界(难)

双向bfs

题目备注
773. 滑动谜题

启发式搜索

启发式函数

判断优先级和含义

    1. 启发式函数
    1. 起始到当前的状态花费
    1. 当前到目标的理想状态
题目备注
854. 相似度为 K 的字符串剪枝技巧
675. 为高尔夫比赛砍树寻路

多源bfs

题目备注
1765. 地图中的最高点
934. 最短的桥两个联通两合并的最小步数

其他

题目备注
1263. 推箱子试步型(01BFS)

🏷️搜索(DFS)

经典例题

题目备注
46. 全排列next_permutation(begin(), end())
78. 子集获得子集
1219. 黄金矿工经典地图类回溯
784. 字母大小写全排列典型回溯
1752. 检查数组是否经排序和轮转得到经典回溯
2698. 求一个整数的惩罚数回溯基本功
1457. 二叉树中的伪回文路径回溯基本功

记忆化搜索

题目备注
6168. 恰好移动 k 步到达某一位置的方法数目明确记忆化的到底是什么东西

经典应用

题目备注
698. 划分为k个相等的子集状压或手写哈希
2293. 极大极小游戏迭代和dfs练习题

多个dfs互套

题目备注
913. 猫和老鼠本题的数据量加强了，dfs不能AC，但很值得学习

永远想不到

题目备注
638. 大礼包比较特殊的背包，适合写搜索

递归<=>动归

题目备注
1223. 掷骰子模拟定义维度

时间戳

题目备注
2467. 树上最大得分和路径正向逆向时间戳碰撞

回溯

题目备注
1766. 互质树递归栈的状态记录，题意范围暴力枚举

🏷️(DP)动态规划

经典dp

此处不分具体dp类型，就是超级经典的dp各大o＊＊＊台都有甚至题面都几乎一样的dp

题目备注
300. 最长递增子序列贪心+二分查找 优化
1143. 最长公共子序列hdu-Advanced Fruits - 1503(含寻路)
53. 最大子序和和0点比较松弛
516. 最长回文子序列区间dp
264. 丑数 II其实这个也不知道算不算dp
1800. 最大升序子数组和最大子序和变体
790. 多米诺和托米诺平铺(经典dp) I型 L型 铺盖2*n - 多米诺和托米诺平铺 - 力扣（LeetCode）
1653. 使字符串平衡的最少删除次数【经典】考虑最后一个字母是什么
1638. 统计只差一个字符的子串数目以xx为结尾的dp
746. 使用最小花费爬楼梯爬楼梯加强版
2312. 卖木头块经典画线划分

简单dp练习

题目备注
1641. 统计字典序元音字符串的数目数学能力强的可以推公式

最长递增子序列

注意是子序列

本质就是依附于前面的状态更新

题目备注
646. 最长数对链二元组
435. 无重叠区间经典贪心(线性路径覆盖)
673. 最长递增子序列的个数
1713. 得到子序列的最少操作次数
2370. 最长理想子序列条件影响松弛范围
1691. 堆叠长方体的最大高度长方体最长递增子序列
1139. 最大的以 1 为边界的正方形线性重叠

线性dp

其实绝大多数dp都可以归纳到线性dp中

题目备注
983. 最低票价离散数据的dp
1269. 停在原地的方案数走路的方案数
940. 不同的子序列 II二维状态
552. 学生出勤记录 II典型的线性分类讨论
2369. 检查数组是否存在有效划分老老实实按题意转移
2318. 不同骰子序列的数目升维，显示的枚举所有情况
741. 摘樱桃矩阵路线
1824. 最少侧跳次数同一层再松弛一轮
1262. 可被三整除的最大和同余应用
2369. 检查数组是否存在有效划分题意清晰，书写较麻烦的dp

状态机dp

题目备注
801. 使序列递增的最小交换次数虽然是2^n可能性，但是紧跟相邻状态有关
935. 骑士拨号器简单dp，确定数字间的转移即可
1186. 删除一次得到子数组最大和为操作次数设定一个维度
1911. 最大子序列交替和奇偶交替

序列dp

序列dp题单:【宫水三叶】结合「贪心」的「序列 DP」运用题 - 最长定差子序列 - 力扣（LeetCode）

题目备注
2463. 最小移动总距离借助一个贪心结论
定义dp[][]表示前i个容量处理前j个物品
1218. 最长定差子序列最长递增子序列变体
哈希表(两数之和)
813. 最大平均值和的分组想区间dp一样不断松弛子区间

矩阵形

题目备注
1444. 切披萨的方案数二位差分辅助

以第i位截止的状态

题目备注
1043. 分隔数组以得到最大和经典的以第i位截止，能构造的最大值
1187. 使数组严格递增在第i位上，操作j次，最后一个(i)位置的最小数值
1105. 填充书架大胆往回搜索
1335. 工作计划的最低难度大胆往回搜索

辅助技巧细节

题目备注
6168. 恰好移动 k 步到达某一位置的方法数目走路的方案数 + offset
1774. 最接近目标价格的甜点成本两次01背包
根据阈值微调方法避免特判
2518. 好分区的数目背包
全集 - 补集
1027. 最长等差数列偏移量处理负数

借助dp处理

题目备注
849. 到最近的人的最大距离借助dp枚举所有情况

转移点的搜索

题目备注
1466. 重新规划路线二分搜索转移点
2865. 美丽塔 I借助单调栈，抹平数据
514. 自由之路环形与线性的转换

将数组分割为 m 段

这是一列比较典型的题，一般是三循环，注意循环的细节。

题目备注
410. 分割数组的最大值最大值最小，min-max混用

一些巧妙的题

题目备注
2645. 构造有效字符串的最少插入数分类讨论各种情况
优化

永远想不到的dp

题目备注
854. 相似度为 K 的字符串
2681. 英雄的力量前缀和+动规
1388. 3n 块披萨抽象为环形的打家劫舍
1997. 访问完所有房间的第一天基于前缀和且公式合并优化（难，什么玩意啊）

🏷️前缀和

基础

题目备注
1732. 找到最高海拔入门题
764. 最大加号标志四个方向
53. 最大子数组和经典
1749. 任意子数组和的绝对值的最大值经典(多组)

二维前缀和

题目备注
304. 二维区域和检索 - 矩阵不可变注意重叠部分

多方向

题目备注
1139. 最大的以 1 为边界的正方形多方向(优化暴力)
2106. 摘水果预处理单向，ans时双向

前缀乘积

题目备注
2438. 二的幂数组中查询范围内的乘积需要配合除法取模

前缀树

题目备注
1038. 从二叉搜索树到更大和树根据题意确定遍历顺序
2440. 创建价值相同的连通块平均分割前缀树

前缀和贡献

题目备注
1769. 移动所有球到每个盒子所需的最小操作数左右个数累计贡献
1664. 生成平衡数组的方案数奇偶前缀和
1156. 单字符重复子串的最大长度给滑动窗口贡献值
1402. 做菜顺序递增+0界限+贡献

异或前缀和

题目备注
1542. 找出最长的超赞子字符串有哨兵的异或前缀和

🏷️差分

线性累计

题目备注
2381. 字母移位 II典型应用
1109. 航班预订统计模板题
1094. 拼车模板题
798. 得分最高的最小轮调循环队列
2251. 花期内花的数目差分+离线查询

有序集合

比较冷门的解法，时间复杂度不好计算，一般用线段树处理的比较多

题目备注
715. Range 模块纯模板 区间覆盖型
732. 我的日程安排表 III每次在区间[start, end-1]+1，并返回整个区间的最大值
699. 掉落的方块也是覆盖类
855. 考场就座延迟删除 + 有序集合 + 优先队列
1797. 设计一个验证系统哈希 或 有序集合
1488. 避免洪水泛滥有序的删除元素

逆向差分

题目备注
2451. 差值数组不同的字符串规范首位置

二维差分

题目备注
2132. 用邮票贴满网格图二维差分+二维前缀和 综合题目

🏷️链表

基本功

题目备注
707. 设计链表基本功
206. 反转链表单向链表反转
6093. 设计一个文本编辑器双向链表运用
1669. 合并两个链表搜索插入位置
24. 两两交换链表中的节点双指针
23. 合并 K 个升序链表多路归并

各种应用

题目备注
1823. 找出游戏的获胜者约瑟夫环问题 (Josephe)

快慢指针

题目备注
143. 重排链表寻找链表中点 + 链表逆序 + 合并链表
876. 链表的中间结点双倍速度找中点
142. 环形链表 II龟兔赛跑算法

双向链表

题目备注
146. LRU 缓存灵活运用
460. LFU 缓存灵活运用
1670. 设计前中后队列维护中点

std::list

题目备注
6093. 设计一个文本编辑器双向链表运用

🏷️栈

基础应用

题目备注
946. 验证栈序列验证栈序列
636. 函数的独占时间模拟
20. 有效的括号经典应用
1003. 检查替换后的词是否有效线性连续删除

单调栈

灵神推荐的题单：两张图秒懂单调队列（Python/Java/C++/Go） - 和至少为 K 的最短子数组 - 力扣（LeetCode）

题目备注
496. 下一个更大元素 I模板题
1475. 商品折扣后的最终价格
901. 股票价格跨度pair<int, int>
2454. 下一个更大元素 IV双堆维护两条命，将堆优化成栈
2866. 美丽塔 II用栈维护前后缀
1944. 队列中可以看到的人数弹栈时计数（关键是思考在使用单调栈时维护状态的时机）
1793. 好子数组的最大分数核心是画成一个柱状图，以最低数值最一条水平线来统计矩形面积
1535. 找出数组游戏的赢家连续最大数目

对顶栈

题目备注
2296. 设计一个文本编辑器双向链表模拟
CP 24. 数字游戏中位数贪心

其他技巧

题目备注
856. 括号的分数添加虚拟哨兵
895. 最大频率栈分组栈

🏷️队列

循环队列

题目备注
622. 设计循环队列数据结构基本功
641. 设计循环双端队列数据结构基本功

单调队列

题目备注
面试题59 - II. 队列的最大值纯纯模板
239. 滑动窗口最大值超经典模板题
862. 和至少为 K 的最短子数组前缀和的单调队列
1438. 绝对差不超过限制的最长连续子数组双指针维护真正窗口
单调队列维护窗口最值
2398. 预算内的最多机器人数目双指针维护真正窗口
单调队列维护窗口最值
1687. 从仓库到码头运输箱子单调队列优化dp
本题难度极大
918. 环形子数组的最大和破环成链条，带有长度限制的单调队列
1499. 满足不等式的最大值基于贪心
1696. 跳跃游戏 VI经典优化dp

二维单调队列

题目备注
2373. 矩阵中的局部最大值模板题

双端队列

题目备注
2810. 故障键盘方向切换

🏷️串

个人感觉，字符串的很多相关算法，真的是前人智慧的闪耀

KMP扩展KMP
维护数据next[i] 表示模式串s[1, i]中相等的前后缀的最长长度z[i]表示s与其后缀s[i, n]的最长公共前缀的长度
算法流程双指针(i, j)
借助旧状态next[1~i - 1]加速计算新状态next[i]		盒子[l, r]
借助旧状态z[1~i - 1]加速计算新状态z[i]
世家复杂度O(n)O(n)
用途在字符串中查找字串
字符串的周期
统计每个前缀的出现次数
字符串压缩		匹配所有字串
本质不同字串数
字符串周期
扩展KMPmanacher 马拉车
数据维护z[i]表示s与其后缀s[i, n]的最长公共前缀的长度d[i]表示以i为中心的最长回文串的长度的一半
即回文半径
算法流程盒子[l, r]
借助旧状态z[1~i - 1]加速计算新状态z[i]找i的对应点i-l+1转移		盒子[l, r]
借助旧状态d[1~i - 1]加速计算新状态d[i]找i的对称点r-i+l转移

KMP

题目备注
28. 实现 strStr()模板题
796. 旋转字符串循环串拼接+匹配
1397. 找到所有好字符串数位dp + 状态机
1764. 通过连接另一个数组的子数组得到一个数组多组kmp

扩展KMP (Z函数)

题目备注
2223. 构造字符串的总得分和模板题

manacher 算法

原串的最大回文长度，是新串的最大半径-1

题目备注
5. 最长回文子串模板题
647. 回文子串计数

最小表示法

题目备注
899. 有序队列最小表示法模板
796. 旋转字符串两个串的关系
1752. 检查数组是否经排序和轮转得到根据规律可以一次遍历

Rabin-Karp 字符串哈希

题目备注
187. 重复的DNA序列模板
1044. 最长重复子串二分搜索
2223. 构造字符串的总得分和长前缀相等，短前缀必相等=>二分搜索
扩展kmp模板

AC自动机

题目备注
1032. 字符流后缀匹配
可以用别的方法，字典树，字符串哈希等

中心扩展法

题目备注
1638. 统计只差一个字符的子串数目左右贡献累计

破环成链

题目备注
2516. 每种字符至少取 K 个只取首尾或首尾相连
取单测直接特判，在链的滑动串口操作时会有特殊情况
1658. 将 x 减到 0 的最小操作数取单测直接特判，在链的滑动串口操作时会有特殊情况

其他

题目备注
1163. 按字典序排在最后的子串前缀匹配优化(根据题目优化)
1048. 最长字符串链判断子序列
466. 统计重复个数【难】周期性规律，循环匹配
2696. 删除子串后的字符串最小长度用栈维护连续的字符

🏷️树

LeetCode 序列化二叉树的格式

经典应用

题目备注
1026. 节点与其祖先之间的最大差值子树的最值
617. 合并二叉树合并树
1448. 统计二叉树中好节点的数目单线状态维护

二叉搜寻树

题目备注
669. 修剪二叉搜索树删除指定点
1373. 二叉搜索子树的最大键值和判断搜索树

完美二叉树

题目备注
2415. 反转二叉树的奇数层对称式的递归

从边的角度分析

题目备注
979. 在二叉树中分配硬币从入流和出流的角度思考

LCA祖先

题目备注
1123. 最深叶节点的最近公共祖先尝试递归一次性解决
2846. 边权重均等查询求LCA + 树形自顶向下维护
好题

基环树

题目备注
2127. 参加会议的最多员工数基环树+拓扑排序

其他

题目备注
654. 最大二叉树RMQ
779. 第K个语法符号二叉树左右孩子
1617. 统计子树中城市之间最大距离【难】【方法多】直径 + 乘法原理
1110. 删点成林树化森岭
2569. 更新数组后处理求和查询区间反转
2003. 每棵子树内缺失的最小基因值启发式合并
2673. 使二叉树所有路径值相等的最小代价自底向上贡献

🏷️堆

多路归并

题目备注
373. 查找和最小的 K 对数字模板
378. 有序矩阵中第 K 小的元素模板
1439. 有序矩阵中的第 k 个最小数组和套378

堆模拟

题目备注
1801. 积压订单中的订单总数自定义堆规则
1499. 满足不等式的最大值模板题

multiset

题目备注
1825. 求出 MK 平均值前后状态划分->三个multiset[前，中，后]

其他

题目备注
LCP 33. 蓄水有序增减+堆优化
2530. 执行 K 次操作后的最大分数纯模板
2558. 从数量最多的堆取走礼物纯模板
2462. 雇佣 K 位工人的总代价双堆贪心

🏷️图

拓扑排序

题目备注
207. 课程表裸题
210. 课程表 II裸题
802. 找到最终的安全状态模板
2050. 并行课程 III维护前驱时间dp
2603. 收集树中金币基于拓扑的性质，解析本题

最短路

算法描述时间复杂度(n:点数 m:边数)
Dijstra (朴素)适用于稠密图O(n^2)
Dijstra (堆优化)适用于稀疏图O(m*logn)
Floyd多源最短路O(n^3)
Bellman Frod边数限制（负权）O(n*m)
SPFA理论效率最高（负权）
（竞赛中正权图一直卡该算法）		O(k*m) (k一般为2)
Johnson使用带有负权的全员最短路O(n(n+m)logm)

联通分量

(图论) 连通分量(模板) + 强连通分量(模板)

题目备注
1971. 寻找图中是否存在路径判断联通性模板
并查集，dfs,bfs
2316. 统计无向图中无法互相到达点对数模板
827. 最大人工岛联通分量合并
题目备注
1145. 二叉树着色游戏寻找割点将图分块

费用流

下面这三题用二分图是常规解

题目备注
2463. 最小移动总距离最小费用最大流
创建虚拟节点(源点汇点)
2172. 数组的最大与和记录负权值
1947. 最大兼容性评分和记录负权值
741. 摘樱桃经典矩阵割点

Tarjan 算法

题目备注
1192. 查找集群内的「关键连接」割边 (桥)
2646. 最小化旅行的价格总和LCA+树上差分

二分图

题目备注
886. 可能的二分法判断是否是二分图
785. 判断二分图判断二分图模板题
6256. 将节点分成尽可能多的组奇环->二分图不成立

欧拉回路

题目备注
753. 破解保险箱字符串抽象为图

🏷️分块

题目备注
901. 股票价格跨度求 <= cur

🏷️哈希

自定义哈希

// 仿函数定义哈希
struct MyHash {
    template <class T1, class T2>
    inline size_t operator() (const pair<T1, T2>& pair) const {
        size_t h1 = std::hash<T1>()(pair.first);
        size_t h2 = std::hash<T2>()(pair.second);
        return h1 ^ h2;
    }
};

unordered_set<pair<int,int>, MyHash> ust;
unordered_map<pair<int,int>, int, MyHash> ump;

// lambda法
auto myHash = [](const pair<int, int> &p) -> size_t {
    static hash<long long> hash_ll;
    return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
};
unordered_set<pair<int, int>, decltype(myHash)> points(0, myHash);

下标映射

题目备注
768. 最多能完成排序的块 II借助下标完成离散化
870. 优势洗牌田忌赛马
2325. 解密消息谁映射谁

链地址

题目备注
705. 设计哈希集合模拟hash set
706. 设计哈希映射模拟 hash map

离散化

离散化模板讲解

题目备注
1331. 数组序号转换纯模板
506. 相对名次逆序
剑指 Offer 51. 数组中的逆序对经典应用
1036. 逃离大迷宫二维离散化

哈希记录前缀状态

题目备注
1. 两数之和典
1814. 统计一个数组中好对子的数目经典移项
1590. 使数组和能被 P 整除两数之和变体，取模分类
面试题 17.05. 字母与数字两数之和变体，抽象成括号配对
1171. 从链表中删去总和值为零的连续节点基于前缀和的哈希记录

🏷️排序

题目备注
912. 排序数组真·数组排序
791. 自定义字符串排序计数排序
自定义排序

🏷️思维

题目备注
2808. 使循环数组所有元素相等的最少秒数环形相邻相同字符的贡献

🏷️贪心

经典贪心

题目备注
455. 分发饼干田忌赛马
870. 优势洗牌田忌赛马+映射
435. 无重叠区间路径线性覆盖
678. 有效的括号字符串利用可能的阈值贪心
2517. 礼盒的最大甜蜜度有序序列的，最小(大)差递增
1798. 你能构造出连续值的最大数目连续与不连续的思考
2136. 全部开花的最早一天时间系
605. 种花问题第一直觉

奇偶贪心

题目备注
1247. 交换字符使得字符串相同无序的题旧假设有序(便于)考虑
2216. 美化数组的最少删除数数量计数

栈-贪心

题目备注
6202. 使用机器人打印字典序最小的字符串出现字母不要怕，就是加个for26
处理最值方法：逆序记录，单调递增变量增加

堆-贪心

注意：默认是大顶堆，大顶堆，大顶堆

题目备注
630. 课程表 III
1353. 最多可以参加的会议数目开始和结束时间
1705. 吃苹果的最大数目开始和结束时间 + 计数
1139. 最大的以 1 为边界的正方形单个元素给整体的贡献

中值贪心

有些中值贪心的题可以用三分搜索秒杀

val = abs(o[0]-x) + abs(o[1]-(x+1)) ... + abs(o[m-1]-(x+m-1))

根据 绝对值不等式 得出当这个x是区间的中值时，val最小

题目备注
1703. 得到连续 K 个 1 的最少相邻交换次数固定窗口+开绝对值计算
462. 最小操作次数使数组元素相等 II简单三分
2033. 获取单值网格的最小操作数二维压一维 + 中值贪心模板
2448. 使数组相等的最小开销三分秒hard

取最大贡献

题目备注
1775. 通过最少操作次数使数组的和相等[1->6] == [6->1]
1753. 移除石子的最大得分最大带最小
2335. 装满杯子需要的最短总时长最大带最小
1465. 切割后面积最大的蛋糕组合的贡献

排序和大小比较

题面备注
1754. 构造字典序最大的合并字符串比大小比较后继
2037. 使每位学生都有座位的最少移动次数 - 力扣（LeetCode）经典排序
1144. 递减元素使数组呈锯齿状给哪类状态作用更有效(无用)
1053. 交换一次的先前排列字典序的大小比较

体系平衡

题目备注
1605. 给定行和列的和求可行矩阵贪心 + 整个体系稳定
1172. 餐盘栈分类讨论
1017. 负二进制转换分类讨论+滑动窗口
2611. 老鼠和奶酪两个对象分配资源
先统一分配给一个再贪心给第二个
2178. 拆分成最多数目的正偶数之和分组拆分
765. 情侣牵手两两匹配型
1702. 修改后的最大二进制字符串变化的传递

反悔贪心

题目备注
630. 课程表 III堆
871. 最低加油次数堆
LCP 30. 魔塔游戏堆
2813. 子序列最大优雅度非堆，线性结构
1673. 找出最具竞争力的子序列淘汰机制

逆序遍历

题目备注
2789. 合并后数组中的最大元素大鱼吃小鱼

其他

题目备注
2027. 转换字符串的最少操作次数利用单次操作对后继的影响
1813. 句子相似性 III后缀字符串大小比较
证明较难
1147. 段式回文本质也是搜，但怎么差别这么大呢
2735. 收集巧克力考虑所有状态，并伴随状态记录
2834. 找出美丽数组的最小和基于目标数值划分组，目标值相当于分界线
2952. 需要添加的硬币的最小数量数据线性递增

🏷️脑筋急转弯

题目备注
1460. 通过翻转子数组使两个数组相等冒泡排序
1072. 按列翻转得到最大值等行数化成相同的映射关系
2337. 移动片段得到字符串前后相对关系的贪心

逆向思维

题目备注
822. 翻转卡片游戏正反面考虑
57. 插入区间包含与不包含
1423. 可获得的最大点数总量-好算的
1466. 重新规划路线树形的正逆指向
1671. 得到山形数组的最少删除次数转化为最长递增子序列
2386. 找出数组的第 K 大和第k大转为第k小（难）
2192. 有向无环图中一个节点的所有祖先正逆建图

构造

题目备注
481. 神奇字符串A000002 - OEIS
双指针合并位单指针
2182. 构造限制重复的字符串基于字符个数构造指令序列

稳态

题目备注
1503. 所有蚂蚁掉下来前的最后一刻稳态+举例
2731. 移动机器人稳态+贡献
1726. 同积元组等式左右稳态，等价
689. 三个无重叠子数组的最大和区间互斥
1657. 确定两个字符串是否接近类型数量稳态
2549. 统计桌面上的不同数字收缩范围的贪心

🏷️博弈

(博弈) 常规博弈通用解法 (dp&记忆化dfs&SG函数) - 除数博弈 - 力扣（LeetCode）

1025. 除数博弈

经典博弈

题目备注
292. Nim 游戏巴什博弈

数值大小问题

题目备注
486. 预测赢家区间dp
dp[][]当前玩家在[i, j]较前一位的差值
464. 我能赢吗dfs借助下一个选手判断当前选手

能取问题

题目备注
1140. 石子游戏 II典型dfs博弈

🏷️几何

凸包问题模板：587. 安装栅栏 - 力扣（LeetCode）

杂

题目备注
1039. 多边形三角剖分的最低得分环形点化为线性
区间dp
812. 最大三角形面积三角形面积

向量积

向量积_百度百科

题目备注
2280. 表示一个折线图的最少线段数处理共线问题，判断是否为0

投影+容斥

题目备注
223. 矩形面积IOU（数学术语）_百度百科
1401. 圆和矩形是否有重叠定圆心，找矩形的所有点

直线的截距表示法

题目备注
1001. 网格照明直线的截距表示法

🏷️排列组合

题目备注
6168. 恰好移动 k 步到达某一位置的方法数目
357. 统计各位数字都不同的数字个数组合裸应用
907. 子数组的最小值之和单调栈+乘法原理
2514. 统计同位异构字符串数目有1个A,2个B,3个C 共有多少种排列
6! / (1! * 2! * 3!)

🏷️随机与概率

随机

题目备注
384. 打乱数组Fisher-Yates 洗牌算法
458. 可怜的小猪信息熵_百度百科
382. 链表随机节点蓄水池抽样
398. 随机数索引蓄水池抽样
528. 按权重随机选择随机抽取离散不重叠块
497. 非重叠矩形中的随机点随机抽取离散不重叠块

概率

题目备注
808. 分汤最大公因数，降低搜索范围
1227. 飞机座位分配概率先打表找规律，后证明

随机水题

题目备注
1157. 子数组中占绝大多数的元素本题难度极大，靠随机化可以骗ac

🏷️优化复杂度

置换

题目备注
1713. 得到子序列的最少操作次数将最长公共子序列化为最长递增子序列
2179. 统计数组中好三元组数目化为借助树状数组求解逆序对的形式

摩尔投票

抵消的思想

题目备注
面试题 17.10. 主要元素
229. 求众数 II

一次遍历

题目备注
747. 至少是其他数字两倍的最大数一次遍历获得最大值和次大值
1796. 字符串中第二大的数字一次遍历获得最大值和次大值
6020. 将数组划分成相等数对判断是否均配对 (处理奇偶)
283. 移动零原地分离数组中的两类元素(快慢指针)
905. 按奇偶排序数组原地分离数组中的两类元素(快慢指针)

原地哈希

题目备注
442. 数组中重复的数据找出序列中出现两次的元素
73. 矩阵置零矩阵类原地记录状态

🏷️统计类

公式变形

题目备注
2364. 统计坏数对的数目i < j且 j - i != nums[j] - nums[i]
2426. 满足不等式的数对数目0 <= i < j <= n - 1 且 nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

🏷️其他算法

操作系统

题目备注
502. IPO银行家算法
802. 找到最终的安全状态三色标记法
1233. 删除子文件夹递归+字典树
1487. 保证文件名唯一文件名哈希和递增
1096. 花括号展开 IIShell 编程，花括号展开
722. 删除注释纯模拟

人工智能

题目备注
427. 建立四叉树决策树
558. 四叉树交集决策树

括号类

题目备注
921. 使括号有效的最少添加基础栈思想

枚举

题目备注
1947. 最大兼容性评分和全排列

序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

题目备注
剑指 Offer 37. 序列化二叉树与主站 297 题相同

RMQ

题目备注
239. 滑动窗口最大值经典例题
654. 最大二叉树配合dfs
2398. 预算内的最多机器人数目仿239. 滑动窗口最大值
915. 分割数组根据题意最优可以1*O(n)

逆序对

题目备注
剑指 Offer 51. 数组中的逆序对经典例题
2426. 满足不等式的数对数目离散化+树状数组
315. 计算右侧小于当前元素的个数

区间覆盖

一般来说看着这类题就按照结束时间排序一下

1235和2008完全一致

1751多一个维度的限制次数

题目备注
435. 无重叠区间最长不重叠个数
1235. 规划兼职工作序列dp+二分
2008. 出租车的最大盈利序列dp+二分
1751. 最多可以参加的会议数目 II序列dp+二分 + 限制选择次数

扫描

题目备注
1353. 最多可以参加的会议数目

分组讨论

题目备注
927. 三等分找出标准组后其他组与之匹配

子序列

题目备注
891. 子序列宽度之和子序列作为一个整体，无序就是排序

贡献

题目备注
2444. 统计定界子数组的数目快慢指针追逐
795. 区间子数组个数左右贡献
快慢指针追逐
1769. 移动所有球到每个盒子所需的最小操作数序列移动左右贡献加减
2488. 统计中位数为 K 的子数组中位数通用操作
将数据类型划分为[小于k,k,大于k]三类
然后用括号匹配的思想统计
828. 统计子串中的唯一字符乘法原理 线性维护
907. 子数组的最小值之和乘法原理 单调栈维护

路径生成

题目备注
1092. 最短公共超序列【好题】dfs和dp 2*2 搜方案*逆序还原

离线算法

一般离线算法都会排序，然后类似扫描线一样的遍历

题目备注
1851. 包含每个查询的最小区间排序 + 优先队列
2736. 最大和查询二维偏序模板题

🏷️模拟

分类讨论

题目备注
2423. 删除字符使频率相同噩梦一样的周赛第一题
816. 模糊坐标不会存在多余的零
1330. 翻转子数组得到最大的数组值炒鸡难题
曼哈顿距离最大的四种情况
2244. 完成所有任务需要的最少轮数收缩周期，然后分类
2981. 找出出现至少三次的最长特殊子字符串 I讨论出贡献

构造

题目备注
667. 优美的排列 II差值的规律
2358. 分组的最大数量排序+贡献
1750. 删除字符串两端相同字符后的最短长度双端队列pop

矩阵

题目备注
2352. 相等行列对行列三重循环
498. 对角线遍历蛇皮矩阵

周期

题目备注
1041. 困于环中的机器人四个方向的周期性
1015. 可被 K 整除的最小整数同余
2582. 递枕头注意头尾，争取一次性推出公式

容器运用

题目备注
2353. 设计食物评分系统哈希表
1172. 餐盘栈有序集合维护不同状态

环状

题目备注
2682. 找出转圈游戏输家有规律步长

其他

题目备注
640. 求解方程"x+5-3+x=6+x-2" ===> "x=2"
8. 字符串转换整数 (atoi)状态机
2365. 任务调度器 II反离散
1700. 无法吃午餐的学生数量计时器
874. 模拟行走机器人可以用二分优化
2240. 买钢笔和铅笔的方案数简单互斥

🏷️找规律

题面备注
1739. 放置盒子前缀式递增
2511. 最多可以摧毁的敌人城堡数目从题意中转换规律
2813. 子序列最大优雅度逆向思维
2591. 将钱分给最多的儿童简单题中的战斗机
2336. 无限集中的最小数字无限序列递增

🏷️读题题

题目备注
2304. 网格中的最小路径代价简单动规
你们能读懂吗，反正我读不懂

🏷️一题多解（好题）

题目备注
2824. 统计和小于目标的下标对数目
1631. 最小体力消耗路径二分
并查集
最短路

🏷️API

这里不限定语言

比如C++没有replace()函数

题目备注
1455. 检查单词是否为句中其他单词的前缀前缀
1636. 按照频率将数组升序排序排序
784. 字母大小写全排列大小写字母转换
ch ^= 32
1678. 设计 Goal 解析器replace()
1732. 找到最高海拔cpp
partial_sum(begin(gain), end(gain), pre.begin() + 1);
1805. 字符串中不同整数的数目哈希表
415. 字符串相加python 字符表达式
1410. HTML 实体解析器注意replace顺序
⭐第999每日一题
1185. 一周中的第几天时间相关
1154. 一年中的第几天时间相关

END

后续会不断完善和更新，也不断被审核噶掉

评论 (4)