备考考研专业课中，我在力扣上从零基础起学习DSA。
使用力扣备考DSA的优势包括：
- 动手实现算法代替照背程序，加深算法理解。
- 提高代码能力，更好掌握语言，以应对初试手写代码大题和复试机考。
- 只需补全核心代码，无需关注头文件导入、输入输出、内存回收等程序完整性要求，对于链表、二叉树类问题尤其友好。
- 无需人工判题，测试用例覆盖范围广，有效检验算法正确性。
- 学习资源丰富，官方题库和学习计划对DSA基础问题包含全面，社区也有高质量题解和题单。
- ……
但自己在用力扣备考中也走过一些弯路。最重要的问题莫过于，力扣只能覆盖专业课的DSA范围的一部分：
- 专业课会考察数据结构的底层实现，而力扣更注重数据结构的问题应用。
- 专业课的一些知识点未能被力扣覆盖。
- 专业课出题形式以低代码的填选题居多，大题除代码题外还包括证明题，与力扣有较大出入。
- 力扣更多的算法问题与数据结构考纲不相关，大量刷题过于费时。
- ……
无论如何，在力扣上适当刷题还是有一定意义的。以下是笔者根据王道数据结构指导书的代码大题，整理而成的考研DSA基础题单，难度大都在简单至中等水平。
题单已经整理至考研数据结构题单。欢迎提出意见与补充。
1 线性表
1.1 顺序表
主要涉及模拟、双指针、原地哈希等算法。字符串、数组与矩阵部分同理。
典型题：
- 189. 轮转数组（2010真题）
- 88. 合并两个有序数组
- 4. 寻找两个正序数组的中位数（2011真题）
- 283. 移动零
- 1089. 复写零
- 26. 删除有序数组中的重复项
- 75. 颜色分类
- 268. 丢失的数字
- 41. 缺失的第一个正数（2018真题）
- 169. 多数元素（2013真题）
- 632. 最小区间
1.2 链表
链表的查找、插入、删除、重排等操作。
模板题：
- 206. 反转链表
- 141. 环形链表
- 142. 环形链表 II
- 160. 相交链表（2012真题）
典型题：
- 21. 合并两个有序链表
- 2. 两数相加
- 445. 两数相加 II
- 1634. 求两个多项式链表的和（会员题）
- 203. 移除链表元素
- 83. 删除排序链表中的重复元素（2015真题）
- 82. 删除排序链表中的重复元素 II
练习题：
- 19. 删除链表的倒数第 N 个结点（2009真题）
- 24. 两两交换链表中的节点
- 143. 重排链表（2019真题）
- 234. 回文链表
- 328. 奇偶链表
- 148. 排序链表
- 707. 设计链表
1.3 数组与矩阵
坐标的对应关系。
典型题：
练习题：
1.4 字符串
KMP算法。
模板题：
典型题：
2 栈与队列
2.1 栈
栈的应用，如进制转换、括号匹配、文本编辑、表达式计算等。
典型题：
- 504. 七进制数
- 20. 有效的括号
- 946. 验证栈序列
- 844. 比较含退格的字符串
- 155. 最小栈
- 150. 逆波兰表达式求值
- 224. 基本计算器
- 227. 基本计算器 II
- 772. 基本计算器 III（会员题）
2.2 队列
队列的设计。
模板题：
典型题：
3 树与二叉树
3.1 遍历
树的存储结构，前序、中序、后序、层序遍历，线索二叉树（Morris遍历）。
模板题：
典型题：
递归问题。
典型题：
- 111. 二叉树的最小深度
- 104. 二叉树的最大深度
- 105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 889. 根据前序和后序遍历构造二叉树
- 431. 将 N 叉树编码为二叉树（会员题）
练习题：
3.2 树的应用
哈夫曼（Huffman）树。
模板题：
- 1167. 连接木棍的最低费用（会员题）
并查集。
模板题：
- 323. 无向图中连通分量的数目（会员题）
典型题：
4 图
4.1 基础
图的概念，存储结构。
练习题：
4.2 遍历
DFS、BFS。
练习题：
4.3 图的应用
最小生成树（MST），Prim、Kruskal算法。
模板题：
最短路径，Dijkstra、Floyd算法。
模板题：
拓扑排序。
模板题：
- 207. 课程表（2024真题）
- 210. 课程表 II
5 查找
5.1 二分查找
有序顺序表上的二分查找。
5.2 二叉搜索树（BST）
BST的概念，查找、插入、删除等操作，构造。
- 98. 验证二叉搜索树（2022真题）
- 700. 二叉搜索树中的搜索
- 230. 二叉搜索树中第K小的元素
- 701. 二叉搜索树中的插入操作
- 450. 删除二叉搜索树中的节点
- 235. 二叉搜索树的最近公共祖先
- 285. 二叉搜索树中的中序后继（会员题）
- 108. 将有序数组转换为二叉搜索树
- 1008. 前序遍历构造二叉搜索树
5.3 平衡二叉树（AVL）
AVL的概念，插入、删除等调整操作。
5.4 哈希表
哈希表的设计。
6 排序
十大排序，快速排序划分操作，堆的概念。
- 912. 排序数组
- 215. 数组中的第K个最大元素（2016真题）
参考
评论 (14)
