刷刷我的
stash： DP 树 堆/堆排序
https://juejin.cn/post/7170873189482889223/
https://leetcode.cn/circle/discuss/tXLS3i/
贪心算法
605 种花问题 贪心在有坑就占
121 买卖股票的最佳时机 与之前的最小值比较
561 数组拆分 很容易，排序隔着找就好了
455 分发饼干 排序然后一个一个分配出去就好了
575 分糖果 比较哪个小即可
135 分发糖果 困难题，如果从最小的地方开始向两边分配那么无法覆盖所有解（可能存在多个最小值）但是也算是完成了一部分。实际上问题更复杂或者更简单？实际解法也不复杂
解法一：遍历两遍只需要同时满足两个规则：从左往右是递增序列，从右往左也都是递增序列，要同时满足两种情况，只需要取两个规则的最大值即可。
解法二：把递减视为递增序列，实际上由于要满足两个规则，实际上可以把递减序列视为递增序列从而避免从右往左便利的情况。同时由于糖果分配是递增的，所以可以不用数组来保存，直接扫描一遍即可。但是写出来有难度。
2908. 元素和最小的山形三元组 I 虽然是简单题但是如果数值范围大的话就得靠贪心解决了，和上一题方法基本类似，由于是找**最小值（就是因为这个条件所以可以贪心）**所以只需要从左往右的取最小值和从右往左的取最小值即可，最后在中间不断找到最小值即可，非常微妙。
409 最长回文串 之前做过了，不复杂，统计词频即可
621 任务调度器 并不难想到解法，每次从中挑选频数最多（因此需要多次排序）的n+1个任务组成序列即可。
179 最大数 实际上就是一个排序问题，但是还是有点复杂的。
算法的核心在于搞清楚其实列表的顺序就是拼接的顺序，所以只需要通过某种规则排序即可。对于每个可能拼接的结果，只要保证相邻的两个数的拼接结果是最大的，就可以保证最后的结果是最大的（有严格证明）。
此外可以学习一手python sorted方法的另一种自定义方式：
def do_sort(x, y):
if x+y > y+x: return -1
elif x+y < y+x: return 1
else: return 0
nums = sorted(nums, key=cmp_to_key(do_sort))
56 合并区间 排序然后贪心即可，应该是简单题（看评价好像简单困难不一）
57 插入区间 调用一下前一道题的代码即可，但是题目已经隐含排序了，所以代码中只需要把newinterval放到合适的位置即可，时间复杂度可以达到O(n)
228 汇总区间 跟前两道一样，不难
452 用最少数量的箭引爆气球 反过来求最小交集即可。
435 无重叠区间 贪心妙！找每次最小的不重合右区间即可
646 最长数对链 直接抄上一道题，无重叠区间取反即可。
48 旋转图像 顺时针旋转=水平翻转+对角线旋转
169 多数元素 多数元素大于n/2所以无论在任何时刻，遇到该数的频次-遇到其他数的频次>=0
215 数组中的第 K 个最大元素 比较重要的题，下一道题也可以用到这道题的方法，其中有两种解法：大根堆解法和快速选择解法，这两个建议都学习一下。
大根堆解法：构建大根堆，则删除的第K个元素之后堆顶就是该元素（heapq.nlargest(k, nums)[-1]）
快速选择解法：快排递归求解可知每次会有一个元素到达对应的位置，所以第N-k个位置对应第k大的数，而且每次划分不需要排序，复杂度是O(N)。
建议两个都手搓一下。
75 颜色分类 做出来倒是一点不难，但是得知道如何通过双指针解决问题。双指针也涉及到贪心的相关内容，l从左往右扫描，则1必然在右指针左，2必然在右指针右，以此规则遍历即可。
649 Dota2 参议院 题目比较复杂，但是可以有多种解法，这里使用的是循环队列的解法（但是停止条件存在问题其实），更加合理的做法是使用两个列表分别表示两个阵容的数量和对应的位置
678 有效的括号字符串 初次涉及到动态规划了，这里的解法是设置了两个变量最小open和最大open，每次遇到左括号时则最小最大均会+1，遇到右括号时最大-1（当最大小于0说明有括号超标了所以返回不有效），同时最小取0和最小-1的最大值（因为需要考虑到*的存在）。当遇到*时最小取最小-1和0的最大+1。在这种实现中最小表示最少可能的未匹配左括号数量而最大表示最多～。
420 强密码检验器 是困难题，应该有前置题目可以先做
上述的题目是数组贪心相关的，整体来说难度参差不齐。由于这方面的题目较多所以其实并没有简单的通解能够解决所有问题，通常需要分析贪心的条件（感觉可以贪就贪，咱就不证明了）。通常的解决方案有flag、双指针、双向检测最大值（对于多个条件的需要多遍遍历，寻找同时满足条件的情况即可）
53 最大子数组和 妙妙妙
134 加油站 同样妙妙妙，关键在于题目条件和合适的推理，如果gas-cost的和小于0则必然不存在对应的出发点。同时由于解唯一，所以只需要从前往后遍历，如果走不通就设置为下一个点即可，遇到的可以走到尽头的一定是可以走通的点。
581 最短无序连续子数组 首先能想到前后遍历一下，从前往后找最大，从后往前找最小即可。（虽然有思路但是写不出来的飞舞呜呜呜）
152 乘积最大子数组 最开始想着从前往后遍历，值是不断增加的所以扫描就好了，显然是错误的：[1,-2,-5,-4,3]所以还是得用正经方法（所以说这题并不是贪心可恶）。正经方法就是从前往后维护一个最大值和最小值（负数）数组，遇正继续，遇负交换，问题划分成两个子问题即可。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxv, imax, imin = -inf, 1, 1
ln = len(nums)
for i in range(ln):
if nums[i] < 0:
imax, imin = imin, imax
imax = max(imax*nums[i], nums[i])
imin = min(imin*nums[i], nums[i])
maxv = max(maxv, imax)
return maxv
子序列与贪心算法
334 递增的三元子序列 直觉上感觉好像并不能直接m1, m2 做出来，感觉得谨慎一点，但是确实可以。
376 摆动序列 这个倒是不难想，毕竟是必然递增的，所以得到差值数组即可
659 分割数组为连续子序列虽然是中等但是个人感觉已经很难了，一个有趣的点在于，由于是贪心的题目，所以正常来说的话会每次尽可能分3个或者分尽可能多（但是都不对，这两个都可以通过题目给出的例子直接反例枪毙）
题解非常简单的说明了**，如果x-1存在就接上去因为延长一个序列好于新加一个序列**，但是理解起来比较复杂，不如看这个例子：
还是贪心算法，从头扫描，如果能接着上一个序列，就在上个序列后添加当前值，如果不行，前插一行继续下一个数字。 例如 2， 3， 4， 4， 5， 5， 6 顺序如下 [[2]] [[2, 3]] [[2, 3, 4]] 4不能后接，前插一行 [[4], [2, 3, 4]] [[4, 5], [2, 3, 4]] [[4, 5], [2, 3, 4, 5]] [[4, 5, 6], [2, 3, 4, 5]] 最后比较是否所有序列长度大于等于3
虽然思想类似，但不是根据大小序一个一个递增延长的，而是遍历列表（因为列表存在重叠元素，可以依次按序往之前已经有的子序列添加了）
但是像上述例子做的话复杂度就太高了O(n^2)使用哈希表即可。剩下的就不用说了。
数字与贪心
343 整数拆分 dp划分子问题：mv = max(mv, l*what[r], r*what[l], r*l)
单调栈法
因为之前没有做过单调栈的相关问题，所以首先解释一下，单调栈是指只有当值大于当前栈顶元素时才能进栈的栈
496 下一个更大元素 I 第一眼看题目和数量空间，感觉可以O(l1*l2)秒掉，但是还是得尽可能地达到进阶的要求。单调栈的解法十分巧妙，首先由于单调栈的性质，每次进栈的时候都会把比其小的取出放入，所以不难想到，一个数下一个更大元素正好是能取出的最后一个元素，因此遍历数组得到所有数的下一个最大元素，之后查询即可。当然，题解也是非常妙的。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = {}
stack = []
for n in reversed(nums2):
while stack and n >= stack[-1]:
stack.pop()
res[n] = stack[-1] if stack else -1
stack.append(n)
return [res[n] for n in nums1]
503 下一个更大元素 II 真天才啊这做法，对于循环的题目，考虑长度加倍取模长即可，真离谱的想法
316 去除重复字母 记忆一个固定模式：
while stack and c < stack[-1]:
stack.pop()
402 移掉 K 位数字 前面的题目会了，这道就能很容易爆了
接下来三道难题果断白给
数组中的动态规划
before do it， 动态和贪心虽然学习并了解了很多遍，但是时至今日仍然是对我而言极度困难的一类题目。要想更好的理解动态规划，首先需要理解动态规划和递归的区别，显然，一个是自顶向下进行求解，而DP则是自底向上求解（实际上都可以理解成一个个分支的图后者树形），在进行求解的过程中，如果上一点的选择不会影响到之后的状态，那么这类题型就是贪心，每次选择最优解即可（虽然有时候需要严格证明），如果会影响到之后的状态，那么这类题型就是DP。也因此一般做到DP会有两种思路：拿一个数组记录所有的状态或者使用递归解法解决。但是两者都会面临状态过多的情况，因此需要使用一些手段来筛选需要的状态（感觉DP的核心就是筛选，当然，严格的证明过程也是不需要的）
虽然各种题有各种讨巧的做法，但是DP总归是两步组成的：状态转移、筛选状态。剩下的就要靠练习了感觉。
509 斐波那契数 没想到吧，我也是dp
198 打家劫舍 第一个题解确实详细也几乎是DP的启蒙，建议全文背诵（至于精简版写法，暂且无所谓了）
70 爬楼梯 挺简单的但是刷不出来，可以正推推导式。动态规划多少跟递归有点关系，但是使用常规递归会导致计算量超标和栈深度过高，所以还是使用dp合理一点
338 比特位计数 O(nlogn)是不需要使用dp的，O(n)是需要使用dp算法的。O(n)方案中的的最高位方法挺妙的，使用 i&(i-1)==0来判断是否是正好2的幂数，如果是的话为1，否则就是最高位的数字加上去即可，挺妙的。
55 跳跃游戏 取能走的最远和之前预期的能走的最远的最大值即可。
45 跳跃游戏 II 和之前的题相差倒是不大，首先从一个点出发可以到达的所有点都是下一个起跳点，比较这些起跳点中可以跳的最远的即可。从一个起跳点开始到达之前的边界之前的最大值。之后继续跳到下一点。
213 打家劫舍 II 两轮打家劫舍
650 只有两个键的键盘 就是利用最小公倍数的思路即可，可以化简为递归子问题：找n的最小公倍数$f(n) = f(n/k) + 2$
91 解码方法 想法是对的，就是没有写出来呜呜呜。思路有点像爬楼梯，保存一下之前的状态并求和即可。当然同样可以用两个变量来减少时间复杂度。
复杂的dp还是算了
264 丑数 II 实际上就是每次找三个因数中最小的不断递增即可。
子数组、子序列中的动态规划
689 三个无重叠子数组的最大和 每日一题，一眼动态规划，关键在于如何设置递归子问题。正解是分成两种情况：1、删除元素2、不需要删除元素：
413 等差数列划分 骗骗骗，可以不用dp做
368 最大整除子集 想法有了但是做不出来了，脑子好痒
背包问题
494 目标和 妙妙妙，非常妙的题目，假设所有取正的数和为p，取负的数为q，则有q=s-p，则target t=p-(s-p)所以p=(s+t)/2从而把问题转化为了从中挑选数字使得p=(s+t)/2。接下来就是0-1背包问题了。
2742. 给墙壁刷油漆 每日一题做到了，完全不会抽象题目，还是有待提升。题目可能忘记说是顺序进行了，因此实际上不是贪心问题，那么问题就是从前往后过程中哪堵墙需要付费，哪堵墙需要免费（实际上就是个两种状态的转移过程）。举个例子，对于第n-1堵墙，如果付费第n-1，那么问题就是刷n-2墙之后付费时间之和为time[n-1]、免费时间之和为0的最小开销。如果免费，那么问题就是刷n-2墙之后付费时间之和为0，免费时间之和为1的最小开销。所以递归式：
- 付费：dfs(i,j) = dfs(i-1,j+time[i]) + cost[i]
- 免费：dfs(i,j) = dfs(i-1,j-1)
求两者最小值即可。
矩阵中的动态规划
动态规划与字符串匹配
状态压缩动态规划
区间中的动态规划
树形 dp
数位 dp
数组
上面的题目都是简单的，显然排序一下会简单很多，但是复杂度就会到达O(nlogn)所以一般尽可能的还是会考虑O(n)的算法。由于复杂度不看系数所以多遍历几次也是可以的（多用几次max,min也没啥问题）
645 错误的集合 虽然有常规思路但是如果用数学方法求解还是有意思的
697 数组的度 存一下就好
448 找到所有数组中消失的数字 中等但是很简单
442 数组中重复的数据 用O(n)的空间很简单，但是O(1)就很讨巧了
41 缺失的第一个正数 原地哈希，和上一道题一样的方案
274 H 指数 如果不使用O(n)做的话也不难
80. 删除有序数组中的重复项 II 用双指针轻松拿下（也可以考虑使用哈希表来保存，但是这样就需要额外的时间复杂度了）
上面的题目涉及到频数，出现的计算，因此大概率是需要使用数组桶的方式进行求解，对于python来说可以使用一些简单的方法来统计频率或者统计位置
# frequency
from collections import Counter
busket = Counter(list)
# posistion
for i,j in enumerage(list):
if lpos.get(j, None) if None:
lpos[j] = [i]
else:
lpos[j].append(i)
453 最小操作次数使数组元素相等 求对立事件！
665 非递减数列 不难也还行
283 移动零 不难
上面的涉及到简单的数组移动，但是一般会有原地狡猾的呢限制来提高难度，所以可以使用诸如双指针等方法进行交换来实现原地置换
118 杨辉三角 确实不难
119 杨辉三角 II 是前面的升级版，要求找到规律了
661 图片平滑器 手写滤波器，但是没有特殊的地方，复杂度会比较高
598 范围求和 II 小贪心！
419 甲板上的战舰 是图论部分的问题，如果不考虑挑战的话其实并不复杂（毕竟不能修改棋盘），可以先浅浅解决一下
上述题目为二维数组相关问题，目前来看难度还不大，主要还是熟练二维数组操作技巧。但是同时二维数组也会比较频繁的和图论等问题结合，因此后续还会出现很多类似题目。（比如419题）
189 轮转数组 用python可太容易了
栈和递归 (暂时完成？)
用栈访问最后若干元素
71 简化路径 中等题但是比上一道还简单
388 文件的最长绝对路径 可以不用栈做的其实
栈与计算器
150 逆波兰表达式求值 很基础的栈应用了已经
227 基本计算器 II 稍微有点繁琐了已经
224 基本计算器 已经繁琐到没必要做了
栈与括号匹配
20 有效的括号 ez
636 函数的独占时间 在入栈的时候顺便多处理一下就好了，也挺好的题目
32 最长有效括号 栈+DP，有点难了属于是，自己的方法考虑不到嵌套的情况，建议参考题解二进行快乐的理解记忆
递归
递归在dfs的时候还会好好学习的，但是核心在于入栈和出栈之前进行一手判断操作
385 迷你语法分析器 核心其实是解析器
341 扁平化嵌套列表迭代器 妙妙妙
394 字符串解码 递归就好了，但是写不出来
树
树与递归
差点难到哥们
563 二叉树的坡度 天才题解，同时也提供了一种很舒服的递归条件：
class Solution:
def findTilt(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0, 0
l_sum, l_diff = dfs(node.left)
r_sum, r_diff = dfs(node.right)
return l_sum + r_sum + node.val, l_diff + r_diff + abs(r_sum - l_sum)
return dfs(root)[1]
树的层次遍历
树的前序遍历
树的前序序列化
树的后序遍历
树的中序遍历与二叉搜索树
重构二叉树
二叉树的展开
最近公共祖先
Morris 中序遍历
四叉树
What’s more
28. 找出字符串中第一个匹配项的下标 妙啊，虽然能想到使用递归加$(a)b$方式添加有效字符串，但是确实写不出来。
class Solution:
@lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]
res = []
for i in range(n):
for l in self.generateParenthesis(i):
for r in self.generateParenthesis(n-1-i):
res.append("({}){}".format(l, r))
return res
这里还涉及到了一个装饰器：lru_cache(None)
| Strategy | Eviction policy | Use case |
|---|---|---|
| First-In/First-Out (FIFO) | Evicts the oldest of the entries | Newer entries are most likely to be reused |
| Last-In/First-Out (LIFO) | Evicts the latest of the entries | Older entries are most likely to be reused |
| Least Recently Used (LRU) | Evicts the least recently used entry | Recently used entries are most likely to be reused |
| Most Recently Used (MRU) | Evicts the most recently used entry | Least recently used entries are most likely to be reused |
| Least Frequently Used (LFU) | Evicts the least often accessed entry | Entries with a lot of hits are more likely to be reused |
如上表显示不同情况下需要使用的情况
42. 接雨水 非常经典的题，左右各扫一遍找最小即可。（本来以为很难结果秒了）
478. 在圆内随机生成点 拒绝采样，这个很微妙！细节在于完全随机（所以是均匀的），考虑到随机选择极坐标是不均匀的（点会集中在圆心），合格的做法应该是随机选择半径的平方！（因为圆内的面积和半径的平方成正比）
2850. 将石头分散到网格图的最少移动次数 每日一题，看起来并不复杂实际上也确实，但是关键在于如何实现枚举，这里使用了一个python itertools中的permutations方法直接生成所有枚举之后遍历即可。