代码：Pipeline Pattern + Service Layer 模式写复杂业务代码

Posted on Edited on In

数据结构

  1. 数组与矩阵 (核心模式归类)

    A. 原地修改 / 数组作为哈希表 (实现 $O(1)$ 额外空间)

    B. 矩阵遍历与坐标变换

    • 54. 螺旋矩阵【模式：四边界收缩；$(u, d, l, r)$ 指针随遍历向内挤压】
    • 36. 有效的数独【模式：一维化索引；利用 (r/3)*3 + c/3 映射九宫格】
    • 189. 轮转数组【模式：三次翻转；通过 reverse 实现 $O(1)$ 空间位移】
    • 31. 下一个排列【模式：标准算法；找 pivot -> 找更大数 -> 交换并反转】

    C. 双指针、贪心与接雨水 (处理单调性或边界)

    • 11. 盛最多水的容器【模式：对撞指针；每次移动较短边以求更大容积】
    • 42. 接雨水【模式：双指针/单调栈；核心是“木桶原理”，高度由短板决定】
    • 407. 接雨水 II【模式：BFS + 优先队列；从外向内收缩 3D 边界】
    • 283. 移动零【模式：快慢指针；一个负责遍历，一个负责存放非零值】
    • 228. 汇总区间【模式：分组循环 / 双指针；核心：通过 nums[j+1] != nums[j]+1 识别连续区间断点】
    • 134. 加油站【模式：贪心；记录总收益与局部余量判断起点】
    • 135. 分发糖果【模式：双向遍历；确保同时满足左右邻居约束】

    D. 前缀和与子数组 (处理区间和/积)

    E. 区间处理 (排序 + 贪心)

    • 56. 合并区间【模式：区间合并；核心：按起点排序，维护 [L, R]，利用 l <= cur_right 动态扩展右边界】
    • 57. 插入区间【模式：分类讨论；核心：将区间分为“左侧不重叠”、“中间重叠合并”、“右侧不重叠”三部分处理】
    • 452. 用最少数量的箭引爆气球【模式：区间交集；核心：按终点排序，贪心选择重叠区域的边缘】
    • 435. 无重叠区间【模式：贪心留空；核心：按终点排序，尽量保留先结束的区间，以给后续留出更多空间】
    • 253. 会议室 II【模式：上下车/差分思想；核心：将起点看作 +1，终点看作 -1，求最大并发数；或利用小顶堆维护当前结束时间】
    • 228. 汇总区间【模式：分组循环 / 双指针；核心：识别连续数字序列的断点】
    • 2580. 统计将重叠区间合并成组的方案数【模式：区间合并 + 组合数学；核心：合并后得到 m 个独立连通块，结果为 $2^m$】

    F. 查找、排序与二分

    F. 哈希计数与频率统计 (利用数组或 Map 记录状态)

    • 1. 两数之和【模式：在线哈希查找；核心：在一次遍历中同时进行“查找”与“存入”，实现 $O(n)$ 时间复杂度】
    • 128. 最长连续序列【模式：哈希集合 + 智能起点；核心：利用 unordered_set 实现 $O(1)$ 查找，仅从序列起点 (x-1 不存在) 开始计数，确保 $O(n)$ 复杂度】
    • 217. 存在重复元素【模式：哈希集合；核心：利用 unordered_set 实现 $O(n)$ 频率检测，最基础的去重思想】
    • 219. 存在重复元素 II【模式：固定窗口哈希；核心：维护大小为 k 的 unordered_set】
    • 220. 存在重复元素 III【模式：滑动窗口 + 有序集合；核心：利用 std::set::lower_bound 寻找满足范围条件的元素】
    • 202. 快乐数【模式：循环检测；核心：利用 unordered_set 记录历史值或使用“快慢指针”在 $O(1)$ 空间内检测无限循环】
    • 383. 赎金信【模式：字符计数；利用 int[26] 数组实现 $O(n)$ 时间 $O(1)$ 空间的高性能频率校验】
    • 242. 有效的字母异位词【模式：频率对比；核心：利用 int[26] 计数，通过“先加后减”配合“负数早期退出”实现 $O(n)$ 校验】
    • 49. 字母异位词分组【模式：等类规约；核心：利用“排序后的字符串”或“字符频次”作为 Map 的 Key 进行归一化分类】
    • 387. 字符串中的第一个唯一字符【模式：两次遍历；先统计频次，再找第一个频次为 1 的索引】
    • 205. 同构字符串【模式：索引映射；通过 mapS[s[i]] == mapT[t[i]] 校验字符映射的一致性】
    • 290. 单词规律【模式：双向哈希；核心：利用双 Map 或 Map+Set 建立 char 与 string 的双射关系，注意利用 stringstream 处理单词拆分】
    • 266. 判断一个字符串是否是回文排列【模式：奇偶计数；回文排列最多只能有一个字符出现奇数次】
    • 409. 最长回文串【模式：贪心构造；统计成对出现的字符，最后可选加一个奇数项作为中心】

  2. 栈与单调栈 (核心模式归类)

    A. 基础栈应用与模拟 (处理嵌套、撤销与状态存取)

    • 20. 有效的括号【模式：括号匹配；核心：利用栈的 LIFO 特性处理嵌套关系】
    • 150. 逆波兰表达式求值【模式：后缀表达式计算；核心：遇到运算符弹出两数计算，注意减/除顺序】
    • 224. 基本计算器【模式：符号栈模拟；核心：利用栈维护当前括号层级的“全局正负号”，实现 $O(n)$ 一次遍历展开括号】
    • 155. 最小栈【模式：双栈/辅助栈；核心：同步维护一个“当前的最小值”栈】
    • 232. 用栈实现队列【模式：双栈翻转；核心：利用入栈和出栈两个容器实现 FIFO】
    • 394. 字符串解码【模式：多栈状态存取；核心：分别用栈存储当前的倍数 cnt 和已拼出的 string】
    • 71. 简化路径【模式：路径模拟；核心：遇到 .. 执行出栈，配合 stringstream 拆分单词】

    B. 单调栈基础 (在线性时间内寻找左右最近的极值)

    C. 单调栈进阶 (处理区间面积与贡献度计算)

    • 84. 柱状图中最大的矩形【模式：左右扩展边界；核心：利用单调栈一次性确定每个柱子的左、右边界，求最大矩形面积】
    • 907. 子数组的最小值之和【模式：贡献度法；核心：计算每个元素作为最小值的区间覆盖范围 $(i-L)*(R-i)$】
    • 2866. 美丽塔 II【模式：前后缀单调栈；核心：分别计算左侧和右侧的单调递增和，最后枚举顶点取 Max】
    • 768. 最多能完成排序的块 II【模式：单调栈维护块极值；核心：栈中每个元素代表一个“块”的最大值，重叠则合并】

    D. 栈与贪心/其他

  3. 队列、双端队列与堆 (用于滑动窗口极值或动态 TopK)

  4. 链表 (核心模式归类)

    A. 基础操作与反转 (双指针、递归与 Dummy Node)

    B. 快慢指针与环形检测

    • 141. 环形链表【模式：快慢指针；核心：利用步长差 $(2-1=1)$，在 $O(n)$ 时间 $O(1)$ 空间内检测链表是否有环】
    • 142. 环形链表 II【模式：双指针追赶；核心：相遇后将一指针归零，同步慢走寻找环入口】
    • 19. 删除链表的倒数第 N 个结点【模式：快慢指针；核心：利用 $n$ 步位移差定位倒数第 $n+1$ 个节点（前驱节点）】
    • 61. 旋转链表【模式：成环解环；核心：先连成环再在 $n-(k%n)$ 处断开，简化指针操作】
    • 876. 链表的中间结点【模式：快慢指针；核心：fast 走两步 slow 走一步，fast 到头时 slow 在中点】
    • 287. 寻找重复数【模式：映射找环；将数组索引视为链表指针，转化为环入口问题】

    C. 合并、排序与分隔

    D. 复杂链表与采样

    • 138. 随机链表的复制【模式：原地克隆；核心：A->A'->B->B' 插入法，实现 $O(1)$ 空间拷贝随机指针】
    • 382. 链表随机节点【模式：水塘抽样；核心：从未知长度流中等概率采样，确保概率为 $1/i$】
    • 146. LRU 缓存【模式：哈希表 + 双向链表；实现 $O(1)$ 的访问与淘汰】
    • 460. LFU 缓存【模式：双哈希表 + 频次链表；实现 $O(1)$ 的频率敏感淘汰】

  5. 二叉树与树形结构 (核心模式归类)

    A. 遍历、属性与结构基础 (递归与迭代)

    B. 路径、祖先与贡献度计算 (DFS 进阶)

    C. 构造、变换与序列化

    D. 二叉搜索树 (BST 专项)

  6. 树与图论 (Tree & Graph - 核心模式归类)

    A. 树的基础与进阶 (Tree)

    B. 网格搜索与连通性 (DFS/BFS)

    • 200. 岛屿数量【模式：DFS/BFS；核心：原地修改标记（沉岛）实现 $O(1)$ 空间】
    • 305. 岛屿数量 II【模式：并查集 (Union-Find)；核心：动态维护连通分量，将“陆地化”转化为“集合合并”】
    • 130. 被围绕的区域【模式：逆向思维；从边界 'O' 开始标记，未被标记的内部 'O' 均需填充】
    • 133. 克隆图【模式：哈希表 + DFS/BFS；核心：利用 Map 存储 [原节点 -> 新节点] 防止死循环】
    • 399. 除法求值【模式：带权图搜索；将变量视为节点，比值视为边权，通过 DFS 或并查集求解】

    C. 拓扑排序 (有向无环图 DAG)

    D. 广度优先搜索进阶 (最短路径/步数)

    • 909. 蛇梯棋【模式：BFS；核心：一维坐标与二维矩阵的映射转换】
    • 433. 最小基因变化【模式：单向/双向 BFS；寻找状态空间的最短路径】
    • 127. 单词接龙【模式：双向 BFS；核心：利用中间态（如 h*t）优化状态转移搜索】

    E. 最短路径算法 (Dijkstra/Floyd/Bellman)

    F. 高级图论与连通性 (并查集/基环树/网络流)

  7. 平衡二叉搜索树 (std::map/set)

  8. 前缀和、后缀和与区间求和

  9. 差分 (连续区间同时加上或者减去一个数，数组还原)

  10. 树状数组 (Binary Indexed Tree)

  11. 线段树 (Segment Tree - 区间修改与聚合查询)

  12. 字典树 (Trie)

  13. 字符串匹配 (KMP / AC 自动机)

  14. 并查集 (Union Find)

  15. 数据结构设计与实现 (Consolidated)

    A. 基础结构实现

    B. 缓存与高级哈希

    C. 树与图的高级结构

  16. 离线query

基本算法

  1. 滑动窗口/双指针 【left,right】

  2. 排序算法/top k/select kth

  3. 枚举

  4. 模拟/分组/循环 (group/cycle arrray/模拟/易错)

  5. 贪心算法 (Greedy Algorithm - 核心模式归类)

    A. 基础贪心与排序 (利用排序消除维度影响)

    B. 反悔贪心 (结合优先队列动态调整)

    • 630. 课程表 III【模式：反悔贪心；核心：先按截止时间排序，若当前无法加入则替换掉之前耗时最长的课程】
    • 502. IPO【模式：双堆/排序+大顶堆；核心：动态选择当前资金下利润最大的项目】
    • LCP 30. 魔塔游戏【模式：反悔贪心；核心：血量不足时将之前扣血最多的房间移到最后】
    • 871. 最低加油次数【模式：反悔贪心；核心：油不够时从经过的加油站中选油最多的加】

    C. 贡献度法与数学贪心

    D. 区间处理 (排序 + 边界维护)

    E. 邻居约束与多遍遍历

    F. 贪心 + 二分/DP 结合

  6. 分治 (Divide and Conquer)

    核心逻辑：

    1. **分解 (Divide)**：将原问题拆分为规模较小、相互独立的子问题（如左右子树、数组半区）。
    2. **解决 (Conquer)**：递归解决子问题，直到触及边界。
    3. **合并 (Combine)**：将子问题的解合并为原问题的解（如归并排序的 merge 或 LCA 的状态上传）。

数学 (Mathematics - 核心模式归类)

  1. 数论基础 (Number Theory)

    A. 质数、约数与筛选法

    B. 最大公约数 (GCD) 与 最小公倍数 (LCM)

    C. 数字处理与投票算法

    • 169. 多数元素【模式：Boyer-Moore 摩尔投票法；$O(n)$ 时间 $O(1)$ 空间找众数】
    • 229. 多数元素 II【模式：进阶摩尔投票；统计出现次数超过 $n/3$ 的元素】
    • 400. 第 N 位数字【模式：数学模拟；按位数区间（个位、十位…）定位数字】
    • 343. 整数拆分【模式：数学推导；核心：尽可能拆分成 3 以获得最大乘积】

  2. 组合数学与概率 (Combinatorics & Probability)

    A. 排列组合与大数取模

    B. 模运算与乘法逆元

    C. 随机采样 (Sampling)

  3. 位运算 (Bit Manipulation)

    A. 基础技巧与 Lowbit

    • 核心性质：n & (n-1) 消除最低位 1；n & -n 获取最低位 1 (lowbit)】
    • 191. 位 1 的个数【模式：__builtin_popcount 或 n & (n-1) 迭代】
    • 231. 2 的幂【模式：n > 0 && (n & (n-1)) == 0】

    B. 异或 (XOR) 专项

  4. 快速幂与几何 (Fast Power & Geometry)

搜索问题核心分类与总结 (Search Strategies)

  1. 二分搜索：从“查找”到“答案空间”的跨越 (Binary Search)

  2. BFS：状态空间的最短路径 (Breadth-First Search)

  3. DFS 与回溯：全量枚举与约束满足 (DFS & Backtracking)

    💡 回溯四阶梯与去重口诀

    阶梯 核心场景 去重/控制逻辑 关键代码
    1. 基础回溯 简单组合 (17题) 递归深度控制索引 dfs(i + 1)
    2. 组合去重 选 k 个数 (77题) start 索引控制单向搜索 for (int i = start; ...)
    3. 状态压缩 全排列 (46题) Bitmask 替代 visited 数组 if (!(mask & (1 << j)))
    4. 排列去重 有重全排列 (47题) 排序 + 相邻状态校验 if (j > 0 && nums[j] == nums[j-1] && !used[j-1])
    5. 复杂约束 棋盘/皇后 (52题) 空间换时间 (哈希标记) if (!cols[c] && !diag[r+c])
    6. 余额控制 括号生成 (22题) 动态维护待匹配余额 if (remain > 0) dfs(..., remain-1)
    7. 矩阵回溯 单词搜索 (79题) 原地标记 + 字符还原 board[r][c] = '#'; dfs(); board[r][c] = tmp;

    去重口诀：

    • 组合靠 start：不回头看，一路向右。
    • 排列靠 used：全员参与，位掩码标记。
    • 重复靠排序：前人未用，后人莫入（!used[i-1]）。
    • 棋盘靠标记：列号、和、差，三位一体定乾坤。
    • 括号看余额：左括号不超标，右括号不透支。
    • 矩阵靠沉岛：先占位再递归，事后记得还原。

    组合、排列与路径

  4. 逆向思维与启发式搜索 (Advanced Search)

DP问题（递推类DP）

DP 类问题处理五部曲总结

步骤 核心任务 (Key Action) 你的代码体现 (Example) 空间优化思路 (Space Optimization)
1. 状态定义 明确 dp 数组各维度的物理含义 dp[i][j] 表示到达坐标 (i,j) 的最小路径和 维度压缩：若当前状态只依赖前一状态，可将二维数组降为一维（或常数个变量）。
2. 转移方程 建立当前状态与前置状态的数学关系 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 原地修改：如果输入数组（如 grid）后续不再使用，可以直接在原数组上操作实现 $O(1)$ 额外空间。
3. 初始边界 确定无需推导的“种子”值和边界逻辑 初始化 dp[0][0]，并单独处理首行 dp[0][i] 和首列 dp[i][0] 虚拟边界：有时可以多申请一行/一列（如 dp[m+1][n+1]）并填入占位值，从而统一循环内的逻辑。
4. 计算顺序 确定循环的方向（Top-down vs Bottom-up） 使用双重 for 循环，从左到右、从上到下遍历 倒序遍历：在 0/1 背包等问题中，通过倒序遍历一维 DP 数组，可以防止当前层的计算污染待使用的旧数据。
5. 最终结果 确定答案在 dp 表中的存储位置 返回 dp[m-1][n-1] 状态追踪：如果不仅要结果还要路径，通常需要额外的 parent 数组记录来源，空间优化此时会受限。

  1. 线性 DP 和 状态机 DB （包括状态机DP，序列DP,子问题有一个端点是固定不变的）

    1. 线性DP（一维 O(n),dp[i] 只与之前的某个几个状态有关系)

    2. 线性DP（一维O(n^2),dp[i],和之前的每个状态有关系）

    3. 线性DP (dp[i][k],dp[i]有k个状态，一维+k个状态,状态机DP（关键是设计状态以及状态转移方程，之后在处理边界条件）)

    4. 网格，矩阵DP（二维 dp[i][j])

    5. 网格，矩阵DP（二维 dp[i][j][k],二维+k个状态)

    6. 序列DP (序列DP是动态规划中的一种常见形式，通常用于解决一些关于序列的问题，比如最长递增子序列、编辑距离等)

    7. 数组DP dp[i][j]

  2. 背包 DP

  3. 区间 DP （子问题向内缩小，两端都会向内移动）

  4. bitmask，状压 和 状态压缩DP,bitmask vs map+vector （把集合用二进制表示,二进制mask 1<<n）

  5. 树形 DP （子树天然地形成子问题，需要考虑dp的信息是怎么从子树传给上面的子树的，记忆化搜索，递归。就是我们已经知道以uuu为根的答案，想要通过u−>v的父子关系把答案传递）

    1. 树上最大独立集 (不选相连的节点)
    1. 定根DP，一次扫描
    2. 换根DP，二次扫描法

  6. 数位 DP (dfs(int i,int state,bool is_limit,bool is_num)

  7. 数据结构优化DP

  8. 倍增和倍增优化DP

  9. 矩阵快速幂优化DP

  10. 记忆化搜索 （动态规划，状态优化，求方案数量，离散化）

  11. 博弈DP

    • 3283. 吃掉所有兵需要的最多移动次数
      1. 除数博弈 1435 有数学做法
      1. 石子游戏 1590 有数学做法
      1. 预测赢家
      1. 石子游戏 IV 1787
      1. 石子游戏 VII 1951
      1. 石子游戏 III 2027
      1. 石子游戏 II 2035
      1. 石子游戏 V 2087
      1. 我能赢吗
      1. 石子游戏 VIII 2440
      1. 猫和老鼠 2567

树与图论 (Tree & Graph - 核心模式归类)

A. 树的基础与进阶 (Tree)

  - [3373. 连接两棵树后最大目标节点数目 II](https://leetcode.cn/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii)
  - [3786. 树组的交互代价总和](https://leetcode.cn/problems/total-sum-of-interaction-cost-in-tree-groups)【边贡献法，auto lamda dfs写法，避免使用function】

B. 网格搜索与连通性 (DFS/BFS)

  • 200. 岛屿数量【模式：DFS/BFS；核心：原地修改标记（沉岛）实现 $O(1)$ 空间】
  • 130. 被围绕的区域【模式：逆向思维；从边界 'O' 开始标记，未被标记的内部 'O' 均需填充】
  • 133. 克隆图【模式：哈希表 + DFS/BFS；核心：利用 Map 存储 [原节点 -> 新节点] 防止死循环】
  • 399. 除法求值【模式：带权图搜索；将变量视为节点，比值视为边权，通过 DFS 或并查集求解】

C. 拓扑排序 (有向无环图 DAG)

D. 广度优先搜索进阶 (最短路径/步数)

  • 909. 蛇梯棋【模式：BFS；核心：一维坐标与二维矩阵的映射转换】
  • 433. 最小基因变化【模式：单向/双向 BFS；寻找状态空间的最短路径】
  • 127. 单词接龙【模式：双向 BFS；核心：利用中间态（如 h*t）优化状态转移搜索】

E. 最短路径算法 (Dijkstra/Floyd/Bellman)

F. 高级图论与连通性 (并查集/基环树/网络流)

参考

1
2
3
4
5
6
函数名	检查内容	对应你的描述
isdigit(c)	检查是否为 数字 (0-9)	数字字符
isalpha(c)	检查是否为 字母 (a-z, A-Z)	纯字符/字母
isalnum(c)	检查是否为 字母或数字	字母数字混合
tolower(c)
toupper(c)

工程小技巧 (Engineering Tips)

1. 数组快速清零

在 C++ 中，局部变量（栈上分配）默认包含随机垃圾值。使用以下语法可实现极致高效的清零：

1
2
int arr[9][9] = {0}; // 显式初始化第一个元素为 0，其余元素自动补零
int arr[9][9] = {};  // C++11 简写，全员清零
  • 注意：如果不加 {0}，数组内容将不可预测，这是初学者最常见的 Bug 来源。
  • 性能：编译器通常会将其优化为内联的 memset 或专门的 CPU 指令，比手动 for 循环快得多。

2. 字符串单词拆分 (stringstream)

在处理以空格分隔的字符串（如“hello world”）时，手动控制指针解析既繁琐又容易出错（需考虑首尾空格、多空格等情况）。

1
2
3
4
5
6
7
#include <sstream>
string s = "  hello   world  ";
stringstream ss(s);
string word;
while (ss >> word) {
    // 自动跳过所有空格，依次提取出 "hello" 和 "world"
}
  • 优势：逻辑极简，代码鲁棒性极强，是面试中处理字符串解析的首选方案。

3. 搜索策略选择指南

在算法竞赛或面试中，面对复杂的搜索问题，快速判断技术路线是节省时间的关键：

  • 求最短路径 / 最小步数：首选 BFS（利用其层级遍历的天然最短性）。
  • 求所有方案 / 排列组合：首选 DFS + 回溯（全量枚举状态空间）。
  • 在单调 / 有序空间找最优值：首选 二分答案（将最优化问题转化为判定问题 check(mid)）。
  • 状态空间爆炸：优先考虑 双向 BFS（极大减小搜索树规模）或 记忆化搜索（DFS + Memo，避免重复计算）。