数据结构与算法
链表
优先队列
栈
哈希
LeetCode203. 移除链表元素
LeetCode237. 删除链表中的节点
LeetCode 206、反转链
表
结合双指针
LeetCode 215、数组中的第 K 个最大元素
普通栈
单调栈
哈希集合
unordered_set
哈希表
unordered_map
动态规划
1.入门问题
2.路径问题
3.序列DP
4.背包DP
LeetCode 876、链表的中间结点
LC509. 斐波那契数
LC70. 爬楼梯
LC198. 打家劫舍
LC62. 不同路径
LC63. 不同路径 II
LC64. 最小路径和
LC213. 打家劫舍II
LC5. 最大子数组和
LC931. 下降路径最小和
5.状态DP
最长递增子序列(LIS)问题
最长公共子序列(LCS)问题
LC300. 最长递增子序列
LC673. 最长递增子序列的个数
LC334. 递增的三元组
LC718. 最长重复子数组
LC1143. 最长公共子序列
LC5. 最长回文子串
0-1背包
完全背包
LC494.目标和
LC322. 零钱兑换
LC518.零钱兑换II
DFS/BFS
买卖股票的最佳时机系列问题
二维矩阵表示图(岛屿问题)
LC200. 岛屿数量
LC695. 岛屿的最大面积
邻接矩阵表示图 LC547. 省份数量
邻接表表示图 LC841. 钥匙和房间
计算连通块数目
计算连通块大小
计算连通块数目
多源矩阵BFS LC994. 腐烂的橘子
拓扑排序
用DP解题,一般要思考三个重要问题。
DP数组的定义是什么?
动态转移方程是什么?
如何对DP数组进行初始化?
设置一个三维数组 dp
// dp[i][k][b]
// i 表示天数,dp[i] 表示第 i 天的最
大利润
// k 表示最多交易次数,每次交易包含买
入和卖出,这里只在买入的时候将 k - 1
// 注意:【 k 表示最多交易次数,而不是
实际交易次数,比如最多交易两次可能实际只交易一
次】
// b 表示当前是否持有股票,取值为 0 和
1
// 其中 0 表示当前持有 0 份股票,即
【不持有】股票
// 而 1 表示当前持有 1 份股票,即【持
有】股票
LC207. 课程表
LC210. 课程表Ⅱ
回溯法
LeetCode 78、子集
LeetCode 90、子集II
LeetCode 46、全排列
LeetCode 47、全排列Ⅱ
注意比较DFS和BFS的异同。
相同之处:
这两种算法都属于在树形结构或者图的搜索算法,
能够访问所有的节点/位置
不同之处:
DFS像侦察兵一样一直优先往深处搜索;BFS像军队
一样铺展开来搜索
DFS通常需要借助用递归实现,本质上是用到了编译栈;
BFS通常需要借助队列来辅助实现
BFS有层的概念(level),有时候也称为波纹法,通常
可以用来搜寻最短路径
对于二叉树而言,DFS有先序、中序、后序三种遍历
方式,但对于图而言通常没有这种分类;BFS在二叉树中
也称为层序遍历。
图可以有多用多种方式来表示,譬如二维矩阵、邻
接矩阵、邻接表等等
LeetCode 39、组合总和
LeetCode 40、组合总和II
LeetCode79、 单词搜索
LeetCode967、连续差相同的数字
LeetCode 19、删除链表的倒数第 N 个结点
LeetCode 160、相交链表
二叉树
DFS
BFS
LeetCode94/144/145 二叉树的中序/前序/后序遍历
LeetCode 104、二叉树的最大深度
LeetCode 111 、二叉树的最小深度
LeetCode 226、翻转二叉树
LeetCode 105、从前序与中序遍历序列构造二叉树
LeetCode 236、二叉树的最近公共祖先
LeetCode 297 、二叉树的序列化与反序列化
LeetCode 102、二叉树的层序遍历
LeetCode 103、二叉树的锯齿形层序遍历
二叉搜索树
树形动态规划DP
LeetCode 98、验证二叉搜索树
LeetCode 235、二叉搜索树的最近公共祖先
LeetCode 337、打家劫舍III
双指针
LC20. 有效的括号
LC1047. 删除字符串中的所有相邻重复项
LC150. 逆波兰表达式求值
LC394. 字符串解码
LC71. 简化路径
LeetCode735 小行星碰撞
LC496. 下一个更大元素 I
LC739. 每日温度
LC42. 接雨水
LC349. 两个数组的交集
LC242. 有效的字母异位词
LC1. 两数之和
LC219. 存在重复元素II
同向双指针 LC26. 删除有序数组中的重复项
LC27. 移除元素
相向双指针
LC88. 合并两个有序数组
LC167. 两数之和II- 输入有序数组
LC11. 盛水最多的容器
LC15. 三数之和
力扣16. 最接近的三数之和
LC75. 颜色分类
LeetCode 215、数组中的第 K 个最大元素
滑动窗口
不定长滑窗
固定滑窗
LC3. 无重复字符的最长子串
LC209. 长度最小的子数组
LeetCode 1052、爱生气的书店老板
二分查找
在排序数组中进行二分查找
在数轴上进行二分查找
利用问题的二段性进行二分
LeetCode 69、x 的平方根
LeetCode 34、在排序数组中查找元素的
第一个和最后一个位置
LeetCode 35、搜索插入位置
LeetCode875.爱吃香蕉的珂珂
贪心算法
所谓贪心思想,其严谨定义是每一次计
算都考虑局部的最优解,从而最终能够
到达全局最优解。
LC455. 分发饼干
LC134. 加油站
LC860. 柠檬水找零
LeetCode 179、最大数
由于排序数组、数轴具有单调性的性质,所
以是二分查找的一个非常重点的应用场景。
二段性问题的二分法:
即所需要的答案ans能够把数轴分成两个部
分。
注意循环中的判断语句不好写,或是需要自
己实现用来判断的函数
滑窗三问:
Q0:第一个窗口如何初始化?
Q1:对于每一个右指针 right 所指的元素 ch ,做
什么操作?
Q2:left在移动前,即 left = right – k 对应的
元素 left_ch 要做什么操作?
Q3:如何进行 ans 的更新?