题模
模式识别
- Hash: 适用于涉及出现次数的问题。常用方法包括哈希表或哈希集合来存储出现次数。
- 子串构造: 利用哈希存储子串的位置或信息,用于高效查找。
- 滑动窗口: 适用于子串问题,优化空间复杂度。
- 递归 + 回溯: 解决需要探索所有可能的情况的问题,如全排列、组合问题。
- 队列 + 追加: 广度优先搜索 (BFS) 的基础,适用于路径查找、层次遍历等问题。
- 图: 包含点和边,树是一种特殊的图(无环、连通)。
双指针
- 相向双指针: 用于解决数组中对称问题或寻找两个指针相遇的问题。
- 同向双指针(窗口): 用于处理滑动窗口问题,如最大子数组和、最短子串问题。
- 两个数组: 处理两个有序数组的合并或交集问题。
参考: 双指针算法模板和一些题目 - bonelee - 博客园
滑动窗口
- 固定窗口: 窗口大小固定的情况下,移动窗口来计算子数组或子串的属性。例如,计算固定大小的滑动窗口内的最大和或最小值。
- 可变窗口: 窗口大小可以变化,以满足某些条件。例如,寻找满足某条件的最短子串或最长子串。