algorithm-Brush

逆波兰，栈

leetcode 224

1. 逆波兰法。
   1. 构造逆波兰表达式。中缀转后缀, ( 入栈，) 弹栈到 (, + 弹栈所有高优先级 - 后入栈。
   2. 后缀计算值。 数字入栈，符号弹栈俩元素或单元素，计算值入栈，返回最后栈顶。
2. 栈记录每个值的正负号。由于所有计算都是加减，所以很简单。记录每个数字对应的符号。（注意括号）。

leetcode 227

1. 同 224 。没 (,),但有 *,/。我们需要构造优先级，*,/ 优先级相同，+,- 优先级相同，弹栈弹更高优先级（包括同优先级）。一发过，牛逼。

leetcode 394

1. 数字以字符串形式入栈，出栈再计算。

字典树

leetcode 677

1. 构造字典树，每个节点存放值，插入重复元素需要为之前插入的树上所有节点更新值。

树的遍历

leetcode 297

1. 序列化：层序遍历。反序列化：层序遍历重建。

leetcode 440

1. 字典序抽象出十叉树，计算每个前缀数字的节点数，通过数学优化减少遍历。

leetcode 99

1. 中序遍歷構造遞增序列，然後尋找一個或者兩個遞減的座標，進行交換。

leetcode 958

1. 层序遍历，完美二叉树的节点坐标特性。

offer36

1. 平衡树转双链表，中序遍历。

lc 230

1. 统计中序遍历第 k 个节点。

lc 103

1. 层序遍历，先左后右。。。方法上注意每次都把本层的节点一次遍历完。

lc 98

1. 验证树是否是二叉搜索树，中序遍历。

lc 695

1. 层序遍历找一层中最大宽度，unsigned long long 2^64-1。

lc 114

1. 后序遍历

lc 106

1. 知道中序和后序，构造二叉树。通过后序找到根节点，然后构造左右子树。

树的删除

lc 450

1. 平衡二叉树 删除节点，并旋转。

双指针

leetcode 295

1. 双指针，左右指针调整中位数，区分奇数偶数。（multimap 重复元素插入和搜索特征）
2. 一个大堆，一个小堆。

leetcode 135

1. 算是双指针...有点滑动窗口的感觉。线性扫描。
2. 好像还有一种双向扫描的方法。

leetcode 88 有序序列合并。倒过来，双指针。

lc 11 看上去好像是接水的单调栈，实际上是左右俩指针向内收缩，的确难想到。

二分

leetcode 1095

1. “三个二分”，找最大值，搜左边，左边搜不到搜右边。二分注意从大到小还是从小到小，以及边界，以及退出时的判断。

leetcode 154

1. 旋转数组找最小数，利用最小值肯定在左右中间找，逐渐缩小二分查找区间。最右边数的值作为区分最小数在哪一边的标准。

leetcode 154

1. 俩有序数组找中值，巧借坐标为 k/2 -1 的数据进行范围缩放。

leetcode 72

1. 二维数组转一维二分。

leetcode 81

1. 旋转数组找目标，通过比较最左数，目标数，中间值缩小范围，这里遇到重复则退化为遍历。。。

leetcode 162

1. 找极大值。

leetcode 275

1. 找 max(len - x >= f(x) ? f(x) : len -x > f(x-1) ? len - x : none)

leetcode 240

1. 横坐标和纵坐标分别二分排除非目标区域。 (利用 upper_bound)

lc 16

1. 三数字和最接近的数，先排序，后遍历前两个数字，最后二分找差距最小最接近的第三个数。

动态规划

lc 70

1. 简单爬楼梯。

leetcode 17.24

1. 从一维怎么求最大区间去思考。二维需要先固定上边，再固定左边，然后移动下边和右边，动态规划更新最值。

leetcode 887 扔鸡蛋

1. 巧妙解法 抽象出 鸡蛋数，机会数量 两个因子计算可以求解的楼层数，而不是死纠 鸡蛋数, 楼层数 算最大机会次数。
2. 我不会，蛋我大受震撼

leetcode 10

1. 正则表达式，如果当前匹配到 * 向左看前一个字符串是否匹配，若匹配，状态如何转移，若不匹配，状态如何转移。（将 x*看成一个整体） leetcode 44
2. 和上题类似。匹配到 * 等价于 使用 * 和不使用 * 的两种情况。

leetcode 516 区域动态规划，删除某几个字符求最大回文子串长度。根据区间首尾字符是否相同，分为两种情况决定区间长度最大值的计算方式。 leetcode 1312 区域动态规划，添加最少的字符数量形成回文子串。根据区间首尾字符是否相同，分为两种情况决定需要添加的字符数量。

leetcode 115 一般来说，这种字符串匹配的 dp 问题需要通过 增删一个字符 的逻辑构建 状态转移方程，想到及万岁。

leetcode 354 两维 最大升序序列长度，暴力 dp O(N^2), 通过构建递增序列，并二分寻找修改点的方式可以降低到 O(logN)。 需要对其中一维升序排序，另一维降序排序，来迎合两维皆需要升序的需要。

leetcode 188

至于状态是什么：1. 天数 i 2. 交易数 j 3. 当前是否有股票（有些难想）用数组 0 | 1 表示。 当然 f(x) 是最大利润。注意要考虑交易数为 0 的情况 所以数组大小应该是 j + 1。

买卖股票, 初始边界状态的建立有些繁琐, (因为那些非正常情况,我们不是清 0 而是置 INT_MIN), 然后注意新的一轮买股票算一笔交易,而不是卖的时候,否则转移方程会出错。

leetcode 312 比较难以想象的转移方程，正向思考状态转移可能无果，因为发生的变化没有一定的规律，但是反向思考，在一定的范围内每次添加一个数字（选择任一个位置添加），那么这个范围就会被缩小到左边界到添加的数坐标这个区间，以及添加的数字到右边界的区间。然后初始状态就是这个区间的长度大于 0。将这俩个区间的求出最大值相加加上添加这个数带来的收益，得出整个区间的最大值。然后定义需求是求最大区间 dp[0][len + 1] 的最大值，根据状态转移方程的方向确定如何遍历，，，再考虑一些边界，，，最终得出结果。

leetcode 152 看出来规律是，当前数字及之前一些数字连在一起的最大乘积是 选取当前数字，或者当前数字是正数时和前一个数字的最大值相乘，或负数和前一个数字的最小值（负数）相乘。

1. max_val[i] = max(nums[i], nums[i] * max_val[i-1], nums[i] * min_val[i-1])
2. min_val[i] = min(nums[i], nums[i] * max_val[i-1], nums[i] * min_val[i-1])

leetcode 221 全 1 正方形找最大面积，观察右下角 nums[i][j]，它能构成最大边长的正方形得满足：

1. nums[i][j] == 1
2. 包含 nums[i][j] 的最大全 1 正方形肯定是 nums[i-1][j]，nums[i][j-1]，nums[i-1][j-1] 三个位置的最大边长最小值 + 1。

leetcode 518 背包问题，自变量用总金额，因变量用方法数，可以想到建立动态规划方程，当前状态等于一些子状态的集合，也就是考虑更少的硬币数能否实现，，，但是可能会出现重叠，，，因此答案中，先遍历硬币，再遍历金额，，，这可以保证每次只对之前遍历过的那些硬币大小和当前硬币大小进行组合，，，避免重叠。

leeetcode 91 leeetcode 139

1. 字符串匹配 dp[i] = dp[j] + check(s[j..i-1]) 可以用字典树。

leetcode 343

1. 数学，找规律 dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]))。

leetcode 673 最长递增子序列的个数，dp[index] 保存到 index 的最长递增序列长度，cnt[index] 保存到 index 的最长递增序列个数。 转移方程 dp[i] = max(dp[j]) + 1，cnt[i] = cnt[j] + 1，j < i，nums[j] < nums[i]。

leetcode 300 最长递增子序列的长度，，，简单做法就是上面 max(dp[i])。更优化的方法是贪心 + 二分，构建单调序列 d[i] 代表长度为 i 的序列的最小结尾值。 如果比当前序列结尾值大，插入到结尾，否则通过二分查找第一个比 d[i] 小的 d[k] 然后更新最小值 d[k+1] = d[i]。最后看递增序列的长度。 贪心体现在让单调递增序列中值尽可能的小。

leetcode 264 第 n 个 2^x * 3^y * 5^z。难想的是 dp[i] = min(dp[p1] * 2, dp[p2] * 3, dp[p3] * 5);

leetcode 494 找规律，0/1背包，<最大坐标 i , 总和 j> -> 方案数量 dp[i][j], dp[i][j] = dp[i-1][j] + dp[i-1][j- nums[i - 1]]，将选取当前坐标数字和不选取当前坐标数字的方案数量相加。

leetcode 279 简单0/1背包。 leetcode 647 回文串，dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];。

douyin_back_to_origin

1. 动归 + 余数

滑动窗口

leetcode 209

1. 寻找和大于某值的最短区间长度。右扩左缩。

offer59-I

1. 選找每個固定長度區間的最大值，反正比較難想的是它的優先隊列彈出範圍外的最大的元素的策略（可以說是延時淘汰）。

leetcode 480

1. 中位數查找，區分 k % 2 的兩種情況，通過修正 multiset 迭代器 mid, left, right 來求中間值，方便的做法是 multiset 保存 pair<long, int>value_index 減少特殊情況。

深度优先搜索

679.24

1. 求二十四点，dfs 回溯。

leetcode 698

1. 排序，dfs，剪枝。

leetcode 1339

1. dfs + 树后续遍历

lc 39

1. 任意个选定数字的和为一个目标值， 类似完全背包，但是似乎用 dfs 回溯去做，还得考虑如何去除重复。

lc 79

1. 简单矩阵找字符串。

lc 40

1. 感觉像是多重背包，回溯可以做。

优先队列

c++ 优先队列的比较器特征：默认 less<> 大堆顶，自己写的 Cmp 如果是写成 left < right 仍然是大堆顶顺序。 中间的存储容器用 vector 或者 deque 均可以，但是 vector 更稳定？

leetcode 60

1. 全排列 算 k/(n-m)! and k%(n-m)!, k = k%(n-m)!... 优先队列不过是为了快速取当前应该拿出的值。

leetcode 692

1. 根据元素出现的次数和元素的字典序排列决定优先队列的顺序，然后找 TopK。
2. nth_element + sort 快速选择。

leetcode 407

1. 3D 接雨水。所有边境点添加到墙高度优先队列中，从边境最小点遍历四个方向，如果下一个点没有被访问而且比它小，则可以装水（同时这个点记录已被访问），否则不装水。 之后把这个点也放到墙高度优先队列中。类似迪杰斯特拉算法。

单调队列

leetcode 862

1. 构造前缀和，求最短区间和 >= k （可能存在负数）。通过构造单调队列减去那些只会更长的区间，再寻找满足条件的最短区间长。
2. 暴力 O(N^2)。会超时。

归并排序

leetcode 315

1. 看上去很简单，找右边小于它的数，事实上难的一批。不能用 dp...最后想到的方案是插入排序但会超时，n2log(n)。使用归并排序，复杂度 nlogn, 我写的一直有些bug,,, 元素的坐标和元素绑定在一起可以省去很多麻烦。inplace_merge(first,mid,end) 应该是 stl 库自带的归并接口，代表含义是 [first,mid) 已经排序 和 [mid,end)已经排序，将它们合并。

基数排序

leetcode 164 从最小位到最大位，依次放到 0 到 9 的数组中。注意基数排序的时间复杂度 O(nk), k 是最大位数。比如整数 2 ^ 31 - 1 ，则 k = 31; 所以 O(nk) 不一定比 O(nlog(n)) 小。

堆排序

lc 912 模板练手。。。似乎可以用来做最大 K 问题。

設計題

leetcode 895 頻率棧，通過倆 hashmap 來分別存放 {count, vals[]} 和 {val, count}。難以想像的是它在添加元素的時候不是 update {count, val} -> {count + 1, val} 而是直接添加 {count + 1, val}。

leetcode 1206 跳表 增删查。主要需要想到如何去向左和向下走的过程。容易出 BUG。在初始化一个节点时随机高度，在插入时为这些层设置它们对应的 prev 节点。 删除时策略删除最上层先找到节点，需要考虑到多个相同值的节点如何保证删除的唯一性。

大数题

leetcode 43 找规律，结果的第 n 位 是 所有的 乘数1 的第 k 位 乘以 乘数2 的第 n - k 位 加上进位。

前缀和

leetcode 523 区间整除。算两个前缀和余数是否相同就好了。

leetcode 230 区间差 k。遍历前缀和的时候顺便去看 map 中有没有和自己相差 k 的前缀和。

链表

leetcode 24

1. 两两旋转 offer36
2. 平衡树转双链表，中序遍历。

lc 61

1. 整体右旋 k 。

lc 142

1. 找到链表上出现环的第一个点。

lc 143

1. 将链表后半部分倒着插入到前半部分。

lc 82

1. 链表去除所有出现二次以上的节点。

lc 138

1. 深拷贝链表，，先拷贝到链表中再分离，三次遍历。

lc 912

1. 链表排序，归并排序。

lc 86

1. 小于目标的节点放到大于等于目标的节点前面。尾插。

lc 445

1. 链表大数相加。栈。

数学题

lc 54

1. 旋转遍历二维数组，抠细节。 lc 59 同上遍历二维数组填写数字。

lc 31

1. 寻找组合中的下一个组合。

lc 498

1. 斜边坐标和相同。

lc 384

1. 洗牌算法，重在交换。

offer 45

1. 拼接数字最小。通过构造比较函数，让 s1+s2 <s2+s1。

rep9.36

1. 36 进制大数相加。

位图

lc 287

1. 找重复数字。注意 2^remain 是 1 << remain 而不是 remain << 1。

图论

lc 695

1. DAG 判环。拓扑排序，从入度为0开始，到找不到入度为0结束。

TopK

lc 347

1. 寻找最大频率数字，哈希表，堆排序。

字符串

678

1. (*) 括号匹配。贪心，构建最大，最小匹配数量。