算法框架

一、数据结构

1. 字符串

2. 数组

最底层的数据结构，内存连续，读写 O(1)，一般出现在双指针、滑动窗口等题目中

常见技巧	描述	示例
二分查找	x，f(x)，target 三件套	704.二分查找 34.在排序数组中查找元素的第一个和最后一个位置
双指针	快慢指针，两端向中心指针，中心向两端指针	27.移除元素 977.有序数组的平方 26.删除有序数组中的重复项
滑动窗口	双指针变种，解决子数组问题，有明确的扩大或缩小窗口的条件	209.长度最小的子数组
模拟行为	循环不变量原则	59.螺旋矩阵II
前缀和	时间复杂度 O(1)，空间换时间，频繁查询某个区间的累积和	303.区域和检索 560.和为K的子数组
差分数组	前缀和的“逆运算”，频繁对原始数组的某个区间的元素进行增减	1109.航班预订统计
并查集	由子结点找到父亲结点，处理一些集合的合并与查询	130.被围绕的区域

3. 链表

最底层的数据结构，插入删除 O(1)，一般从链表的头部/尾部开始访问

常见技巧	描述	示例
链表操作	增删改查	707.设计链表 83.删除排序链表中的重复元素
递归	递归三要素	203.移除链表元素 206.反转链表 24.两两交换链表中的节点 19.删除链表的倒数第N个结点
双指针	快慢指针，两端向中心指针，中心向两端指针	203.移除链表元素 206.反转链表 24.两两交换链表中的节点 19.删除链表的倒数第N个结点
哈希表	空间换时间	160.相交链表 142.环形链表

4. 哈希表

KV，底层通过数组/链表实现，一般用来快速判断一个元素是否出现集合里 或 统计频次

常见技巧	描述	示例
哈希表	统计频次	242.有效的字母异位词 1002.查找共用字符 202.快乐数

5. 栈和队列

栈：先入后出，可用来进行深度优先搜索

队列：先入先出，可用来进行广度优先搜索

6. 二叉树

二叉树可以链式存储，也可以顺序存储。链式存储方式就用链表实现， 顺序存储的方式就是用数组实现。

7. 图论

二、算法思维

1. 双指针

分为快慢指针、左右指针

2. 前缀和

3. 差分数组

4. 二分查找

5. 排序算法

6. 滑动窗口

7. 单调栈

8. 并查集

9. BFS 和 DFS

BFS：深度优先遍历，可分为前序/中序/后序

DFS：广度优先遍历，可分为层次/层序

10. LRU 和 LFU

LRU：最近最少使用的缓存淘汰算法，哈希链表、双链表

LFU：最久未使用的缓存淘汰算法，哈希链表、双链表

11. 递归

容易联想到栈，深度优先遍历，自顶向下，通过 f(n)递归 f(n-1)

12. 回溯算法

N 叉树的深度优先遍历

13. 动态规划

一般用于求最值的场景

自底向上并不是 i 从 0 到 n，也可能从 n 到 0，如果问题是求 dp0n, 则底问题是 dn-1n-1

思路：

1）穷举法（递归） 2）记忆化搜索 3）递推

递推求解思路：

1）设计状态：自底向上（画出二叉树） 2）初始状态 3）状态转移方程（数学归纳法）