力扣博文链接
模拟13 罗马数字转整数989 数组形式的整数加法8 字符串转换整数 (atoi)59 螺旋矩阵 II67 二进制求和319 灯泡开关134 加油站暴力11 盛最多水的容器22 括号生成221 最大正方形栈与队列921 使括号有效的最少添加150 逆波兰表达式求值...
目录
看到题目我们首先要想怎么样才能够把正确答案求出来，然后再想使用什么样的数据结构进行优化
树
1584 连接所有点的最小费用（python3 kruskal 算法最小生成树）
堆
767/1054 题(两道题的本质都是一样的)使用python中的heapq模块创建小根堆（python中没有大根堆所以需要在元素前面添加负号表示大根堆），heapq模块在初始化列表，添加与弹出元素的时候都会维持堆的不变性非常方便，heapq模块经常使用的方法：
① 初始化一个堆（通常将一个列表初始化为一个小根堆）：heapq.heapify() ② 弹出堆顶元素：heapq.heappop() ③ 往堆中添加元素：heapq.heappush()，堆数据结构可以参照博文
一般题目中要求解前k个最小或者最大的元素（维护集合中元素的最大值或最小值的数据结构）那么就可以考虑使用堆来解决
1054 距离相等的条形码（python3 大根堆--贪心）
1046 最后一块石头的重量（python3 模拟、大根堆）
1834 单线程 CPU（python3 lambda表达式排序 + 优先队列）使用lambda表达式来定义排序规则维护编号顺序的不变性
502 IPO（python3 贪心、大根堆维护元素最大值）
658 找到 K 个最接近的元素（python3 大根堆维护前k大的元素、二分查找、双指针）
模拟
使用程序模拟题目描述的过程
1566 重复至少 K 次且长度为 M 的模式（python3 模拟）
1539 第 k 个缺失的正整数（python3 模拟、字典）
1566 重复至少 K 次且长度为 M 的模式（python3 模拟）
1073 负二进制数相加（python3 模拟两个数组相加的过程）
26 删除排序数组中的重复项（python3-java 模拟：判断相邻元素是否相同）
1652 拆炸弹（python3 模拟：计算连续k个数字的和）
1662 检查两个字符串数组是否相等（python3 模拟）
1009题是关于怎么样求解十进制数字对应的二进制数字长度的题目
1046 最后一块石头的重量（python3 模拟、大根堆）
1736 替换隐藏数字得到的最晚时间（python3 模拟）
LCP 03 机器人大冒险（python3 模拟、分析-计算运动周期）
833 字符串中的查找与替换（python3 模拟、使用zip-sorted函数实现多个列表对应位置的整体排序 逆序排序这样在修改列表的时候不会对之前的字符串匹配产生影响）
1812 判断国际象棋棋盘中一个格子的颜色（python3 判断）
1837 K 进制表示下的各位数字总和（python 3 模拟）
1839 所有元音按顺序排布的最长子字符串（python3 模拟）
331 验证二叉树的前序序列化（python3 模拟、dfs）
731 我的日程安排表 II（c++-java-python 线段树-动态开点、模拟）
枚举
1010 总持续时间可被 60 整除的歌曲（python3）
1615 最大网络秩（python3 统计节点的度数 + 枚举）
1620 网络信号最好的坐标（python3 枚举、字典存储坐标点）
1637 两点之间不包含任何点的最宽垂直面积（python3 枚举）
1014题在暴力的基础上进行了优化，使得时间复杂度降低了很多
28 实现 strStr()（python3 暴力 字符串的匹配）
164 最大间距（python3 枚举、桶排序思想计算相邻元素的最大间距）
121 买卖股票的最佳时机（python3 寻找数组中单调递增的序列中最小数字与最大数字--单调栈、枚举）
479 最大回文数乘积（python3 暴力枚举）有技巧的暴力枚举
1935 可以输入的最大单词数（python3 暴力枚举、哈希表）
枚举技巧：先考虑如何枚举才可以将所有答案枚举出来？也即考虑先怎么样做，再考虑怎么样优化。在很多情况下都是考虑以当前的i结尾（终点）前面的...523/525题是结合了怎么样枚举然后通过分析得出怎么样优化的问题。
523 连续的子数组和（python3 枚举、前缀和、哈希表优化）
532题与523/525题都是类似的都是先如何考虑枚举才能将所有答案枚举出来，一般都是以当前的i结尾的（最常见的枚举思想）...，也即枚举以当前的i为终点的...并且当我们发现答案与顺序无关的时候那么可以考虑先排序，这样会比较好处理，因为排序之后可以考虑是否可以使用双指针或者二分查找。可以好好理解一下523/525/532题的枚举思想（枚举以i为终点...之前的...）。
532 数组中的 k-diff 数对（python3 枚举、双指针）
1925 统计平方和三元组的数目（python3 暴力枚举）
611 有效三角形的个数（python3 枚举技巧、双指针、二分查找）这一题也是涉及到了枚举的技巧
686 重复叠加字符串匹配（python3 枚举分析、kmp匹配字符串）
713 乘积小于K的子数组（python3 枚举技巧、双指针）
744 寻找比目标字母大的最小字母（python3 枚举、二分查找）
组合
计算出不同种类的数目之后将两个结果相乘那么最终得到的结果就是不同种类的组合情况
1588 所有奇数长度子数组的和（python3 前缀和、组合）
1010 总持续时间可被 60 整除的歌曲（python3 余数组合）
357 计算各个位数不同的数字个数（python3 递归、排列组合 类似于生成全排列 for循环+标记列表vis生成没有重复元素的全排列）
1814 统计一个数组中好对子的数目（python3 字典计数、组合 ）遇到等式首先需要化简，将所有与当前变量有关的操作归到一边
1828 统计一个圆中点的数目（python3 枚举）判断一个二维平面上的点是否在圆内的公式：（x - x1）^ 2 + (y - y1) ^ 2 <= r * r
下面是y总关于视频中的组合数题目，组合方案不考虑元素之间的顺序，排序方案则需要考虑元素之间的顺序。
233 数字1的个数（python3 组合数）有点像数位dp的题目
python求解x个数字选出n个数字的组合（python3 递归）求解x个数中选n个数的方案
链表
445 两数相加 II（python3 翻转链表、高精度加法）
递归
① 检查图的连通性问题（使用并查集也可以解决）：可以将与当前位置相关的位置全部搜索到连接在一起，比如水洼问题、岛屿问题
② 尝试所有的可能性才可以得到最佳方案的问题（需要尝试所有可能的组合方案），这是可以使用递归解决的一类经典问题，通过尝试不同的组合来找出一个最佳方案（数据量小的时候递归可以解决但是当数据量很大的时候一般使用动态规划的思路解决）
比如搜索二维矩阵中的路径问题（从起点(0, 0)到终点(row - 1, col - 1)的路径问题），字符串组合的最佳方案问题等等
③ 二叉树或者N叉树的问题，比如求解关于二叉树中的路径问题，叶子节点的相关问题，最近公共祖先等问题（树本身就是递归定义的所以一定是可以使用递归去解决的）
④ 选或者不选当前的数字有两种写法，第一种是使用二个dfs方法来表示两个不同的状态，第二种是直接在for循环中递归，如果存在重复的方案的话我们一般选择第二种写法这样在递归的时候可以声明哈希表判重
1367 二叉树中的列表（找到一个满足条件直接返回true）
1391 检查网格中是否存在有效路径（找到一个满足条件直接返回true）
1267 统计参与通信的服务器（python3类似于水洼问题修改列表的值）
面试题 04.01. 节点间通路（python3 dfs 找到一条符合的路径直接返回True）
1161 最大层内元素和（python3 dfs使用一个变量来记录树的层数）
1123 最深叶节点的最近公共祖先（python3 dfs）
230 二叉搜索树中第K小的元素（python3 BST的中序遍历：注意类名与self.访问属性的区别）
240 搜索二维矩阵 II（python3 递归、二分查找）
865 具有所有最深结点的最小子树（python3 递归：方法中声明两个TreeNode变量使用层层往上传递结果来保存最深的节点）
404 左叶子之和（python3 递归：使用一个变量标记）
37 解数独（python3 dfs找到满足条件的直接返回True）
538 把二叉搜索树转换为累加树（python3 反序中序遍历）
987 二叉树的垂序遍历（方法中传入两个参数记录坐标、字典存储元组-值的对应关系）
面试题 04.02. 最小高度树（python3 dfs 创建二叉搜索树 ）
1593 拆分字符串使唯一子字符串的数目最大（python3 递归）
1545 找出第 N 个二进制字符串中的第 K 位（python3 递归左右两边可以看成是对称的位置）
下面的1530题感觉好经典，解决的思路很巧妙值得学习学习，特别是使用层层返回的时候来更新当前节点与左右子树的距离以及数目的技巧，然后计算出当前节点左右子树的组合情况非常巧妙（其中使用到的一个count数组也是非常巧妙：每一层的节点都是有一个count数组，对应当前节点下的左右子树的情况，然后利用下一层的节点的值在返回到上一层的时候来更新当前的节点）
1530 好叶子节点对的数量（python3 递归：层层返回数组进行更新）
LCP 07 传递信息（python3 dfs： 搜索所有路径（使用字典来存储能够使用下标访问的图））
面试题 16.19 水域大小（python3 dfs 连通性问题）
1625 执行操作后字典序最小的字符串（python3 dfs执行两个操作）
491题与90题是很类似的可以对照着理解，并且着重理解去重的技巧（特别是在for循环中递归的去重技巧）
491 递增子序列（python3 dfs搜索所有的递增子序列 + 去重技巧）
1631题是一道非常经典的dfs + 二分查找优化的问题，通过二分查找的中间值传递到dfs方法中可以来决定二分查找的方向，可以降低dfs搜索的时间复杂度
1631 最小体力消耗路径（python3 dfs + 二分查找优化）
450是一道经典的递归删除节点的题目，其中的优化代码涉及到很多节点之间复杂的指针修改关系
450 删除二叉搜索树中的节点（python3、java递归删除节点）
814题根据递归调用层层返回的结果来处理当前这一根节点的左右孩子，并且对于树的相关题目我们最好是画出具体的图来帮助我们更好理解节点之间处理的细节，并且需要利用好好由下往上节点层层返回返回的特点
814 二叉树剪枝（python3 利用递归调用返回的结果来删除节点）
669 修剪二叉搜索树（python3 递归创建删除节点后的子树）
1641 统计字典序元音字符串的数目（python3 递归求解所有按照字典序排列的字符串组合）
在树的相关题目中，对于树的遍历之后处理的方法存在两种，第一种是自上往下处理节点，第二种是自下往上处理节点（利用的是每一次递归调用都会返回到当前的节点，也就是递归层层返回的特点），自上往下处理节点是在递归方法的一开始就对节点的情况进行处理，自下往上处理节点是利用当前根节点往下递归的返回值或者节点的值进行处理，我们在写递归方法的可以分析题目看哪一种方法处理起来更加简便那么就选择哪一种方法进行处理，1315是经典的自下往上比较好处理节点的题目
1315 祖父节点值为偶数的节点和（dfs 自下往上处理节点、bfs）
1073 负二进制数相加（python3 模拟两个数组相加的过程、递归）
934题是dfs染色标记 + bfs搜索最短路径的题目
934 最短的桥（python3 dfs标记 + bfs搜索最短路径）
剑指 Offer 13 机器人的运动范围（dfs 搜索可以到达的所有位置）
863题是关于左孩子节点、右孩子节点以及父节点之间的怎么样建立联系的题目，其中利用到了递归层层返回的特点来求解当前节点的父节点到另外一个子树的距离
863/934题都是结合了dfs与bfs两种搜索的方法，其中bfs可以搜索距离为K的所有节点
863 二叉树中所有距离为 K 的结点（python3 dfs + bfs）
877题是一道存在重复子问题的递归题目，我们知道当方法中的有多少个参数在变化的时候那么我们就需要多少维的列表来记录之前已经求解过的值，对于这道题目来说当左范围与右范围相同的时候那么说明递归下去就是重复求解了，所以使用一个二维列表来记录，我们可以在递归方法调用之后将递归的结果存储到列表中，这样我们在递归方法的一开始的时候就可以通过列表的值判断之前是否已经求解过了，假如求解过那么直接返回这个值即可
395题当不满足条件的时候以字符作为分割求解剩下的子串是否满足条件
395 至少有K个重复字符的最长子串（python3 递归）
123 买卖股票的最佳时机 III（python3 记忆型递归、动态规划）
357 计算各个位数不同的数字个数（python3 递归、排列组合 类似于生成全排列 for循环+标记列表vis生成没有重复元素的全排列）
650 只有两个键的键盘 （python3 往参数规模较小的进方向进行递归 每次执行多次操作这样可以更快减小数据规模和耗时）
1849 将字符串拆分为递减的连续值（python3 递归）
下面是y总视频中讲的关于递归的相关题目：
211 添加与搜索单词 - 数据结构设计（python3 Trie树 + dfs）
212 单词搜索 II（python3 使用Trie树对dfs减枝）
236 二叉树的最近公共祖先（python3 递归）使用二进制来表示查找节点的状态
282 给表达式添加运算符（python3 递归，代数结构优化）
297 二叉树的序列化与反序列化（python dfs 通过某个特殊字符反序列化二叉树）
下面的301题删除无效的括号是y总讲的一道非常经典的递归题目，题目涉及的细节还是比较多的，在for循环中更新对应的参数之后往下递归
329 矩阵中的最长递增路径（python3 记忆化dfs搜索）这道题目是记忆化搜索的经典题目
331 验证二叉树的前序序列化（python3 模拟、dfs）
嵌套类的相关问题一般都是可以使用递归来解决的，下面的385/394/726/736题都是关于嵌套的题目（嵌套感觉本身就是递归的定义，比较常见的是括号嵌套）
385 迷你语法分析器（python3 递归 将字符串看成是一棵二叉树）
386 字典序排数（python3 Trie树思想，dfs）
404 左叶子之和（python3 递归）维护一个变量来标记是否是左子树
417 太平洋大西洋水流问题（python3 dfs，二进制思想）
437 路径总和 III（python3 递归、一维情况的扩展-前缀和 + 哈希表）
在使用递归解决的时候需要注意的是对于当前的问题需要递归返回的结果还是在递归的时候对相应的变量进行处理呢？递归返回到当前这一层的时候是从最下面开始往上处理返回层层返回的，所以当我们需要从下往上的结果的时候在递归调用完就可以修改相应的变量，类似于后序遍历对节点处理的过程，对于在递归的时候就处理相应的变量是在递归时对节点进行处理，类似于前序遍历。
450 删除二叉搜索树中的节点（python3 递归删除节点）使用python语言删除节点有一个坑是需要修改对应的左子树或者是右子树
464 我能赢吗（python3 博弈论-二进制思想、记忆化搜索）
第473题是一道经典的dfs剪枝问题，这道题目好像是由一道题目修改过来的，略微会简单一点
491 递增子序列（python3 dfs）在for循环中递归这样每一层可以声明一个哈希表进行判重
501/508题是类似的
501 二叉搜索树中的众数（python3 递归-BST的中序遍历）
508 出现次数最多的子树元素和（python3 递归）在递归的时候使用哈希表维护出现的次数
538 把二叉搜索树转换为累加树（python3 递归-反向中序遍历）
543 二叉树的直径（python3 递归-搜索每个根节点的最大直径）
563 二叉树的坡度（python3 递归计算左右子树的元素和）
653 两数之和 IV - 输入 BST（python3 递归、哈希表）
654 最大二叉树（python3 递归创建左右子树、ST表解决RMQ问题）
676 实现一个魔法字典（python3 Trie树、dfs）
685 冗余连接 II（python3 有向图中找环-dfs、寻找度为2的边）
695 岛屿的最大面积（python3 dfs求解连通块中1的最大数目）
736 Lisp 语法解析（python3 括号嵌套-递归）这里在递归求解的时候使用copy方法拷贝一个字典的副本
记忆化搜索的经典题目：
638 大礼包（python3 记忆化搜索、二维列表初始化技巧）
691 贴纸拼词（python3 记忆化搜索、状态压缩dp）
宽搜
使用宽搜思路解决的题目有一个明显的特点是：从起点到终点的最少步数，像走迷宫，在数轴的位置上从起点到终点的最少步数等问题，此外宽搜还可以关于二叉树的层次问题，如求出二叉树的深度，每一层中最右边节点等问题
bfs基本步骤：① 声明一个队列并且初始化队列的第一个节点 ② 弹出队首节点，对队首节点进行处理 ③ 往队列中加入弹出节点的周围邻接节点
使用python语言的时候经常会借助collections.deque()声明一个双端队列，并且对于二叉树的相关题目经常会使用到元组来表示当前的节点以及深度（感觉python中的元组非常方便地表示了节点与深度之间的关系）
1311 获取你好友已观看的视频（set、map、优先队列排序）
1609 奇偶树（python3 bfs： 使用for循环遍历列表模拟队列先进先出）
1315 祖父节点值为偶数的节点和（python3 dfs 自下往上处理节点、bfs）
365 水壶问题（python3 bfs 类似于蓝桥杯的分酒问题、数学推导-裴蜀定理）
1654 到家的最少跳跃次数（python3 bfs：从起点到终点的最少步数）
934题是dfs染色标记 + bfs两个搜索方法结合搜索最短路径的题目
934 最短的桥（python3 dfs标记 + bfs搜索最短路径）
199 二叉树的右视图（python3 bfs 找出每一层最右边的节点）
bfs可以用来求解所有距离为K相同的节点：在队列中发现第一个节点距离为K的时候队列中的元素都是距离为K的（bfs可以看成是沿着当前的位置向周围相同的距离进行扩展）
863 二叉树中所有距离为 K 的结点（python3 dfs + bfs）
542题使用到了多源bfs方法进行广度优先搜索，一开始的时候往队列（python一般使用collections.deque()声明一个双端队列）中加入多个节点并且使用set集合标记加入队列中的这些节点，然后开始往周围的邻接搜索，如果是二维平面的多源bfs搜索那么我们就可以将当前二维平面的所有整数点看成是两个不同的集合，我们从标记的集合节点出发搜索另外一个集合的元素，可以知道标记的集合中的节点哪一个先到达另外一个节点的位置那么表示另外一个集合到标记集合的最短距离就确定了，从而一次bfs可以解决多个源点到目标节点最短路径的问题
433 最小基因变化（python3 图论思想，宽搜）求解从原状态到目标状态的最少步数（经典的bfs问题）
637 二叉树的层平均值（python3 宽搜搜索每一层的节点）
662 二叉树最大宽度（python3 宽搜搜索每一层的节点）
675 为高尔夫比赛砍树（python3 宽搜搜索相邻两个位置的最短距离）
多源bfs：542题
指针
能够使用双指针的前提是两个指针具有单调性（针对于具体的问题我们需要找到一个含义是的一个指针往后走的时候另外一个指针单调往后走），也即当一个指针i往右走使得区间[j, i]不满足条件的时候那么指针i单调往右走，对于双指针的问题我们可以多画画图（通常声明靠后的指针为i，前面的指针为j）。
面试题 16.06 最小差（python3 排序 + 二分查找--双指针）
1577 数的平方等于两数乘积的方法数（python3 双指针）
26 删除排序数组中的重复项（python3-java 模拟：判断相邻元素是否相同、双指针）
581 最短无序连续子数组（python3 排序-双指针、栈匹配元素对应的位置）
1679 K 和数对的最大数目（python3 使用字典对余数分组、排序 + 双指针）
1750 删除字符串两端相同字符后的最短长度（python3 双指针 使用简单例子确定边界）
y总视频中讲解的双指针算法（其实应该算做是滑动窗口算法）：209题
能够使用双指针算法的前提是当一个指针往后走的时候另外一个指针单调往后走，指针不单调的是不能够使用双指针算法的
287 寻找重复数（python3 寻找环的起点：快慢指针）
345 反转字符串中的元音字母（python3 双指针、字典）
395题是非常巧妙的一道双指针题目，增加一个条件使得指针具有单调性
395 至少有 K 个重复字符的最长子串（python3 双指针）对于这种字符串在维护一个区间长度的时候考虑枚举出现的字母的...
424 替换后的最长重复字符（python3 双指针）与395题是类似的，最外层也是枚举26个字母，只是枚举的时候含义是不一样的。
有一类双指针算法的题目是字符串相关的区间问题，力扣的第3题与438题是类似的，都是关于双指针算法的经典题目。其中438题使用到了哈希表的一个技巧是每次都是维护一个长度为k的窗口的时候将哈希表中对应的次数减1。第438/567题是类似的，都是字符串相关的双指针算法问题，其中涉及到哈希表与滑动窗口的维护技巧。
438 找到字符串中所有字母异位词（python3 哈希表、双指针）
467 环绕字符串中唯一的子字符串（python3 找规律、双指针）
485 最大连续 1 的个数（python3 双指针）固定一个指针i，另外一个指针j往后走
如何快速判断一个序列是否是另外一个序列的子序列（python3 双指针），524/524题都是需要判断一个字符串是否是另外一个字符串的子序列
522 最长特殊序列 II（python3 子序列、双指针）
524 通过删除字母匹配到字典里最长单词（python 3判断一个序列是否是另外一个序列的子序列）
532 数组中的 k-diff 数对（python3 枚举、双指针）
567 字符串的排列（python3 双指针、哈希表）使用两个哈希表和双指针来维护长度为k的窗口
611 有效三角形的个数（python3 枚举技巧、双指针、二分查找）
658 找到 K 个最接近的元素（python3 大根堆维护前k大的元素、二分查找、双指针）
713 乘积小于K的子数组（python3 枚举技巧、双指针）
719 找出第 k 小的距离对（python3 二分查找、双指针）
进制
图论
图论中一般会涉及到最短路径相关算法，例如dijkstra算法，spfa算法（给定的图中存在负边）
图论思想：将题目表达的意思转换为图论的问题，从一个状态转换为另外一个状态可以看成对应的两个节点是有联系的，也即两个节点存在一条有向边（将点与点的联系看成存在一条边这样就可以将题目转换为图论的模型）。我们在很多时候遇到的问题都可以转换为图论的问题，并且这是一类经典的问题，将数组的数看成是一个点，当当前位置的数字与其他数字有联系的时候那么看成是它们之间存在一条边。
457 环形数组是否存在循环（python3 图的遍历-判断是否有环）
565 数组嵌套（python3 图论思想-求解所有环的最大长度）
无向图中找环最简单的方法：并查集，检查两个点是否在同一个集合中如果在同一个集合中那么加入当前的边就会构成环。树上判断是否存在环可以使用深搜（有向图与无向图都可以找环），一般的图可以使用Tarjian算法求解强连通分量判断是否存在环，tarjian比较适合一般的图，可以找出所有的环。找环其实是一种经典的算法，我们可以记住其中的模板需要的时候直接写出来即可。
685 冗余连接 II（python3 有向图中找环-dfs、寻找度为2的边）
分析
1465 切割后面积最大的蛋糕
1209 删除字符串中的所有相邻重复项 II（python3）
1509 三次操作后最大值与最小值的最小差（python3）
1493 删掉一个元素以后全为 1 的最长子数组（python3）
1171 从链表中删去总和值为零的连续节点（python3前缀和）
738 单调递增的数字（python3 从后往前找逆序的位置）
1561 你可以获得的最大硬币数目（python3 排序）
1562 查找大小为 M 的最新分组（python3 元组与变量协同记录连续的1的数目）
1541 平衡括号字符串的最少插入次数（python3 使用变量进行括号匹配）
1557 可以到达所有点的最少点数目（python3 统计入度为0的点集）
1053 交换一次的先前排列（python3 从后往前找第一个逆序的位置）
299 猜数字游戏（python3-java 两个字典记录不匹配数字出现的次数，字符对应的数组向右位置进行自增与自减进行匹配）
1653 使字符串平衡的最少删除次数（python3 分析、动态规划）
1664 生成平衡数组的方案数（python3 动态规划、分析）
1665 完成所有任务的最少初始能量（python3 二分查找、分析）
1446 连续字符（python3 统计连续相同的字符出现的最大次数）
1680 连接连续二进制数字（python3 位运算、分析）
1689 十-二进制数的最少数目（python3 分析：通过分析题目找出对应的规律）
1752 检查数组是否经排序和轮转得到（python3 分析： 找规律）
LCP 03 机器人大冒险（python3 模拟、分析-计算运动周期）
贪心
334 递增的三元子序列（python3找出第一小与第二小的数字）
1663 具有给定数值的最小字符串（python 3 贪心）
435与452题都是关于区间调度的类似的问题
435 无重叠区间（python3 贪心求解最多不相交区间的数目 区间调度问题）
452 用最少数量的箭引爆气球（python3 贪心、区间调度问题）
1007 行相等的最少多米诺旋转（python3 字典记录数字出现的位置、贪心）
1054 距离相等的条形码（python3 大根堆--贪心）
991 坏了的计算器（python3 正向思维与逆向思维、贪心）
1753 移除石子的最大得分（python3 贪心、找规律）
1754 构造字典序最大的合并字符串（python3 贪心）
下面是y总视频中讲的贪心题目：
316 去除重复字母（python3 贪心）对于这一类删除某些字符使得字典序最小的都是类似的都可以使用这一题的思路
321 拼接最大数（python3 贪心）贪心题的证明都是比较麻烦和抽象的，但是代码会比较好写一点
分情况讨论
406 根据身高重建队列 （python3 贪心，二分 + 树状数组）
452 用最少数量的箭引爆气球（python3 求解区间相交的个数）
502 IPO（python3 贪心、大根堆维护元素最大值）
646 最长数对链（python3 求解最多不相交区间的个数-贪心）
659 分割数组为连续子序列（python3 贪心、哈希表）
数学
1276 不浪费原料的汉堡制作方案（python3二元一次方程）
裴蜀定理：ax + by = z 有解当且仅当 z 是 x, y 的最大公约数的倍数
365 水壶问题（python3 广度优先搜索、数学推导-裴蜀定理）
592 分数加减运算（python3 字符串处理、求解最大公约数）
① 相邻两条垂直的边的平行四边形是矩形 ② 对角线的中心相同而顶点到中心的距离相等的四边形是矩形
963 最小面积矩形 II（python3 判断是否四个点能否构成矩形）
1665 完成所有任务的最少初始能量（python3 二分查找、分析、证明不等式）
剑指 Offer 14- I 剪绳子（python3 数学推导）
下面是y总视频中讲的关于数学方面知识的题目：
223 矩形面积（python3）将二维问题转化为一维问题
462 最少移动次数使数组元素相等 II（python3 绝对值不等式）
二项式展开定理：
650 只有两个键的键盘（python3 递推、数学-分解质因数）
构造
概率
在一个矩形中生成随机点其实很简单，根据横坐标与纵坐标独立的原则，使用随机函数依次生成矩形内的横坐标与纵坐标即可
470 用 Rand7() 实现 Rand10()（python3 概率）
528 按权重随机选择（python3 概率、前缀和、二分查找）
排序
1464 数组中两元素的最大乘积
1491 去掉最低工资和最高工资后的工资平均值（python3）
1619 删除某些元素后的数组均值（python3 对列表进行排序）
1647 字符频次唯一的最小删除次数（字典统计字符出现的次数 + 排序）
164题是基于桶排序的思想依次计算相邻两个同的最小元素与最大元素的差值来从而计算出相邻元素的最大间距
164 最大间距（python3 枚举、桶排序思想计算相邻元素的最大间距）
1679 K 和数对的最大数目（python3 使用字典对余数分组、排序 + 双指针）
python可以使用lambda表达式自定义排序的规则，多个参数的情况下可以使用括号来规定参数排序的顺序，参数前面添加负号表示按照从大到小进行排序
日期
KMP
686 重复叠加字符串匹配（python3 枚举、kmp匹配字符串）
RMQ
ST算法适用于不需要进行区间修改的快速求解区间最小/最大值的问题，也即ST算法不支持修改
654 最大二叉树（python3 递归、ST表解决RMQ问题）
Trie树
Trie树一般能够解决字符串中单词的匹配问题，判断某个前缀是否存在于单词列表中，Trie树有两种常见的写法，208题使用的字典来链接字符与字符之前的关系，677题使用数组和idx来链接字符与字符之前的关系
208 实现 Trie (python3 前缀树) 使用字典来表示映射当前节点的孩子节点
211 添加与搜索单词 - 数据结构设计（python3 Trie树 + dfs）
212 单词搜索 II（python3 使用Trie树对dfs减枝）
Trie树可以用来解决字符串的字典序排序问题，下面的386题使用到了Trie树的思想，非常巧妙好好理解一下
386 字典序排数（python3 Trie树思想，dfs）
421题也是经典的借助于Trie树思想的题目，将数字对应的二进制存储到Trie树中
421 数组中两个数的最大异或值（python3 Trie树优化）
676 实现一个魔法字典（python3 Trie树、dfs）字符串存储 + 前缀操作==> 想到Trie树
对顶堆
扫描线
自动机
格雷码
字符串
1233 删除子文件夹（python3字符串排序，startswith判断是否是前缀）
592题使用python中的re模块分割字符串
592 分数加减运算（python3 字符串处理、求解最大公约数）
思维题
逆序对
统计逆序对的数目一般有两种做法，第一个做法是树状数组，第二种是归并排序思想
剑指 Offer 51 数组中的逆序对（python3 树状数组、归并排序思想）
回文串
730 统计不同回文子序列（c++-python3 区间dp）
全排列
一般是已知长度为k的不重复元素的列表或者数组，生成包含所有元素的全排列。一般使用递归中交换各个元素的位置来生成所有元素的全排列，也可以使用在for循环中进行递归，并且结合标记列表或者数组来标记哪一个是被访问过如果之前被访问过了那么当前就不能够使用这个元素了
离散化
离散化主要是数据比较分散不可能直接开很大的数组，所以需要将这些分散的数字映射到连续的位置，方便节省空间
699 掉落的方块（python3 区间修改-带懒标记的线段树）
剑指 Offer 51 数组中的逆序对（python3 树状数组、归并排序思想）
线段树
线段树可以解决区间相关的大部分问题，如单点修改，区间修改，区间查询，区间最大值，最大连续子段和，染色求面积等区间问题，线段树一个特别好的功能是能够支持修改操作（包括单点修改与区间修改），所以适用于大部分区间动态修改（单点修改与区间修改）与区间查询相关的问题。
1264 动态求连续区间和（c++-java-python 线段树模板-无懒标记）
699 掉落的方块（c++-java 区间修改-带懒标记的线段树）
731 我的日程安排表 II（c++-java-python 线段树-动态开点、模拟）
平衡树
c++中的set类似于平衡树，可以实现平衡树的基本插入，查询的操作。
715 Range 模块（c++ set维护区间的动态信息）
单调栈
可以使用栈来维护一个长度k的递增子序列或者是递减子序列
单调栈-找到左边/右边第一个比自己小/大的元素（python3 模板）
121 买卖股票的最佳时机（python3 寻找数组中单调递增的序列中最小数字与最大数字--单调栈）
456题是一道使用单调栈优化但是思路比较难想的题目
503 下一个更大元素 II（python3 单调栈、破环成链技巧）
739 每日温度（python3 单调栈-右边第一个自己大的元素）
找规律
有的时候需要自己模拟一下测试样例看是否存在某种规律当存在某种规律的时候那么就可以使用循环进行模拟
781 森林中的兔子（python3 字典统计数字出现的次数）
467 环绕字符串中唯一的子字符串（python3 找规律、双指针）
522 最长特殊序列 II（python3 子序列、双指针）
540 有序数组中的单一元素（python3 找规律、二分查找）
博弈论
877题是一道关于博弈的问题，对于博弈的问题因为涉及到两个人的分数所以我们可以定义一个相对分数（两者分数之差），这样不管使用记忆型的递归还是动态规划都可以很好计算两者分数的差距最终判断这个相对分数大于0来判断是谁赢得比赛
877 石子游戏（python3 记忆型递归、动态规划、博弈）
464题是一道经典的博弈问题，其中使用了记忆化搜索搜索赢的状态
464 我能赢吗（python3 博弈论-二进制思想、记忆化搜索）
博弈论问题常见的递归搜索、dp解法
并查集
1584 连接所有点的最小费用（python3 kruskal 算法最小生成树）
前缀和
可以在O(1)的时间计算出某个区间和，一般涉及到区间和都可以考虑前缀和的思路（静态前缀和，也即不需要修改数组元素的情况），在很多情况下前缀和会结合哈希表进行优化，1524题的图非常清楚了表达了两者优化求解的过程。
下面1524题是关于计算[0，i]的区间前缀和为奇数还是偶数 + [0, i - 1]前缀和为奇数与偶数的数目计算出区间和为奇数的数目(区间和问题) 公式：和为偶数区间 + 和为奇数区间 = 和为奇数区间 ，和为奇数区间 + 和为奇数区间 = 和为奇数区间
1171 从链表中删去总和值为零的连续节点（python3 前缀和 ：区间和问题）
1588 所有奇数长度子数组的和（python3 前缀和、组合：区间问题）
209 长度最小的子数组（python3 前缀和+二分查找、滑动窗口：区间和为某个值s）
1712题前缀和 + 二分查找划分三个区间
1712 将数组分成三个子数组的方案数（python3 前缀和 + 二分查找）
1695 删除子数组的最大得分（python3 滑动窗口、前缀和计算某个区间的值、字典）
1838 最高频元素的频数（python3 排序 + 滑动窗口，前缀和 + 二分查找）
303 区域和检索 - 数组不可变（python3 前缀和）
528 按权重随机选择（python3 概率、前缀和、二分查找）
二维前缀和
二维前缀和可以判断快速判断某一个子矩阵中的元素是否相同
304 二维区域和检索 - 矩阵不可变（python3 二维前缀和模板）利用公式计算即可
363 矩形区域不超过 K 的最大数值和（python3 二维前缀和、bisect维护插入元素有序）
前缀和 + 哈希表优化
很多时候前缀和都会结合哈希表进行优化，降低时间复杂度，经常用来求解某个区间和是k的倍数...和为k的区间个数等问题
下面1546 是一道比较经典的题目，使用了哈希表进行了优化，这样省略了之前计算先遍历一遍数组计算所有位置的前缀和的操作，使用哈希表（字典）检查是否存在和为target的区间，我们在遇到有关区间求和的问题首先需要想到的是前缀和的思路然后再考虑是否可以使用哈希表（字典）进行优化
1546 和为目标值的最大数目不重叠非空子数组数目（python3 前缀和 + 字典优化）
1658 将 x 减到 0 的最小操作数（python3 字典、前缀和计算某一个区间的和）
1542题是一道经典的前缀和 + 哈希（字典）思想的题目
1542 找出最长的超赞子字符串（python3 状态压缩、前缀和 + 哈希表）
523/525/560题是类似的分析思路，这三题都涉及到了枚举的思想，也即枚举当前位置i为终点的所有区间这样就可以将所有答案枚举出来。这些问题基本上是求解以区间和为k的倍数的数目，区间和为t的数目问题。
437 路径总和 III（python3 一维情况的扩展-前缀和 + 哈希表）
523 连续的子数组和（python3 枚举、前缀和、哈希表）
560 和为K的子数组（python3 枚举、前缀和、哈希表）
快速幂
循环节
位运算
可以使用(x - 1) & x == 0或者x % -x == x 来判断当前的数字nums是否是2的整数次幂，因为当num为2的整数次幂的时候与前一个数字恰好是互为取反的关系，例如数字3与数字4对应的二进制数字为011与100所以经过与运算之后得到的结果肯定是0。异或操作：x xor 0 = x，x xor x = 0。
1386题使用二进制的0与1表示两种不同的情况，1 << n可以将第n位二进制位置为1，第n为是从低位开始算起的（也即1 << n可以得到二进制数字100...0，1后面有n个0），或运算可以保持原有数字的基础上将某些二进制位置为1
1542题使用到了异或运算计算字符出现的次数是偶数次数还是奇数次数，使用1 << n得到第n位的二进制为1的数字
1542 找出最长的超赞子字符串（python3 状态压缩、前缀和 + 哈希思想）
1680使用的就是(num - 1) & num来判断num是否是2的整数次幂，通过在循环判断当前的num是否是2的整数次幂来计算当前数字num的二进制位数，通过x = x << (len2(num)) + num这个公式来连接1~num的二进制数字对应的十进制数字的结果
1680 连接连续二进制数字（python3 位运算、分析）
289 生命游戏（python3 模拟、二进制）充分利用了二进制中只使用到了一位的特点，所以通过移位操作就可以利用32位数字对应二进制的其他位
401 二进制手表（python3 枚举、位运算）移位运算计算二进制1的数目
638 大礼包（python3 记忆化搜索、二维列表初始化技巧）
子序列
300 最长上升子序列（python3 动态规划、贪心 + 二分查找）
334 递增的三元子序列（python3 动态规划-最长上升子序列）
1626 无矛盾的最佳球队（python3 动态规划-最长上升子序列）
354 俄罗斯套娃信封问题（python3 动态规划-最长上升子序列）
dp求解方案数目
dp求解方案数目可以使用倒推的方法求解，下面的368题是一道经典的最长上升子序列问题求解最佳方案的问题
368 最大整除子集（python3 最长上升子序列-dp逆推方案）
如何快速判断一个序列是否是另外一个序列的子序列->双指针算法，时间复杂度为O(n)
524 通过删除字母匹配到字典里最长单词（python 3判断一个序列是否是另外一个序列的子序列）
583 两个字符串的删除操作（python3 动态规划-递推）
673 最长递增子序列的个数（python3 动态规划-最长上升子序列）
712 两个字符串的最小ASCII删除和（python3 最长公共子序列）
730 统计不同回文子序列（c++-python3 区间dp）
子数组
718 最长重复子数组（python3 二分查找、字符串哈希）
后缀和
538 把二叉搜索树转换为累加树（python3 递归-反向中序遍历）
蓝桥杯
平方拆分（第十届蓝桥杯国赛Java-B组 java-python dfs ）
numpy
python3
python3基础练习100题（根据常见问题来练习python3中的api）
数据结构
主要包括了以下几个方面的应用：map映射、计数 ，set集合(去重)，list集合(列表)，字典（dict）
将相同的东西放在一起或者是计数的问题都可以使用哈希表来解决（例如计算所有的数字或者是所有的字符的出现次数），哈希表是一种数据结构，对于不同的语言有不同的表现形式，c++或者是java语言可以使用map、python语言可以使用字典dict来表示哈希表（哈希表主要用来解决计数与映射关系：y = f(x)，相当于一个函数），使用哈希表进行计数之后可以通过遍历哈希表的键值对，通过当前的键来寻找哈希表中是否存在另外一个和为target的数字（1711题）
python中可以使用字典来表示哈希表，经常使用collections.defaultdict(int)或者是collections.defaultdict(list)创建，int和list表示字典中值的类型，当字典中不存在这个值的时候那么默认值为0或者是list，这样就可以直接进行计数或者是添加对应的元素到键对应的list列表中，可以省略判断键是否存在于字典的步骤，此外还可以使用collections.Counter方法统计直接统计字符或者数字出现的次数。python中的collections.defaultdict(list)是可以用来创建dfs搜索的邻接表，其中键表示节点编号，值为相互连接的其余节点。
我们遇到问题的时候首先是想怎么样才可以把答案做出来，其次才是优化，数据结构是一种工具有的时候与问题本身没有什么关系，我们有的时候只是借助于数据结构来优化时间或者是空间。
1366 通过投票对团队排名（java8语法，list转为map进行排序）
1311 获取你好友已观看的视频（set、map、优先队列排序）
1296 划分数组为连续数字的集合（treemap）
1481 不同整数的最少数目（python3的Collections中的Counter方法对列表中的元素进行计数）
1207 独一无二的出现次数（python3的Collections.Counter方法将列表转换为字典进行计数）
229 求众数 II（python3的Collections.Counter方法计数）
1577 数的平方等于两数乘积的方法数（python3 字典计数）
1583 统计不开心的朋友（python3字典：index函数的使用）
剑指 Offer 56 - II. 数组中数字出现的次数 II（字典、位运算）
1539 第 k 个缺失的正整数（python3 模拟、字典）
1525 字符串的好分割数目（python3 两个字典对左右两边的字符进行计数）
1010 总持续时间可被 60 整除的歌曲（python3字典映射）
1604 警告一小时内使用相同员工卡大于等于三次的人（python3字典映射）
387 字符串中的第一个唯一字符（python3 字典计数）
1620 网络信号最好的坐标（python3 枚举、字典存储坐标点）
1624 两个相同字符之间的最长子字符串（python3 字典记录字母第一次出现的位置）
349 两个数组的交集（python3 字典、&运算求解两个集合的交集）
1640 能否连接形成数组（python3 字典记录数字出现的位置）
python对字典进行排序的时候可以使用lambda表达式定义排序的规则：dic = sorted(dic.items(), key=lambda x:(x[1], -x[0]))，当传入两个参数的时候第一个参数表示的是先按照第一个参数（键或者是值，x[0]表示键，x[1]表示值）进行排序，当第一个参数相同的时候然后再按照第二个参数进行排序，对值为int类型的值进行排序的时候可以对第二个参数添加负号表示降序排序（前提是第一个参数是升序排序，reverse=True或者是默认不写）
1636 按照频率将数组升序排序（python3 字典统计数组中各个数字出现的次数：python可以定义键值对的排序规则）
299 猜数字游戏（python3 两个字典记录不匹配数字出现的次数）
1647 字符频次唯一的最小删除次数（python3 字典统计字符出现的次数 + 排序）
在前缀和的题目中，经常会使用到与字典（哈希表）一起检查是否存在和为x的区间，其中1546/1658题使用的都是前缀和 + 字典的方式来寻找某一个区间和等于目标值x的方法
1546 和为目标值的最大数目不重叠非空子数组数目（python3 前缀和 + 字典优化）
1658 将 x 减到 0 的最小操作数（python3 字典、前缀和计算某一个区间的和）
1657 确定两个字符串是否接近（python3 字典统计字符出现的次数）
1007 行相等的最少多米诺旋转（python3 字典记录数字出现的位置、贪心）
1368题使用字典来记录每一行位置被预约的情况，使用collections.defaultdict(list)来创建能够为键添加多个元素的字典，字典的值为list列表，假如需要将某些值存储到字典中不存在的键中，会默认创建一个空的list列表这样就可以直接将多个元素添加到键对应的list中（一开始的时候没有什么特别好的思路所以使用字典来记录每一行的位置的情况，并且根据题目描述的求解方式求解出答案看是否可以解决问题）
1542题是一道经典的前缀和 + 哈希（字典）思想的题目
1542 找出最长的超赞子字符串（python3 状态压缩、前缀和 + 哈希思想）
767 重构字符串（python3 大根堆--贪心、字典统计字符出现的次数）
1054 距离相等的条形码（python3 大根堆--贪心、字典统计数字出现的次数）
1497是一道关于余数的经典题目，使用字典对余数进行分组，检查是否能够被k进行整除：对k取余之后相加的结果等于k那么取余之前相加的结果肯定能够被k整除（已知一个数检查和为k的另外一个数是否存在就可以使用字典来进行检查）
1497 检查数组对是否可以被 k 整除（python3 使用字典对余数进行分组）
1679 K 和数对的最大数目（python3 使用字典对余数分组、排序 + 双指针）
1695 删除子数组的最大得分（python3 滑动窗口、前缀和、字典标记是否存在重复）
1748 唯一元素的和（python3 字典统计数字出现的次数）
781 森林中的兔子（python3 字典统计数字出现的次数）
1814 统计一个数组中好对子的数目（python3 字典计数、组合 ）遇到等式首先需要化简，将所有与当前变量有关的操作归到一边
1832 判断句子是否为全字母句（python3 字典计数）使用字典 + 一个计数变量判断出现的次数
217 存在重复元素（python3 字典统计数字出现的次数（哈希表））
345 反转字符串中的元音字母（python3 双指针、字典）
347 前 K 个高频元素（python3 哈希表、计数排序思想）
380 O(1) 时间插入、删除和获取随机元素（python3 字典与列表）
389 找不同（python3 哈希表 统计字符出现的次数）
398 随机数索引（python3 哈希表 collections.defaultdict声明值可以为多个元素的列表类型）
438 找到字符串中所有字母异位词（python3 哈希表、双指针）
451 根据字符出现频率排序（python3 对字符串自定义排序）
508 出现次数最多的子树元素和（python3 递归、哈希表）
1935 可以输入的最大单词数（python3 暴力枚举、哈希表）
523 连续的子数组和（python3 枚举、前缀和、哈希表）
哈希表经常用来检查两个数的差值是否为k的题目，考虑枚举的是的nums[i]，检查在哈希表中是否存在这样的nums - k，如果存在说明符合条件
535 TinyURL 的加密与解密（python3 哈希表）
哈希表可以在求解数组中是否存在两个数的和等于目标值的问题，类似于前缀和 + 哈希表的优化算法，我们可以在遍历的时候将遍历过的值存储到哈希表中，这样可以边遍历边检查哈希表中是否出现过某个数字即可。
653 两数之和 IV - 输入 BST（python3 递归、哈希表）
659 分割数组为连续子序列（python3 贪心、哈希表）
715 Range 模块（c++ set维护区间的动态信息）
维护有序
有的时候需要在插入元素的时候维护对象是有序的，对于c++语言可以将元素插入到set集合（set集合的元素是有序的），python可以使用bisect模块中的insort_left将元素插入到列表中并且使得列表元素是有序的，当插入元素的时候是有序的时候就可以使用二分查找方法。bisect模块可以动态维护插入元素是有序的一段区间（类似于c++中的平衡树）
363 矩形区域不超过 K 的最大数值和（python3 二维前缀和、bisect维护插入元素有序）
480 滑动窗口中位数（python bisect模块动态维护一段有序的区间）
代数结构
维护一个代数结构，这个代数结构能够表示任意的表达式
282 给表达式添加运算符（python3 递归，代数结构优化）
计算几何
数位统计
按照一位位考虑可能的情况，细节还是比较多的，下面的440题是经典的数位统计的题目。
奇淫技巧
448 找到所有数组中消失的数字（python3 哈希表、奇淫技巧）
破环成链
当为循环数组的时候我们可以使用到的一个技巧将原数组复制一份放到后面即可
503 下一个更大元素 II（python3 单调栈、破环成链技巧）
发散思维
453题是一道很好的题目，当遇到这种类型的题目如何思考解决方式？
动态规划
1. 动态规划的思路一般求解的是关于最佳方案的问题（大部分是求解一个数），最基本的动态规划应该是使用一维数组（或者列表）或者二维数组（或者列表）进行递推，从上一个状态递推到当前状态，直到最后一个状态（1621是一道经典的动态规划题），动态规划很多时候可以看成是暴力枚举的优化，在递推的过程中记录在有效的方案（状态），通过上一步的记录的状态来推导出当前的状态，一直到最终的目标状态。一般一维dp与二维dp求解的是最佳方案的某一个数值，当数据量为10 ^ 5左右的二维矩阵中一般也是需要往动态规划的思路上想。动态规划比递归的时间复杂度要小呢？原因是是递归每一次处理（搜索）的是一个问题但是动态规划解决的一类问题。
2. 在y总的B站视频中关于dp知识点的主要有两个步骤：① 状态表示，其中会涉及到很多的动态规划模型，这些模型的表示不是自己想出来的而是通过做这一类的题目记忆下来下次遇到类似的模型那么就可以直接想到这个，结合题目调整这个模型即可，其中动态规划常见的模型有：数字三角形模型、最长上升子序列模型、背包模型、状态机模型、状态压缩dp、区间dp、树形dp、数位dp、单调队列优化dp，斜率优化dp、字符串dp等模型。这些都表示一大类的dp问题，很多题目往往是这些模型的变题，另外一些dp就需要多做题掌握一些状态表示和状态计算的方法了。② 状态计算，以集合的角度来考虑这个问题，通过理解当前的属性表示的含义进行状态的计算。
3. 到后面刷题的时候发现当我们需要尝试所有可能的解决方案的时候我们看是否可以使用动态优化（递推）的思路去优化我们的递归求解，一般可以使用递归解决的可以尝试动态规划求解。组合优化（背包问题）、分解的最优解问题（343题）都是可以使用动态规划解决的。
1191 K 次串联后最大子数组之和（python3最大连续子数组的和）
1594 矩阵的最大非负积（python3 与152题乘积最大子数组类似：使用两个变量记录当前位置的最小值与最大值）
1524 和为奇数的子数组数目（python3 以当前位置i结束的子数组的前缀和）
1567 乘积为正数的最长子数组长度（python3 152-1567-1594都是类似的问题）
322与474题是关于背包问题的比较经典的问题
300题与1626题本质上都是LIS模型（最长上升子序列模型），300题的贪心 + 二分查找解决的思路是非常棒的，时间复杂度为O(nlogn)
300 最长上升子序列（python3 动态规划、贪心 + 二分查找）
1626 无矛盾的最佳球队（python3 最长上升子序列）
410 分割数组的最大值（python3 二分查找、动态规划）
1641 统计字典序元音字符串的数目（python3 递归、由上一个状态递推出当前的状态）
1027是一道比较经典由前面状态递推出当前状态的的动态规划题目，而且对于关于数据规模比较大的数组类的最优问题基本上是可以使用动态规划去解决的，并且我们定义的dp数组的含义经常是以当前位置i结尾的数字对应的（一般子序列问题都是这样定义的）...最优...，为什么这样定义呢：因为这样就可以从前面状态递推出当前的状态，我们可以将当前结尾的这个数字尝试添加到之前的状态中看是否可以构成更优的方案
我感觉动态规划需要培养的就是第一个怎么样定义dp数组的含义，一维还是二维还是三维，第二个是写出具体的状态转移方程，这道题目是比较好理解的状态转移的题目，可以好好学习一下
1638是一道关于两个字符串的子串匹配的动态规划问题（以当前位置的字符结尾对应长度的子串的匹配第二个字符串中相同长度的子串问题），关于字符串的动态规划题目，对于dp的含义多往以上一个字符结尾对应的dp数组的值...去想，以上一个字符结尾的dp数组的值推导出当前位置对应的dp数组的值
1638 统计只差一个字符的子串数目（python3 动态规划）
1653题理解二维dp的含义，在上一步的基础上进行迭代得到当前状态下dp数组的值
1653 使字符串平衡的最少删除次数（python3 分析、动态规划）
1664 生成平衡数组的方案数（python3 动态规划、分析）
877题是一道很经典的动态规划题目，由一个小范围的值推导出更大范围的值（无后效性），这里需要注意的是怎么样利用两层循环由小范围的值推导出更大范围的值
动态规划需要使用到dp数组，而且一开始的时候最简单的方法是根据需要求解的问题以及涉及到的几个动态变化的参数来确定需要使用几维的dp数组，确定之后需要明确dp数组的含义，dp数组的含义很重要因为会关系到接下来如何由小范围的dp数组的值推导出dp数组更大范围的值，假如是二维dp通常需要使用到两层循环，这个时候就涉及到怎么样由小的范围确定大的范围的dp数组值，一般都是以最外层的循环为右边界一直递推到0这个范围从而确定dp[0][r]的值，每一次都是这样推导从而最终得到最大范围的dp数组的值，877题与1335就是二维的dp数组根据两层循环以最外层循环为右边界往左边进行推导（可以多理解一下这两道题目中使用两层循环从右边界往左推导的过程以及表达的具体含义可能对dp解决问题的思路会更熟悉一点）
1049题是01背包模型，01背包：在背包容量、物品重量、物品价值确定的情况下，怎么样拿取物品到背包中使得最后背包中物品的价值是最大的，可以使用一维的dp数组解决，dp[j]表示背包容量为j的情况下背包中物品的最大价值，我们可以从尝试将当前的物品放置到容量最大的那个背包到容量为当前物品重量的那个背包，求解出当前的dp[j]的最大值，这样每一次放置物品的时候都可以利用上一次dp[j]的最大价值的信息推导出当前背包dp[j]的信息，这样最后dp数组的最后一个元素的值肯定是最大的。
1049 最后一块石头的重量 II（python3 零一背包问题）
1696 跳跃游戏 VI（python3 动态规划、优先队列优化）
198 打家劫舍（python3 动态规划 由简单例子分析出递推公式）
123 买卖股票的最佳时机 III（python3 记忆型递归、多维动态规划）
97/1143题都是二维动态规划的经典问题，二维动态规划最好的理解的办法是画出例子进行dp[i][j]的推导，二维表格有助于理解状态之间的转移与状态方程的编写
97 交错字符串（python3 二维动态规划）通过二维表格表示两个字符串之间的交错拼接顺序，核心是二维表格位置表示的含义，通过二维表格进行递推
下面是y总视频中讲的动态规划的题目：
213 打家劫舍 II（python3 动态规划）求解一个环中若干个不相邻点的最大和
下面446题的动态规划感觉还是挺难的，好好理解一下。
446 等差数列划分 II - 子序列（python3 动态规划-递推）
对于某些字符串的最优方案问题我们可以考虑dp来解决
514 自由之路（python3 动态规划）二维字符串dp，一般考虑前i个字符...，然后想怎么样状态计算
552题中包含了常见的动态规划递推中的状态转移的两种枚举技巧，可以好好理解一下
552 学生出勤记录 II（python3 递推-动态规划-枚举技巧）
583 两个字符串的删除操作（python3 动态规划-递推）
650 只有两个键的键盘（python3 递推、数学-分解质因数）
688 "马"在棋盘上的概率（python3 动态规划-递推）
689 三个无重叠子数组的最大和（python3 动态规划-递推 dp求字典序最小的方案）
741题是从起点到终点走两条路径的经典题目，如果是走k条路径则需要使用费用流来解决
树形dp
树形dp分为自上往下与自下往上求解
数位dp
区间dp
730 统计不同回文子序列（c++-python3 区间dp）
状态机dp
309 最佳买卖股票时机含冷冻期（python3 状态机dp）
714 买卖股票的最佳时机含手续费（python3 状态机dp）
字符串dp
583 两个字符串的删除操作（python3 动态规划-递推）
背包问题
背包问题中主要是关于"凑"的相关问题，所以当我们遇到在一定条件下去"凑"并且需要求解最优解的时候那么判断是否可以使用背包模型（组合类的优化问题）。背包问题求解方案数目也是类似的，dp数组存储的就是方案数目，一般都是当前的状态需要累加上一个状态的方案数目最终得到总的方案数目。
1049 最后一块石头的重量 II（python3 零一背包）
377题与一般的背包问题是不一样的，需要考虑顺序，所以枚举的是每一个位置，可以好好理解一下其中的思路
416 分割等和子集（python3 零一背包）需要识别出具体的零一背包模型，判断在背包容量为v的条件下是否可以恰好装满背包
二维费用的背包问题：474题与acwing的第8题属于经典的二维费用的背包问题。
高维背包问题：对于高维背包我们可以尝试记忆化搜索的方法来解决，记忆化搜索可以避免重复求解已经求解过的和某些不合法的状态
638 大礼包（python3 记忆化搜索、二维列表初始化技巧）
单调队列
一般需要声明一个双端队列对队头与队尾的元素进行增加、删除元素的操作
差分数组
可以用来求解出关于多个相交的区间上的点出现的频数问题，关于区间上的问题可以多往差分数组、前缀和（ 某个区间上的和）、树状数组这些方面思考
1589 所有排列中的最大和（python3 差分数组、排序）
蓝桥杯--算法提高--VIP--分苹果题目（python3 差分数组）
下面是y总视频中差分数组的题目
主要用来快速判断数组中相邻两个元素的差值
拓扑排序
归并排序
归并排序主要使用的是分治的思想，求解逆序对使用的就是归并排序的思想
剑指 Offer 51 数组中的逆序对（python3 树状数组、归并排序思想）
滑动窗口
1052与1208题使用的模板都是类似的，都是先初始化 l = r = 0，然后滑动右窗口等到题目不满足条件的时候缩小左边的窗口并且在滑动窗口的时候计算出每个窗口的最佳答案，可以对照着理解这两道题目
1208 尽可能使字符串相等（python3 滑动窗口模板）
209题是一道经典的滑动窗口思路的题目，这一类问题有一个明显的特点是寻找满足某个条件的长度最小的区间，所以一般滑动窗口能够解决基本上是...长度最小的问题
209 长度最小的子数组（python3 前缀和+二分查找、滑动窗口）
1695 删除子数组的最大得分（python3 滑动窗口、前缀和、字典）
1838 最高频元素的频数（python3 排序 + 滑动窗口，前缀和 + 二分查找）滑动窗口的题目一般会给出一个最大的限制条件进行限制
下面是y总视频中讲解的滑动窗口的题目：
维护一个长度为k的窗口可以使用两个指针i，j进行移动
220 存在重复元素 III（python3 分桶、滑动窗口）使用bisect模块来维护集合s中插入元素之后的有序性
排序算法
快速选择
快速选择算法基于快速排序算法思想，快速选择算法根据当前主元位置i与k的大小关系决定递归哪一边，可以求解出排序之后第k小（由小到大排序）或者是第k大（由大到小排序）的元素，注意在比较的时候需要注意大小写的符号，可以好好理解一下力扣的215题与acwing7686题。
215 数组中的第K个最大元素（python3 快速选择算法-第k大的元素）
786 第k个数（python3 快速选择算法-第k小的元素）
树状数组
树状数组和线段树数据结构主要使用在一个区间中单点更新操作比较频繁而且需要查询某个区间和的操作中（单点修改与区间查询），一般来说能够使用树状数组使用树状数组，不能够使用树状数组则使用线段树（线段树能够处理树状数组不能够处理的问题），因为树状数组的代码更短，时间复杂度更低（主要结合lowbit函数），树状数组一般有三个操作，lowbit(x)：求解最低位的1对应的数字，query(x)：查询[1:x]区间和，add(x, v)：更新操作，将树状数组的x位置的值加上v。有的时候会使用二分 + 树状数组进行优化。
307 区域和检索 - 数组可修改（python3 树状数组模板）
315 计算右侧小于当前元素的个数（python3 树状数组）
406 根据身高重建队列 （python3 贪心，二分 + 树状数组）
剑指 Offer 51 数组中的逆序对（python3 树状数组、归并排序思想）
树的哈希
二分查找
二分查找比较经典的题目：1102/410/774/875/LCP12/1011/1062/1482/1552，这些题目基本上都是可以使用类似的二分查找模板（确定最小边界与最大边界，查找中间值mid-这个中间值mid是有具体的含义的，然后判断mid是否符合题目要求来更新下一次二分查找的范围）。二分查找需要明确的一个点是查找的是什么，很多情况下二分的就是我们要求解答案。能够使用二分的前提是每一次能够通过某个策略能够判断出答案是在左边还是在右边，单调性是能够使用二分的一个特点。
二分查找模型的另外一个特点是求解最小化最大值问题和最大化最小值问题
240 搜索二维矩阵 II（python3 递归、二分查找）
面试题 16.06 最小差（python3 排序 + 二分查找--双指针）
1011 在 D 天内送达包裹的能力（python3 二分查找最小化最大值问题）
1631 最小体力消耗路径（python3 dfs + 二分查找优化）
410 分割数组的最大值（python3 二分查找、动态规划）
209题二分查找新思路：只查找满足条件的区间
209 长度最小的子数组（python3 前缀和 + 二分查找、滑动窗口）
当数据规模比较大而且不能够使用动态规划的思路解决的时候需要往二分查找这方面去思考，一个最简单的方法检验是否能够使用二分查找策略的方法：找出题目中的所有参数然后检验二分查找当前的参数是否可行，假如可行说明二分查找这个参数的方案是可行的，这样最终就可以求解出符合要求的答案，1648就是一道使用二分查找思路比较隐晦的题目，因为这道题目中二分查找的参数不是最终的答案，我们还需要根据二分查找的结果最后计算出最终的答案，所以会多了一个步骤。
1665题是一道二分查找比较难想到如何检测mid是否满足题目的条件的题目，可以学习学习
1665 完成所有任务的最少初始能量（python3 二分查找、分析）
LCP 08题是关于二分查找过程中判断多个属性是否同时满足条件的题目，需要多学习一下其中的思路
LCP 08 剧情触发时间（python3 二分查找-二分查找的过程中需要判断多个属性值是否满足题目条件）
162题是根据题目的具体条件进行的二分查找
1712 将数组分成三个子数组的方案数（python3 前缀和 + 二分查找：对于数据规模大于等于10 ^ 5的要多想想二分查找）
1838 最高频元素的频数（python3 排序 + 滑动窗口，前缀和 + 二分查找）明确查找的是什么
y总视频讲的二分题目：
222 完全二叉树的节点个数（python3 递归、二分查找）
352 将数据流变为多个不相交区间（python3 二分查找第一个大于等于x的位置）
378 有序矩阵中第 K 小的元素（python3 多路归并、二分查找）
406 根据身高重建队列 （python3 贪心，二分 + 树状数组）
最小化最大问题最大化最小问题一般的做法是二分查找（需要先检查是否具有二段性，也即判断是否可以使用二分查找方法解决：是否存在一种方案能够判断出答案是在左边还是在右边）
410 分割数组的最大值（python3 最小化最大问题-二分查找）
483 最小好进制（python3 数学、二分查找）...随着...是单调的
528 按权重随机选择（python3 概率、前缀和、二分查找）
540 有序数组中的单一元素（python3 找规律、二分查找）
611 有效三角形的个数（python3 枚举技巧、双指针、二分查找）
658 找到 K 个最接近的元素（python3 大根堆维护前k大的元素、二分查找、双指针）
718 最长重复子数组（python3 二分查找、字符串哈希）
719 找出第 k 小的距离对（python3 二分查找、双指针）
744 寻找比目标字母大的最小字母（python3 枚举、二分查找）
洗牌算法
树的直径
543 二叉树的直径（python3 递归-搜索每个根节点的最大直径）
区间调度
关于区间的相关题目可以尝试一下贪心的思路求解
435 无重叠区间（python3 贪心求解最多不相交区间的数目 区间调度问题）
452 用最少数量的箭引爆气球（python3 贪心求解连续相交区间的数目 区间调度问题）
区间问题
对于区间问题一般考虑贪心的思路，要不就是区间左端点，要不就是右端点，要不就是双关键字排序。
主要存在一维与二维的情况，一维求解有多少个区间和等于目标值的个数与二维的时候在树上求解路径总和等于目标值的路径数目，下面对应这两种情况：
一维求解区间总和等于目标值的区间个数可以使用前缀和 + 哈希表的思路解决，在遍历的时候先将前缀和存储到哈希表中然后使用哈希表检查是否存在以当前i为右端点区间并且存在左端点构成的区间[j - 1, i]的和是等于目标值（1546/1658题都是经典的前缀和 + 哈希优化的问题）
437 路径总和 III（python3 一维情况的扩展-前缀和 + 哈希表）
452 用最少数量的箭引爆气球（python3 求解区间相交的个数-贪心）
646 最长数对链（python3 求解最多不相交区间的个数-贪心）
状态压缩
1542 找出最长的超赞子字符串（python3 状态压缩、前缀和 + 哈希思想）
求解质数
如果数据范围不是特别大使用线性筛可以求解出1~n的所有质数或者是求解出n个质数，但是如果n非常大(大于10^ 6)的话那么就需要使用埃氏筛
约瑟夫环
余数分组
通过哈希表将相同余数的数组放在一起，这样可以计算出数组中和为某个数target的所有组合
1497 检查数组对是否可以被 k 整除（python3 使用字典对余数进行分组）
1679 K 和数对的最大数目（python3 使用字典对余数分组、排序 + 双指针）
欧拉路径
括号序列
栈与队列
使用栈解决的题目有一个典型的特点：需要根据当前的元素的某些条件决定怎么样处理上一个元素，此外元素之间的匹配问题都是可以使用栈来解决的，理解一下栈解决的1047题、1544题、1598题对栈的模型就比较熟悉了（反正是一看到存在这种特点的一定是可以使用栈来解决的）
1311 获取你好友已观看的视频（set、map、优先队列排序）
1614 括号的最大嵌套深度（python3 栈：匹配的策略：当发现右括号的时候进行答案的更新））
1047 删除字符串中的所有相邻重复项（python3 栈）
581题结合了排序的思想并且使用到了栈的一个作用：匹配元素适当的位置（结合排序思想可以用来寻找无序数组的最小边界与最大边界）
581 最短无序连续子数组（python3 排序-双指针、栈匹配元素对应的位置）
1696题使用了python中的优先队列（元素可以被赋予优先级别）PriorityQueue进行优化，优先队列可以设置元素的优先级别所以可以优先处理队列中的某些元素
1696 跳跃游戏 VI（python3 动态规划、优先队列优化）
122 买卖股票的最佳时机 II（python3 寻找所有单调递增的序列-栈）
1834 单线程 CPU（python3 lambda表达式排序 + 优先队列）python中的heapq模块可以实现优先队列的相关操作
下面是y总讲的关于栈和队列的相关题目
388 文件的最长绝对路径（python3 栈维护层次关系）
对于删除k个元素条件下求解最小或者最大值的题目都是可以使用栈来维护的，在遍历的时候判断当前遍历的元素与栈顶元素的大小关系以及是否满足题目一个限制需要有多少个的元素，其实这样考虑是基于贪心的思路考虑的，因为每一次决策的时候可以发现当前可以删除的情况下删除掉栈顶元素肯定是最优的，所以需要将其删除掉。好好理解一下，下面的402题是一道经典的题目。
高精度加法
445 两数相加 II（python3 翻转链表、高精度加法）
加解密思想
535 TinyURL 的加密与解密（python3 哈希表）
摩尔投票法
脑筋急转弯
空间换时间
454 四数相加 II（python3 暴力优化-空间换时间）
字符串哈希
字符串哈希的一个重要作用是能够通过O(n)的预处理，使用O(1)的时间求解出任意一段字符串的哈希值，用来快速判断两个字符串是否相等
718 最长重复子数组（python3 二分查找、字符串哈希）
二进制思想
有的时候使用二进制位（有点类似于状态压缩）来表示对应位置的0和1会非常方便，并且将状态表示为二进制之后（映射为一个十进制的数字）就可以很方便地使用位运算来判断对应的情况从而减少时间复杂度。二进制的思想有的时候是按照一位位进行枚举。
417 太平洋大西洋水流问题（python3 dfs，二进制思想）
464 我能赢吗（python3 博弈论-二进制思想、记忆化搜索）
状态压缩dp
691 贴纸拼词（python3 记忆化搜索、状态压缩dp）
正(逆)向思维
当发现问题正向解决比较难想或者是比较难处理的时候，但是反过来求解会更容易一点那么我们选择反过来求解（正难则反）
991 坏了的计算器（python3 正向思维与逆向思维、贪心）
分类讨论思想
最短路径算法
floyd算法模板（python3）求解图中任意两个顶点之间的最短距离
399 除法求值（python3 floyd算法）有的时候思维需要活跃一点因为需要将问题转换为某个已知的模型
743 网络延迟时间（python3 单源最短路径-spfa/dijkstra）这里声明列表的每一个元素为元组或者字典这样可以建无向图或者有向图
计数排序思想
347 前 K 个高频元素（python3 哈希表、计数排序思想）
设计数据结构
需要考虑数据的存储
多路归并思想
多路归并的题目一般是在若干个升序的序列中求解前k个最小的数字，经典的做法是将这些序列的第一个数字加入到堆（求解前k小元素可以使用小根堆）中，然后在循环中弹出堆顶元素将堆顶元素加入到结果集中然后加入弹出堆顶元素的下一个元素，主要是使用堆来维护前k小的数字。有的时候元素比较多对应的组合关系比较多的时候画图是一个比较好的解决方法。
373题是经典的多路归并的问题
373 查找和最小的K对数字（python3 多路归并、小根堆）
378 有序矩阵中第 K 小的元素（python3 多路归并、二分查找）
python数据结构
感觉python提供的几个基本的数据结构都是很方便的，比如字符串（str）、元组（tuple）、列表（list）、字典（dict）、集合（set）、我们在编写程序的时候可以利用这些数据结构来帮助我们存储某些变量，并且在某些情况下能够解决其他语言数据结构存储和表达比较困难的问题（比如java表达复合的数据结构类型的时候就会有点困难），python中列表 + 元组可以将多个复合的数据类型映射到一个值中，类似于二元函数，利用列表 + 元组我们可以存储二维平面上的坐标，字典其实也可以完成类似的映射功能，列表的话就类似于动态的数组非常方便动态增加与删除元素。python中的sortedcontainers.SortedDict()可以维护插入元素是有序的。
python进制转换
下一个更大元素
类似于c++中的next_permutation的思路，求解下一个更大的元素是一个非常常见的思路，可以记住这个思路。
蓄水池抽样算法
二分图最大匹配
维护第k大(小)的值
可以看成是一个数轴，对于数轴中的数字我们分情况讨论即可，看当前的x落到哪一个区间
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
1
0- 0
已为社区贡献4条内容
所有评论(0)