备考考研专业课中,我在力扣上从零基础起学习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真题)
参考
评论 (15)


