LeetCode Rush

本文用于记录在算法题目中使用的技巧或者方法，以备查阅。

链表问题

• 使用双指针可以解决找固定位置相关问题，环形链表问题，相交链表问题，旋转链表问题
• 尝试设置 dummyHead 节点，用于处理特殊情况
• 只知道要删除的节点，实现该节点的删除
• 头插法和尾插法的不同点，可以使用头插法实现链表的反转，也可以直接使用迭代方法
• 链表反转问题：全部反转（迭代，递归，头插法），部分反转（递归，迭代），k 个一组翻转（递归，迭代）
• 合并链表问题：合并两个链表，合并 k 个链表
• 判断回文链表：使用额外数据结构，反转后半部分的链表再进行比较，使用后序遍历来比较（链表只存在前序和后序）

二叉树问题

• 二叉树遍历分为 BFS（层次遍历），DFS（前序，中序，后序遍历）
• 在解决二叉树的问题过程中，通常和其递归遍历框架存在关系，而在编写递归算法中，最关键的是要明确函数的定义是什么，然后使用这个递归推到最终结果，而不要跳入到递归的细节中去
• 递归解决二叉树问题：左右翻转二叉树，二叉树展开为链表（先序），填充每个节点的下一个右侧节点指针（注意不同父节点下的关系），将数组构建为最大二叉树，二叉树最大深度，判断是否存在根节点到叶节点路径总和等于目标值，统计二叉树中某条路径（不要求从根节点开始，到叶子节点结束）和为目标值的总的数目
• 使用前序－中序构造二叉树问题，使用后序－中序构造二叉树问题：关键点在于找到根结点，然后递归构建左右子树
• 二叉树的最近公共祖先：维护每个节点的父节点，或者是使用递归查找（注意结束条件）
• 二叉树的序列化和反序列化：使用前序遍历，后序遍历或者层次遍历，不过也需要记录空节点，不可仅仅使用中序遍历
• 寻找重复的子树：关键在于如何将二叉树序列化起来，然后和已经存在的二叉树进行比较，看看是否重复
• 二叉搜索树的中序遍历结果是有序的，可以解决：BST 第 K 小的元素，BST 转化为累加树
• 二叉搜索树的基本操作：删除，插入，搜索，验证 BST（记录当前树范围）
• 递归解决二叉搜索树问题：不同的二叉搜索树数量（节点值 1 到 n），不同的二叉搜索树所有种类（节点值 1 到 n）
• 二叉树中二叉搜索子树的最大键值和：使用后序遍历可以减少时间复杂度，因为当前节点所做的事情依赖于左右子树，涉及到 BST 的验证
• 扁平化嵌套列表迭代器：将其当做是一个多叉树进行遍历保存，使用懒加载模式
• 完全二叉树的节点数：考虑左右二叉树是否为满二叉树，分解问题，减少时间复杂度
• 恢复二叉搜索树：中序遍历有序性，找出两个交换的节点；使用莫里斯遍历
• 字典序的第 K 小数字：构建一个 10 叉树，根据 cur，next 变量统计当前统计过的数字，和 k 进行比较

图问题

• 图中所有可能路径：涉及到图遍历框架，注意和回溯算法的区别，图遍历中 visited 不会重新被设置为 false
• 拓扑排序：使用 BFS 算法，构建入度数组，之后将入度为 0 的节点入队，使用 DFS 算法，后序遍历并且反转即为拓扑序
• 判断图中是否存在环：利用拓扑排序判断，或者是深度优先遍历，后者还可以获得当前的环节点
• Dijkstra 算法：用于查找图中某个节点到其他所有节点的最短路径（不含有负权重），可使用优先队列实现贪心特性，实际上可以扩展成在图中求最值的算法，相关问题如网络延迟时间，概率最大的路径，最小体力消耗路径
• 找到最终的安全状态：找到所有路径通向终端节点的安全节点，可以使用深度优先搜索 + 三色标记法，也可以使用拓扑排序，先反转图，再使用入度统计信息
• 可能的二分法：给定一组节点，其中规定那些边不能存在，判断能否组成二分图，可以使用 dfs 进行着色，不能存在的边对应的两个端点是不同的颜色
• 素数伴侣：统计奇数与偶数和中能组成素数的组数，可以考虑二分图的匈牙利算法，其遵循先到先得，能让则让的思路；或者建立图，每次选择出度入度和最小的节点剔除，进行统计即可

数组和字符串问题

• 田忌赛马算法决策：比不过的时候选择最差的元素进行比较，如优势洗牌

• 二分搜索模板：基本的二分搜索，寻找左侧边界的二分搜索，寻找右侧边界的二分搜索，使用闭区间需要注意索引溢出的问题

• 二分搜索推广：找到 x，f(x) 和 target，然后套用二分搜索模板即可，相关问题有珂珂吃香蕉，在 D 天内送达包裹的能力，分割数组的最大值，寻找两个正序数组的中位数

• 双指针技巧：快慢指针通常用于解决链表中的问题，如判定环形链表以及环的起始位置，寻找中点，倒数第 n 个元素；左右指针通常用于解决二分搜索，两数之和，反转数组，滑动窗口，寻找旋转排序数组中的最小值，通过删除字母匹配到字典里最长单词， 寻找峰值等算法

• 滑动窗口模板：维护一个窗口，不断滑动并且更新数据结构，相关问题如最小覆盖子串，字符串排列子串判定，找所有字母的异位词，最长无重复子串，长度最小的子数组，串联所有单词的子串（相同长度），最大连续 1 的个数，考试的最大困扰度

• 常数时间获取随机数问题：需要使用数组来存储数据，相关问题如常数时间插入、删除和获取随机元素，黑名单中的随机数等

• 单调栈使用技巧：不同字符的某个子序列，不同字符的最小子序列等

• 双指针技巧：删除排序数组中的重复项，删除排序链表中的重复元素，移除元素，移动零，合并区间，最长回文子串等

• 两数之和问题：借助哈希表或者排序实现，如找到和为 target 的两个数，TwoSum 数据结构设计，推广问题如三数之和，四数之和，以及 nSum 问题

• 数组前缀和技巧：寻找数组左右和相等的中心索引，杨辉三角II

• 二维数组相关：旋转矩阵，对角线遍历

• 快速排序：基础的快速排序很容易就达到最坏时间复杂度，可以使用随机选取来消除已排序数组的影响，使用三路快排来消除大量重复元素的影响，主要注意 partition 方法实现

• 整数转罗马数字：数组统计，再使用贪心算法

• 柱状图中最大的矩形：使用单调栈和哨兵，在弹出栈顶元素的时候已经可以得到左右边界，可以计算出来面积；或者使用单调栈求出 i 位置左右最近的小于 heights[i] 的元素索引，再进行一次遍历即可；相关问题如最大矩形

• 最大矩形：先统计左边 1 的个数，再使用直方图面积法求解

• 课程表 III：给定 [dur, ddl]，求能修读的最大课程数目，使用贪心算法实现

• 最长重复子串：使用字符串哈希来检查相同的字符串是否存在，提高效率

• 寻找最近的回文数：给定一个数字，返回和其相差绝对值最小的回文数，附近回文数主要分为 5 类

• 最长连续序列：返回未排序数组中的最长连续序列的值，使用哈希表可以降低至 O(n)

• 下一个更大元素 III：给定一个数 n，返回其数字重排后下一个最小的大于 n 的数，通过逆序对解决

• 多数元素：给定数组，找出其中的出现次数超过 n / k 的数目，可以使用投票法，分三类讨论

• 寻找重复数：在一个长度为 n + 1 的数组中，其元素都在 [1, n]，使用原地算法，可以通过索引负数标记

• 环形数组是否存在循环：在数组中判断是否存在循环，同样通过快慢指针解决

• 数组嵌套：在 [0..n-1] 中找到最大循环集合，注意只可能存在不相交的循环，因为每个元素都不相同

• 任务调度器：给定任务，在冷却期间不能运行相同任务，使用数学思想进行计算，关注最大执行次数的任务

• 在 LR 字符串中交换相邻字符：能否在 LR 规则下进行字符串转换，看源和目的字符串中 L 和 R 的位置即可

• 子数组按位或操作：返回可能或操作的结果数量，注意使用剪枝防止超时，整个数组或操作结果作为哨兵

• 漂亮数组：构造数组，使得不存在 num[j] * 2 = num[i] + nums[k]，使用分治法

• 坏了的计算器：采用逆向思维，才能贪心地执行除法，从而得到最小的转移步数

• 优美的排列 II：n 个元素的数组，使得数组相邻元素之差只能存在 k 个不同值，考虑大小交错排列法

• 加油站：只需要从不能通过的地方重新开始测试即可

• 只出现一次的数字：其他数字重复出现多次，只有一个数字只出现一次，使用位统计方法

• 最大数：两个数据排序关系只需要看两个数组组成不同数字大小即可

• Excel 表列名称：实际上是偏移为 [1..26] 的进制转换问题，每次取余前先自减取得偏移为 0 的数字即可

• 超级丑数：找到第 n 个丑数，丑数序列乘以质数列表还是丑数序列，可以采用多指针的方式解决

• 摆动排序 II：可以参考桶排序，来构造摆动数组

• 递增的三元子序列：通过记录最小和次小值，再判断是否存在数字大于次小值即可

• 水壶问题：可以使用模拟的方法来进行搜索，或者直接使用数学公式

• 消除游戏：可以考虑约瑟夫环例子推出最终结果

• 有序矩阵中第 K 小的元素：可以使用优先队列进行归并，也可以使用二分法

• 汉明距离总和：统计每个位上 1 的数目，再进行数学计算即可

• 日程表安排 II：可以使用差分数组，也可以使用线段树

• 132 模式：直接遍历会超时，可以考虑使用数据结构维护左右两边的数据信息，再进行一次遍历即可

• 替换后的最长重复字符：以每个字符作为结尾字符，满足最左边的索引，找到最大区间即可

• 重建序列：根据给定的子序列重新构建一个序列，使用拓扑排序即可

• 到达终点数字：问题可以转化为给定数字，添加正负号凑出目标值问题，根据差值进行判断

• 统计子串中的唯一字符：可以转化为每个字符在所有子串中的贡献度，根据该字符前后相同字符位置可以确定

• 回文素数：根据现有的数找到下一个回文数，然后查看是否是素数，或者利用偶数长度的回文数只有 11 性质

• 索引处的解码字符串：逆向思考，先求出整个字符串的长度，如果字符串重复多次组成，那么索引取模结果相同

• 分发糖果：分发糖果使得相邻得分高的人得到更多糖果，可以采取左右两遍遍历的方法，并取最大值

• 环形子数组的最大和：最大和只可能出现在中间位置，或者头尾两端，前者直接求子数组最大值，后者使用数据总和减去子数据最小值即可，两者取较大值即可

• 字符串轮转：判断 s2 是否是由 s1 轮转得到的，碰到环形数组问题，直接原数据复制成两倍即可

• 使数组相等的最小开销：此时开销对应的数值相当于是数组中有多少个相同元素，取加权中位数即可

• 和至少为 K 的最短子数组：使用前缀和与单调队列即可，两种情况可以让队列进行优化

• 全局倒置与局部倒置：只需要检测是否存在非局部倒置即可，维护一个 max 前缀数组即可

• 第 N 个神奇数字：使用容斥原理和二分查找快速查找对应元素，lcm 和 gcd 算法

• 通过最少操作次数使数组的和相等：数据大小限制在 [1-6]，统计每次最大变化量，使得差值最快减小到小于等于 0 即可，贪心思想

• 替换子串得到平衡字符串：滑动窗口，考虑窗口外的字符个数限制需要小于 n / 4 即可

• 检查「好数组」：要使得其中一组数乘以某个数得到 1，则它们的最大公约数必须是 1，参考裴蜀定理

• 格雷码：求某个二进制对应的格雷码通过 x ^ (x >> 1) 即可，按照原来二进制排列，相邻格雷码只有一个 bit 不同

• 滑动窗口最大值：可以考虑使用最大堆实现，也可以使用单调队列实现

• 使数组和能被 P 整除：可以考虑使用前缀和与哈希表，找到子数组，使得 sum[i..j] 模 P 等于 sum[i..j] 模 P

• 统计中位数为 K 的子数组：使用前缀和进行解决，只需要找到对应的 sum[i..j] = 0 或者 1 就行

• 四则运算：要求支持包含 + - * / ( ) 的表达式计算，可以使用递归和双栈方法进行解析计算

• 移动石子直到连续 II：每次移动只能移动端点石子，最大移动可以看左侧或者右侧 n - 1 个节点的空位个数大小；对于最小移动次数，可以使用双指针查看 n 个位置中最多有多少个石子

• 段式回文：可以采用贪心和递归的思想，但是需要理解为什么可以贪心

• 子数组最大平均数 II：统计子数组中长度至少为 L 的最大平均数，可以采用二分法进行解决，在判断时需要考虑是否存在子数组和大于之前前缀和的最小值，即 sum[i] - minPre 的值是否大于 0，相关问题有几何平均值最大的子数组，取对数即可转化为上述问题

• 你可以安排的最多任务数目：tasks 和 workers 数组中最大 k 个 worker 完成最小的 k 个 task，因此可以转换为二分法解决

• 找出数组的第 K 大和：首先统计所有非负整数之和，然后将负数取反，接着排序，排序后可以减去当前索引值，也可以减去当前索引值并且加上之前的索引值，维护最大堆执行 k 次即可

• 和为 K 的子数组：找到区间和为 K 的连续子数组个数，包含正负数。可以采用前缀和来解决，但实际上，sum[i..j] 等于 sum[..j] - sum[..i-1]，我们只需要建立一个前缀和映射表即可，注意需要提前 map.put(0, 1)；相关问题如路径总和 III

• 最强祝福力场：需要注意的是，最大强度必须在重叠的相交点上，而不是矩形的四个角，先求出所有矩形左下顶点，然后两层循环即可，原理是相交矩形左下角点必定是所有矩形中横纵坐标之一；或者可以先统计出所有的相交点，然后统计相交点在所有矩形中的最大个数即可；或者；另外一种思路便是使用离散化和二维差分数组，离散化的目的是降低二维差分数组维数，注意二维差分数组的构建和恢复过程

• 按字典序排在最后的子串：使用双指针，比较相同长度下的字符串，如果不同则可以移动双指针其中的一个即可

• 数组中不等三元组的数目：考虑某个元素，将其当作三元组中间元素，那么只需要统计小于的中原元素的个数，大于中间元素的个数即可，可以使用排序或者哈希表

• 最长合法子字符串的长度：找到不在 forbidden 列表中的最大子字符串的长度，考虑 s[left..right]，如果出现被禁止字符串的情况，则此时 left = i + 1（s[i..right] 是被禁止字符串），该问题的关键在于从 right 开始考虑，而不是从 left 考虑，因为在移动 right 的过程中，新增的字符串以 s[right] 结尾，因此需要从 right 开始考虑

数据结构设计问题

• 并查集算法：解决图论中动态连通性的问题，优化技巧有增加秩，路径压缩，涉及到等价关系的算法可以考虑该数据结构，如等式方程的可满足性

• LRU 缓存算法：按照访问顺序的淘汰策略，使用 LinkedHashMap 数据结构即可实现，注意其遍历顺序

• LFU 缓存算法：按照访问频次的淘汰策略，如果最低访问频次有多个，淘汰最旧的数据，使用 HashMap，借助 LinkedHashSet 实现，注意其遍历顺序

• 最大频率栈：每次 pop 掉频率最大的数据，使用 HashMap 结构实现快速索引

• 数据流的中位数：使用两个优先级队列，并保持两个队列间数字的大小顺序

• 合并 k 个有序链表：使用优先级队列实现，如返回朋友圈前 10 条动态，第 K 个最小的素数分数

• 单调栈：指每次在 push 的时候，保持栈中的大小顺序，用于处理 Next Greater Element 问题，如下一个更大元素 I，下一个更大元素 II，每日温度等

• 单调队列：每次添加元素的时候，保持队列中的大小顺序，用于处理和滑动窗口相关的问题，如滑动窗口最大值

• 优先队列实现：使用二叉堆来实现，涉及到的操作主要有 sink，swim，offer 和 poll 方法，

• 栈实现队列和队列实现栈：双栈一个用于 offer，一个 用于 poll；队列将队头元素调整到队尾

• 找到处理最多请求的服务器：需要统计空闲服务器和处理器中的服务器，采用 TreeSet 和优先队列

动态规划问题

• 该类问题存在重叠子问题，具备最优子结构和状态转移方程，解决方案通常有带备忘录的递归（debug 时可以缩进查看调用栈），dp table 的迭代解法，注意迭代的方向需要根据已知的 dp 状态来确定，如零钱兑换 I，斐波拉契数列，下降路径最小和等
• 编辑距离：dp[m, n] 表示子串 s1[0..m] 和 s2[0..n] 的编辑距离，如果想要具体的编辑方案，可以加上对应的选择即可
• 最长递增子序列：dp[n] 表示将其当作最后一个数字时的最长递增子序列长度，使用 patience sorting 可以降低时间复杂度，推广问题有信封嵌套问题，需要注意其排序方法，最长等差子序列，需要注意超时
• 最大子序和：包含正负数，dp[n] 表示 num[n] 作为子序中的最后一个数，最大的子序和，而不是 nums[0..n] 中的最大子序和
• 最长公共子序列：使用 dp[m, n] 表示子串 s1[0..m] 和 s2[0..n] 中最长公共子序列的长度，相关问题有两个字符串的删除操作，两个字符串的最小 ASCII 删除和等
• 最长回文子序列：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i, j]，然后迭代即可，由于回文子序列特殊性，也可以转化为最长公共子序列问题
• 0-1 背包问题：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i, w]，迭代即可，相关问题有分割等和子集
• 完全背包问题：物品的个数是无限的，通常涉及到将背包刚好填满的情况，相关问题如零钱兑换 II，组装新的数组等。注意其和爬楼梯算法的区别，前者求组合数，后者求排列数
• 区间调度问题：选择出来不重叠的区间的最大的个数，贪心算法需要选择 end 最小的，相关问题如无重叠区间，用最少数量的箭引爆气球，最多等和不相交连续子序列
• 视频拼接问题：需要注意排序的方案，start 升序排列，start 相同则按照 end 降序排列
• 跳跃游戏：跳跃游戏 I 需要找到每次跳跃的最大距离，作为下一次的跳跃起点，跳跃游戏 II 同样道理，注意判定每次增加步数的逻辑，两者也可以使用动态规划来解决
• 最小路径和问题：dp[i, j] 表示 nums[i, j] 到 nums[0, 0] 的最小路径和
• 地下城游戏：dp[i, j] 表示从位置 [i, j] 出发，到达 [m, n] 的最少血量，注意其和最小路径和问题的对比
• 自由之路：dp[i, j] 表示指向 ring[i]，需要输入 key[j..n] 的最小的操作次数
• K 站中转内最便宜的航班：dp[i, j] 表示经过最多 i 次中转，到达 j 的最便宜的航班
• 正则表达式匹配：dp(i, j) 表示 s[i..] 能否被 p[j..] 匹配，使用递归；或者 dp[i, j] 表示 s[0..i] 能否被 p[0..j] 匹配，使用迭代；简单的变体是通配符匹配问题
• 鸡蛋掉落：使用 dp(k, n) 表示从 n 层楼中，使用 k 个鸡蛋，确定 f 的最小确切尝试次数，或者可以使用 dp[k, m] 表示 k 个鸡蛋，最多 m 次操作可以确定 f 的最高的层数，使用迭代解决
• 戳气球：使用 dp[i, j] 表示开区间 (i, j) 内能得到的最大分数，通过最后一步思考状态转移方程
• 博弈问题：预测赢家问题中每个人从两端选择数字，最终数字和大的获胜，使用 dp[i, j] 表示从 nums[i, j] 中选择时的情况，dp[i, j, 0] 表示先手分数情况，dp[i, j, 1] 表示后手分数情况，相关问题有石子游戏
• 两键键盘：输出 n 个字符最少的操作次数，另外也可以考虑分解质因数方法
• 四键键盘：N 次操作输出 A 的最多的个数，考虑最后的一次操作，不是 A，就是 C-V，以此作为递推式
• 股票买卖问题：定义 dp[n, k, 0] 表示在第 n 天，最多 k 次交易，未持有股票的最大收益，而 dp[n, k, 1] 表示在第 n 天，最多 k 次交易，持有股票的最大收益，找到状态转换关系，使用迭代即可解决，注意一些问题也可以使用贪心算法解决
• 打家劫舍问题：dp[i] 表示 num[i..] 开始，能获得的最大价值，变体如增加首尾限制，二叉树限制等
• 字符匹配算法：使用 dp[i, j] = next 表示当前状态 i，遇到字符 j 后下一个状态是 next，以此为状态机，来进行匹配，第一次相当于 pat 与 pat[1..] 匹配，第二次相当于 pat 与 text[0..n] 匹配；也可以使用 KMP 算法，使用 next 数组表示最大相同真前后缀的前缀末尾索引
• 构造回文的最小插入次数：dp[i, j] 的表示对字符串 s[i..j]，最少需要进行 dp[i, j] 次插入才能变成回文串，注意状态转换关系
• IPO：使用贪心算法，每次选择能投资项目中的最大利润
• 不含连续 1 的非负整数：定义 dp[i] 为长度为 i 的有效数字的个数，然后对每位进行操作统计
• 解码方法 II：定义 dp[i] 表示 str[i..n] 可被解码方法的数目，找到递推关系即可
• 超级洗衣机：使用贪心算法，考虑左右两组传递次数和某一个洗衣机最大传递次数
• k 个逆序对数组个数：定义 dp[i, j] 为 1 - i 自然数中，j 个逆序对的个数，分析数字 i 的位置
• 恰有 K 根木棍可以看到的排列数目：定义 dp[i, j] 表示 i 根木棍中可以看到 j 个木棍，分析长度为 1 的木棍所在位置
• 猜数字大小 II：定义 dp[i, j] 表示从范围 [i, j] 猜数字的最小的代价，从而可构造转移方程
• 交错字符串：定义 dp[i, j] 表示 s1[0, i) 和 s2[0, j) 是否能构成 s3[0, i+j)，从而构建转移方程
• 三个无重叠子数组的最大和：定义 dp[i,k] 表示 nums[0..i] 构成 k 个不重叠子数组最大和值，考虑 nums[i] 是否在里面，从而构造转移方程
• 不同的子序列：定义 dp[i, j] 表示 s[i..] 中含有 t[j..] 子序列个数，构造对应的转移方程
• 最低加油次数：给定加油站和初始油量，判断最少需要加多少次油才能到达目的地，使用贪心
• 最后一块石头的重量 II：两块石头重量的差值当作新的石头放入其中，转换为 0-1 背包问题
• 一和零：使用背包问题，dp[i, j, k] 表示前 i 个字符串里面，最大 j 个 0，k 个 1 的子集长度
• 环绕字符串中唯一的子字符串：通过考虑以某字符结尾的最大长度，就可以计算出来不同子串的长度
• 我能赢吗：博奕类问题，每一步遍历当前所有选择看是否会导致赢的结果
• 设置交集大小至少为 2：区间排序，按照首点升序，尾点降序进行排列，每次贪心选择区间前两个元素
• 新 21 点：定义 dp[x] 为起始分数为 x 时获胜概率，得到转移方程
• 组合数取模：组合数求解可以使用递归或者算式，即 comb = comb * i / j，但是较大数不能使用直接方法取模，会造成精度损失，推荐使用打表方法，采用递推式来解决
• 最小差值 II：每个元素只能加 k 或者减 k，可以先排序，然后中间切断，最大值最小值只在端点出现
• 使序列递增的最小交换次数：每次只交换相同位置处的数组，定义 dp[i, j] 表示 [0..i] 的数组在 i 处交换和不交换时使序列递增的次数
• 分汤：首先需要向上取整，定义 dp[i, j] 表示分别剩余 i 和 j 的汤时所求的概率值，另外当 n 超过一定值时，其会趋于 1
• 最小移动总距离：机器人到工厂的位置时不严格单调增的，定义 dp[i, j] 表示前 i 个工厂修复前 j 个机器人的最小移动总距离
• 完美分割的方案数：定义 dp[i, j] 表示前 i 个字段分割成 j 段的方案数，再维护一个前缀和 g[i, j]，表示 dp[t, j] 的前 i 项和
• 不重叠回文子字符串的最大数目：定义 dp[i] 表示前 i 个字符中可以组成多少个长度大于等于 k 且不重叠的子串，中心扩展法求回文
• 最大平均值和的分组：定义 dp[i, j] 表示前 i 个元素分为最大 j 个非空子数组时最大平均值
• 掷骰子模拟：规定连续掷出骰子相同数字不超过某个数，定义 dp[i, j, k] 表示第 i 次投掷后，最后一位是 j，并且 j 重复了 k 次
• 灌溉花园的最少水龙头数目：贪心算法，每个点 i 都求出对应的 rightMost 值，然后从 0 计算即可
• 最短公共超序列：定义 dp[i, j] 表示 s1[i..] 和 s2[j..] 最短公共超序列，然后依据递推式构造答案
• 最长递增子序列：既可以使用 dp[i] 进行递推，也可以使用 l[i] 表示当前子序列长度为 i 时末尾的数字，这样的话，对于一个数字 num[i]，如果 nums[i] > l[i] 可以凑成更长的序列，否则在序列中查找第一个大于 nums[i] 的索引，更新该索引上的值为 nums[i] 即可
• 俄罗斯套娃信封问题：传统 dp[i] 可以使用，但是会超时，可以一维升序，二维降序排列，并运用二分查找更新最长子序列 l[i]，其表示长度为 i 的子序列最后一个值
• 多边形三角剖分的最低得分：选择相邻两个点作为底边，再选择其中一点构成三角形，递推即可
• 购物单：包含主件与附件，附件必须依赖于主键，可以将主键和附件一起考虑，要么只买主键，要么买主键和对应附件，构成背包要素即可
• 放苹果：将 m 个相同的苹果放在 n 个同样的盘子中，定义 dp[m, n] 表示对应结果，则有 dp[i, j] = dp[i - j, j] + dp[i, j - 1]；或者深搜，每次放置的苹果数不少于上一次值，在最后只有一个盘子时统计即可
• 通配符匹配：要求匹配 ? * 两种通配符，可以考虑使用递归，或者动态规划，定义 dp[i, j] 为 str1[..i] 和 str2[..j] 是否匹配，可以写出递推式
• 合并石头的最低成本：每次合并 k 个石头，求合并一堆石子的最小开销，定义 dp[i, j, t] 表示合并 stones[i, j] 为 t 堆石子开销，将石子划分为两堆，进行递推即可
• 最小的必要团队：可以转化为集合背包问题，使用状态压缩，每次遍历技能的时候可以使用或运算来判断是否能够使用更少的人来达到目标
• 查找充电设备组合：实际上可以转换为背包问题进行解决
• 最小化旅行的价格总和：统计路径上的所有点，然后按照打家劫舍III 的思路来处理该树形问题即可
• 两地调度：考虑所有人前往 B 城，再从中挑选 N 个去往 A 城，可以使用贪心的思想
• 跳跃游戏 II：可以使用贪心的思路来解决问题，每一步记录下能够跳跃到的最大距离，每次碰到最大举例，跳跃数加一即可
• 使数组严格递增：给定数组和替换数组，从替换数组中选择数来替换给定数组，使其严格递增，可以使用 dp[i.. j] 来表示给定数组前 i 个元素经过 j 次替换后的末尾元素最小值
• 两个非重叠子数组的最大和：给定非重叠子数组的长度，求两个子数组最大和，可以考虑枚举第二个子数组末尾位置，每次都可以更新前一个子数组的最大值，最终求得最大值
• 树节点的第 K 个祖先：类似跳表思想，维护每个节点的 2 的指数次方的父节点，便可以将查询的复杂度降低到 logn 级别
• 最大子序列交替和：可以定义 dp[i, 0] 表示在 nums[0..i] 中选中一个子序列，子序列最后一个元素下标为偶数的最大交替和，从而构建转移方程，实际上，可以参考股票买卖问题

回溯算法（DFS 算法）

• 回溯算法和动态规划递归算法类似，不过不同的是回溯算法不存在重叠子问题，回溯算法的核心就是做选择，回溯，撤销选择，相关问题如全排列，n 皇后，数独问题，全排列 II（重复数字）
• 集合划分：使用两种视角，桶的视角即为每次刚好填满一个桶，站在数字的视角，即为每次进入一个桶，两种算法通过剪枝可以减少运行时间
• 子集，组合和排列问题：子集和组合问题都是从当前位置的下个位置开始回溯，但是排列问题不同，另外可以考虑递归思路
• 括号生成：合法括号对性质，在回溯中添加左右括号剩余数量（有效信息）
• 单词搜索 II：在二维棋盘中找到某个单词是否存在，注意剪枝以防超时
• 祖玛游戏：为了提高效率，可以使用剪枝或者使用备忘录来检测已经判断过的字符串
• 字典序排序：使用 DFS 可以进行搜索排序，使用迭代可以得到 O(1) 空间复杂度
• 火柴拼正方形：每个位置可以选择放入四个边中之一，只要满足其边长不会超过总长度的四分之一即可
• 到达首都的最少油耗：考虑每条边上的流量，必定是子树元素个数之和除以车子容量大小，然后深搜即可，注意第一个深搜条件
• 24 点游戏：需要注意可以加括号和不能加括号两种回溯的方法，前者需要枚举队列中的任何两个数字的组合，后者则只需要选某个操作符和数字即可
• 火车进站：可以维护一个进站栈和出栈栈，然后深搜回溯即可
• 将真分数分解为埃及分数：可以直接将其划分为 a 个 1/b 相加，或者考虑 b/a = c ，那么显然可以考虑取出一个 1/(c+1)，多余的数进行递归处理即可
• 划分为 k 个相等的子集：使用回溯，每次检测已经选取的值之和是否能够符合条件，递归处理即可
• 最大平分数组：平分数组，使得每个数组和相等，可以转化为划分为 k 个相等的子集问题来解答，另外的相关问题有星际篮球争霸赛
• 冗余连接 II：在有向树中增加一条边，现在需要找到这条边，使其成为一棵有向树；可以通过并查集来判断所有边能否构成树形结构，端点祖先各不相同才能连接，否则不能构成树
• 得分最高的路径：单单通过搜索回溯是不行的，时间复杂度过大，可以使用使用优先队列 BFS 搜索，或者考虑使用二分法和搜索结合的思路（极大极小化问题）
• 铺瓷砖：考虑到给出的范围较小，可以尝试回溯方式解决问题，通过使用一个 boolean 二维数组，可以将其遍历方式按照点的粒度进行遍历，省略方砖之间的检测问题

BFS 算法

• BFS 用于找寻最短路径一类的问题，主要通过队列和设置 visited 集合来解决，可采取的优化如双向 BFS 搜索，相关问题如打开转盘锁，二叉树的最小深度等问题
• 滑动拼图：将二维数组变为字符串处理，同时利用已知信息建立邻居映射
• 单词接龙 II：使用 BFS 查找最短路径，可以采用双端 BFS 优化，使用 DFS 构造路径
• 最小高度树：使用拓扑排序思想，将入度为 1 的数字放到队列中去，然后进行 BFS 即可
• 数组的均值分割：数组中元素个数在 30 以内，可以采取双向 BFS 搜索技巧
• 公交路线：使用 BFS 会超时，可以尝试使用双向 BFS 来解决，另外，也可以将运营线当作是节点，问题可以转化为图问题连接点最短路径，降低搜索开销

并查集算法

• 除法求值：给定一组除法式子，判断给定查询的结果，使用并查集可以让有倍数关系的变量在一起
• 好路径的数目：给定一个树图，统计路径中值最大的节点在端点处的数目，可以采用并查集一步步加入

数学运算技巧

• 常用的位操作：使用异或判断两个数字是否异号，使用异或交换两个数字，使用 n & (n - 1) 消除数字 n 的二进制表示中的最后一个 1，相关问题如汉明重量，判断是否为 2 的指数，查找只出现一次的元素，两数之和
• 阶乘算法题：阶乘后零的个数取决于因子 5 的个数，相关问题有阶乘后的零的个数，阶乘后 k 个零
• 高效寻找素数：在进行因子判断的时候，只需要遍历到 sqrt(x) 即可，相关问题如计算质数的个数，注意两层循环的起始和终止条件
• 高效模幂运算：使用递归处理数组指数，模运算的防溢出运算，高效求幂，相关问题如超级次方
• 寻找缺失元素：情况一是 [0, n] 的序列放到长度为 n 的数组中，情况二是 [1, n] 的序列放到长度为 n 的数组中
• 同时寻找缺失和重复的元素：使用映射来表示某个数字已经存在，通常这样的问题需要索引和数字一起使用
• 水塘抽样算法：对于第 i 个元素，应该有 1/i 的概率选择该元素，1 - 1/i 的概率保持原有的选择，可以推广到随即抽取 k 个元素，相关问题如链表随机节点，随机数索引
• 一行代码解决的问题：Nim 游戏，石子游戏，电灯开关问题（因数个数问题）
• 反直觉概率问题：男孩女孩问题，生日悖论，三门问题（概率浓缩）
• 洗牌算法：Fisher-Yates 算法每次迭代模拟了从剩余数字中选择一个放到对应位置上的过程，相关问题如打乱数组
• 随机数生成问题：基于 (rand(X) - 1) * Y + rand(Y)可以均匀生成 [1, XY] 之内的随机数，随后使用拒绝采样挑选随机数
• 可怜的小猪：小猪试毒问题改编而来，在给定 n 只小猪，m 次尝试时，每只猪提供的信息是 m + 1 次，整个的信息个数就是 pow(m + 1, n)
• 数组中两个数的最大异或值：从高位到低位依次选择，利用异或运算的特殊性，三数之间两数异或等于第三个数，一步步向下迭代求解
• 不可能得到的最短骰子序列：上一个出现的序列后面的子数组应包含所有的数字，否则不能构造对应的子序列
• 镜面反射：根据 p 和 q 的奇偶性来判断翻转次数和折射次数，从而得到最终结果
• 负二进制转换：按照 -2 为 base，给出某个数的负二进制表示，仍旧可以使用除法求值，需要注意的是余数必定是正数才行
• 统计差异值大于相似值二元组个数：暴力会超时，可以转换为相同长度和不同长度两种情况，相同情况下差异值必定大于相似值，不相同下相似值大于差异值
• 子数组中占绝大多数的元素：统计数组中给定区间的占绝大多数的元素，可以通过统计每位 bit 数，bit 数大于阈值则答案中包含该 1；或者通过概率的方式求解，随机选择一个数，查看该数是否为众数；也可用区间树统计区间众数并给出出现次数

其他算法技巧

• 前缀和数组：适用于原始数组不变，频繁查询某个区间的累加和，相关问题如和为 k 的连续子数组个数，使用前缀和与哈希表解决，思想和 twoSum 类似

• 差分数组：主要用于频繁对原始数组的某个区间的元素进行加减，对区间 [i, j] 的修改实际上只需要修改 diff 数组的两个元素即可，相关问题如航班预订统计，得分最高的最小轮调

• 树状数组（二叉索引树）：用于处理区间统计量问题，只适用于点变化的情况

• 区间树：用于处理区间统计量问题，适用于区间变化的情况，比树状数组应用广泛

• 快速选择算法：存在于快速排序算法中，每次 partition 都会使得左边的数字小，右边的数字大，相关问题如数组中的第 k 个最大元素

• 分治思路：归并排序，分而治之，相关问题如为运算表达式设计优先级

• 区间问题：关键在于排序，以及判断两个区间相交与否，相关问题如删除被覆盖区间，区间合并，区间列表的交集，两个矩形覆盖的面积

• 使用哈希表：使用哈希表可以快速统计相同位置上出现的次数，相关问题如回旋镖的数量，将数据流变为多个不相交的区间，随机翻转矩阵，缺失的第一个正整数（O(n)）

• 排除法：搜索名人

• 数位 DP：通常用于求解在区间 [L, R] 上，满足条件的数字个数，主要思想是从高位开始枚举，使用记忆化搜索的方式递归求解。通常其 dfs 函数定义如下：

  // 单定义区间 [0, R] 方案，[L, R] = [0, R] - [0, L - 1]
  int dfs(char[] cs, int idx, bool isLimit, other-conditions);
  // 双定义区间 [L, R]
  int dfs(char[] cs1, char[] cs2, int idx, 
         	bool lLimit, bool rLimit, other-conditions);

  相关问题有数字 1 的个数，不含连续 1 的非负整数，不含 101 的二进制数，范围内的数字计数等

高频面试算法

• 分割数组为连续子序列：使用两个哈希表，分别统计出现次数和能在结尾放置的次数，优先放在上个序列的结尾
• 吃葡萄：将问题转化为三角形边长平分问题，并分析极端情况
• 烧饼排序算法：使用递归，首先让最大烧饼在最底层，类似于汉罗塔问题
• 字符串相乘：模拟乘法运算过程，注意参与乘法运算两个数的索引和结果索引间的关系
• 实现一个计算器：先解决加减，后解决乘除，最后考虑括号，使用单栈方法和双栈方法
• 接雨水问题：考虑当前节点能接的水是多少，从而解决问题，可以对状态进行优化，相关问题如一维数组接雨水，二维数组接雨水
• 寻找最长回文子串：关键在于奇数长度和偶数长度的回文子串的判定
• 括号相关问题：使用栈结构进行模拟，匹配问题则找到需要的右括号的数量，相关问题如判断合法括号串，使括号有效的最小插入及变体（一个左括号匹配两个右括号），有效的括号字符串（加入 *），最长有效括号
• 判定完美矩形：利用面积和顶点出现次数作为判别条件
• 考场就座：最大化学生之间的间隔，使用 TreeSet 作为数据结构，按照 distance 排序，需要处理边界情况
• 高效判定子序列：使用双指针可以解决该问题，但是如果需要匹配的子序列比较多的时候，可以结合二分查找提高效率

Java 编程知识点

• IntegerCache：在自动装箱时，为了提高性能，Java 缓存了 [-128, 127] 的整形值引用，因此，当我们比较两个 Integer 的时候，应该使用 equals 方法，或者借助 intValue 方法，而不是 ==

• Java 中的数字字面量都是整型，如果需要 long 型，需要增加 L 后缀，下列代码存在问题：

  long a = some_num();
  // 0xFFFFFFFF 被转为 -1，并非是 2^31 
  if (a == 0xFFFFFFFF) return false;

• 在使用 int 类型的变量相乘的时候，一定要注意结果可能会溢出，需要使用 1L 的字面量：

  int len = some_num();
  // 错误，仍然会导致溢出，表达式右边的结果是 int 类型
  long count = len * (len + 1) / 2;
  // 正确，此时表达式右边的结果是 long 类型
  long count = 1L * len * (len + 1) / 2;

• random.nextInt() 和 nextInt(upperBound)：不加参数的话，int 类型 32 位都会随机 0 或者 1，可能会产生负数，使用取模可能会产生负数，加参数的话返回 [0, upperBound) 之间的整型

• 在 Java 中使用 int[] 作为 HashMap 的键并不会得到想要的结果，因为其会使用 int[] 的索引作为 hashcode，可以使用 List<Integer> 或者重写一个类，该类重新实现 hashcode 和 equals 算法，亦或直接使用 TreeMap

• Object.hashCode 是一个实例方法，不允许 null；Objects.hashCode(obj) 是静态方法，允许 obj 为 null；Objects.hash(obj…) 也是静态方法，接受多个参数，返回所有参数的总的哈希值

• Integer.valueOf() 和 Integer.parseInt() 两者都是对字符串进行解析，不过它们的返回值类型不同，前者是 Integer，后者是 int

• List<Integer> 到 int[] 类型的转换不能直接使用 toArray，可以借助流：list.stream().mapToInt(Integer.intValue).toArray()

• 想要对自定义类实现排序，要么实现 Comparable<T> 接口，重写 compareTo 方法，或者是排序的时候传入一个 Comparator<T> 对象，重写 compare 方法

• 想要对 int[] 类型进行降序排序，不能直接用 Arrays.sort，其只对 T[] 提供自定义比较器，可以使用流操作来实现：Arrays.stream(arr).boxed().sorted((a, b) -> b - a).mapToInt(Integer::intValue).toArray()

• 在 Java 设计中 Stack 继承自 Vector，这是一种错误的设计，应该使用组合而不是继承关系。官方推荐写法：Deque<Integer> stack = new ArrayDeque<>()

• 注意使用三目运算符优先级：a + b > c ? b : c，此时判断的是 a+b 和 c 的大小，而不是 b 和 c 的大小。

• Java 中的提供字符串拼接有如下方式：String.join 和 StringJoiner，平时使用前者即可满足大部分需求

• Java 中可以使用 String.format("%8s") 来格式化字符串，默认使用空格，可以再次调用 replaceAll 函数来满足需求