|
数组 |
|
|
| 1 |
88.合并两个升序数组 |
归并排序/双指针 |
|
| 2 |
从无序数组中删除所有值为x的元素，要求时间复杂度为O（n），空间复杂度为O（1） |
双指针 |
|
| 3 |
11. 盛最多水的容器 |
双指针 |
|
| 4 |
26. 删除有序数组中的重复项 |
双指针 |
|
| 5 |
4. 寻找两个正序数组的中位数 |
二分 |
【2011真题】 |
| 6 |
34. 在排序数组中查找元素的第一个和最后一个位置 |
二分 |
学习二分模板同时，掌握C++STL函数lower_bound和upper_bound用法 |
| 7 |
35. 搜索插入位置 |
二分 |
|
| 8 |
41. 缺失的第一个正数 |
哈希表 |
【2018真题】也可原地哈希 |
| 9 |
167.两数之和 II - 输入有序数组 |
双指针 |
|
| 10 |
209. 长度最小的子数组 |
双指针 |
|
| 11 |
15.三数之和 |
双指针 |
|
| 12 |
977. 有序数组的平方 |
双指针 |
|
| 13 |
1004. 最大连续 1 的个数 III |
双指针（滑动窗口）/前缀和+二分 |
滑动窗口是同向双指针的一种 |
| 14 |
169. 多数元素 |
①哈希表 ②排序 ③随机化 ④分治 ⑤摩尔投票算法 |
【2013年真题】 |
| 15 |
3. 无重复字符的最长子串 |
哈希表+双指针 |
|
| 16 |
1658. 将 x 减到 0 的最小操作数 |
滑动窗口/前缀和+双指针 |
|
| 17 |
189. 轮转数组 |
模拟 |
|
| 18 |
75. 颜色分类 |
双指针 |
|
|
链表 |
|
|
| 1 |
147. 对链表进行插入排序 |
模拟+排序 |
|
| 2 |
1171.从链表中删去总和值为零的连续节点 |
|
|
| 3 |
148.排序链表 |
|
|
| 4 |
19.删除链表的倒数第k个结点 |
双指针 |
|
| 5 |
86.分隔链表 |
双指针 |
|
| 6 |
21. 合并两个有序链表 |
双指针 |
思考如何将两个升序合并成一个降序链表？ |
| 7 |
82. 删除排序链表中的重复元素 II |
双指针 |
|
| 8 |
146. LRU 缓存 |
双向链表+哈希表 |
|
| 9 |
141. 环形链表 |
双指针 |
|
| 10 |
142. 环形链表 II |
双指针 |
要求O（1） |
| 11 |
83. 删除排序链表中的重复元素 |
|
|
| 12 |
143. 重排链表 |
|
真题 |
|
树 |
|
|
| 1 |
144. 二叉树的前序遍历 |
递归/迭代 |
|
| 2 |
94. 二叉树的中序遍历 |
递归/迭代 |
|
| 3 |
145. 二叉树的后序遍历 |
递归/迭代 |
|
| 4 |
102.二叉树的层序遍历 |
层序遍历 |
|
| 5 |
104. 二叉树的最大深度 |
递归 |
|
| 6 |
100.相同的树 |
递归 |
|
| 7 |
98.验证二叉搜索树 |
BST |
|
| 8 |
230. 二叉搜索树中第K小的元素 |
BST |
|
| 9 |
236.二叉树的最近公共祖先 |
递归 |
|
| 10 |
107. 二叉树的层序遍历 II |
层序遍历 |
|
| 11 |
199. 二叉树的右视图 |
层序遍历 |
|
| 12 |
二叉树每层结点最多多少个 |
层序遍历 |
|
| 13 |
129.求根节点到叶节点数字之和 |
深度遍历 |
|
| 14 |
101. 对称二叉树 |
递归 |
|
| 15 |
110. 平衡二叉树 |
递归 |
之前考过验证二叉排序树，这题也可能考 |
| 16 |
112.路径总和 |
递归 |
|
| 17 |
226.翻转二叉树 |
递归 |
|
|
|
|
|
|
图 |
|
|
| 1 |
图的广度优先搜索（邻接矩阵实现） |
|
|
| 2 |
图的广度优先搜索（邻接表实现） |
|
|
| 3 |
图的深度优先搜索（邻接矩阵实现） |
|
|
| 4 |
图的深度优先搜索（邻接表实现） |
|
|
| 5 |
200. 岛屿数量 |
DFS/BFS/并查集 |
求连通分量 |
| 6 |
695. 岛屿的最大面积 |
DFS/BFS/并查集 |
|
| 7 |
207. 课程表 |
拓扑排序 |
|
| 8 |
判断无向图中是否存在环 |
|
|
| 9 |
判断有向图中是否存在环 |
|
|
| 10 |
设计一个算法，判断图G中从顶点i到 j是否存在简单路径 |
|
|
| 11 |
prim 算法算法思想：从某一个顶点开始构建生成树，每次将代价最小的新顶点（与当前T中顶点集合距离最近的顶点）纳入生成树，直到所有顶点都纳入为止； |
|
|
|
栈、队列 |
|
|
| 1 |
32. 最长有效括号 |
栈 |
|
| 2 |
225. 用队列实现栈 |
队列 |
|
| 3 |
232. 用栈实现队列 |
栈 |
|
| 4 |
150. 逆波兰表达式求值 |
栈 |
|
|
排序 |
|
|
| 1 |
215. 数组中的第K个最大元素 |
快速排序 |
要求时间复杂度O（n) |
| 2 |
347. 前 K 个高频元素 |
排序+哈希表 |
|
|
其他 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|