数据结构

链表/树

典型链表/树问题

• 大数相加
• 反转链表
• 前序，中序，后序: 递归和迭代的遍历方式
• 平衡二叉树
• 二叉搜索树

树/链表参考文章

• 花花酱-树/链表

字符串

典型字符串问题

• KMP
• Edit Distance

堆栈

典型堆栈问题

• 前缀表达式
• 利用栈的迭代解法

队列

典型队列问题

• BFS
• 优先队列（heap）

图

典型图问题

• DFS/BFS
• 最短路径
• 最小生成树(Kruskal, Prim两种算法)

图参考文章

• 花花酱-图

算法

查找

二分查找、哈希查找、常用set/map

排序

O(n^2)与O(nlogn)的排序算法，特点、冒泡/选择/插入，归并/快排/堆排序

回溯法

• 排列、组合

BFS/DFS

动态规划/贪心算法

从递归到动态规划

• 暴力解，复杂度: 指数级别时间复杂度
• 定义状态函数， 写状态转移方程(最优子结构)--递归实现: 指数级别时间复杂度
• 记忆化搜索: 递归实现 + 记忆化搜索 (自顶而下的方法): 多项式级别时间复杂度
• 自底而上求解--动态规划: 多项式级别时间复杂度
• 优化空间复杂度(例如对索引%2，只保留两行数据)

典型动态规划问题

• 斐波那序列
• 爬台阶
• 0-1背包问题/(无限使用背包问题，多维约束，物品依赖与排斥)
• 最长上升子序列： 动态规划时间复杂度$O(n^2)$
• 最长公共子序列
• 单源最短路径算法

动态规划参考文章

• 花花酱-贪心/动态规划

参考链接

• 花花酱B站视频
• 拉钩+leetcode培训视频
• geeksforgeeks 数据结构
• Leetcode All in One
• 编程之法：面试和算法心得