目录

题目内容来自leetcode、牛客等平台，偶有面试笔试真题。

总结

  1. 未特殊说明则惯用语言为C++，偶尔会使用Java、Python，这些情况会特别标出。
  2. 由于牛客等平台在面试时，不一定会提供头文件，需要自己牢记使用的标准库函数位于哪个头文件中。
  3. 会给出一些我觉得非常好看的题解、总结博客的链接。
  4. 算法分类：
    1. 搜索（BFS、DFS）：单目标搜索、多目标搜索，搭配数据结构优化，单调性优化
      • 搜索从思路上可以分为：生成法、判别法两种。前者生成的一定是一个解，后者生成所有，并进行判定。
    2. 动态规划：记忆化的搜索。
      1. 单状态dp[][][]，多状态dp1[]、dp2[]
      2. 多种决策可能
      3. 递推形式
      4. 区间dp，最优化区间
      5. 背包问题
      6. 空间优化，时间优化参考
    3. 贪心
    4. 分治：可分性、合并时的复杂度
    5. 排序：排序后是否可贪心
    6. 数据结构
      1. 单调栈、单调队列
      2. 双堆
      3. 数组：双指针、预处理、和递归结合
      4. 树：前中后序的递归&非递归写法，层次遍历
    7. 图算法：并查集、拓扑排序、欧拉图、最短路、网络流、哈密顿路径、欧拉路径
      • 偶尔会有字符串等其他类型题目转换为图论。
    8. 模拟
    9. 数学推导
    10. 字符串：匹配算法、正则匹配、通配符匹配、转为图算法
    11. 滑动窗口
    12. 哈希
    13. 高级数据结构
  5. 一些建议：
    1. 从时间空间约束上寻找提示
    2. 从暴力法入手，观察搜索树结构，逐渐优化

题型分类

  • 颜色含义
    • 🟢 简单
    • 🟡 中等
    • 🔴 困难
  • 注
    • 篇幅所限，仅记录较有代表性的题目

模拟

  1. 🟡 950：按递增顺序显示卡牌。重新排序卡牌，使得满足一定条件。考验模拟的思路。

贪心

  1. 🟡 1686：石子游戏VI。看了题解。回合制的对抗类的决策问题，一般就是贪心或者搜索。可以先考虑贪心。本题的关键点在于能想到对于一轮决策的最优选择，取决于$(a_i-b_j)-(a_j-b_i)$的正负，并进一步转化为$(a_i+b_i)-(a_j+b_j)$，从而明白其实只需要对和做一次排序，就可以贪心了。

博弈

单独提出一类，经常出现的思路是，最小化一个最大值，或者最大化一个最小值。但思考这种内容，虽然实际不复杂，却往往很绕脑筋。

  1. 🟡 1140：石子游戏II。看了题解。自己想到了需要对未来的决策做最小化，但是始终没绕明白，写复杂了。实际上不需要区分轮次，每一次的DFS输入参数都是统一的，(begin，M)就够了，结果代表该时刻的最优决策。考虑到计算实际是从尾部开始严格向前递推。所以可以很容易的转换为动态规划写法。
  2. 🔴 1406：石子游戏III。做完II应该直接就能做。不过注意记忆化搜索实际上会比直接动态规划慢，函数的递归调用的时间消耗非常大。用记忆化搜索是无法完成的。
  3. 🟡 1690：石子游戏VII。还是一样，这次应该能想到还是对最左右两种决策做最大化。值得注意的是本次搜索的值应该直接就是每一轮得分的差值，这是最好算的，而且能直接运用到递归的过程中。直接计算某一个人的得分反而没有办法利用下去。和其他石子游戏一样，熟练之后应该放弃记忆化搜索，DP的写法能达到最大效率。

搜索

  1. 🔴 2867：统计树中的合法路径数目。自己最终写的是BFS的方式，而且从非质数开始扩展，统计所有的扩展（去重）。但实际上这又发生了很多重复计算。实际上中间的思路，从质数节点开始计算是正确的。题解中最重要的思想，也是树上问题最重要的思想就是，利用树的特点，对子树进行统计，而不是图论式的暴力的dfs、bfs。本题就是从质数节点开始计算，但先去统计质数节点的各个子树内，有多少个路径上完全没有质数的点。将各子树的这个统计值直接相乘，所有乘积的总和就是结果。或者从LCA的角度出发，也很容易看出来，所有的这种路径，一定是拥有一个质数LCA的两个非质数之间的路径。
  2. 🔴 2646：最小化旅行的价格总和。看了题解。可以说是树上DP经典题目了，下次别忘了就行。另外也算是在考察LCA（最近公共祖先）。
  3. 🟡 2477：到达首都的最小油耗。自己写了个类似拓扑排序。实际上夸张了，这题直接从根开始深搜就行。每个节点统计子树的全部乘客，再向上返回。
  4. :rec_circle: 2258: 逃离火灾。唯一需要特殊考虑的情况，是只有安全屋格子允许人和火同时抵达。优化思路，从起始位置和着火点分别BFS$\to$从安全屋反向BFS并记录路径$\to$不需要记录路径，只需要标记路径是从左侧还是右侧。题解里还有对等待时间二分查找+BFS，虽然效率低，但是二分的思路很有代表性。
  5. 🟡 39：组合总数。标准DFS。
  6. 🟡 40：组合总数II。39题的变种。需要使用一些剪枝来避免重复。
  7. 🟡 94：二叉树的中序遍历。普通写法没什么。迭代写法就需要一点东西了，可参考二叉树遍历方法大全、Morris遍历。尤其注意思考Morris后序遍历的反转操作。
  8. 🟡 22：括号生成。虽然是搜索题，但是想要写一个高效的剪枝版并不是很容易。
  9. 🟡 133：克隆图。BFS，需要注意的是图的各种特殊情况，自环，重复边等。
  10. 🟡 491：递增子序列。DFS+少量优化。通过添加当前层使用的数字的记录来避免生成重复的记录。值得二刷
  11. 🟡 638：大礼包。经典的记忆化DFS。开辟一个类似于状态数组，记录指定状态下的最优解，避免重复搜索。值得二刷。
  12. 🟡 863：二叉树中所有距离为K的节点。经典的多次搜索的题目，题解把问题分段处理。
  13. 🟡 417：太平洋大西洋水流问题。这一款题解是经典的变换问题，逆向DFS。地图类搜索题目的搜索起点、终点都可以尝试进行对调。有时能降低复杂度或实现难度。
  14. 🔴 127：单词接龙。经典双向BFS优化。
  15. 🟡 254：因子的组合。非会员链接。搜索，但是搜索的因子保持单调，以避免重复。
  16. 🟡 351：安卓系统手势解锁。暴力生成并判别是否满足要求即可。不用费力的进行正确生成。
  17. 🟡 465：我能赢吗。不可多得的博弈类型DFS，这类题目基本的思路就是记忆化的DFS。本题DFS的返回值代表是否有必胜策略。可以看看题解。
  18. 🟡 1530：好叶子节点对的数量。DFS时选择一个好的返回值真的很重要。本题可以考虑返回当前节点各深度的子孙节点列表。
  19. 🔴 124：二叉树中的最大路径和。经典的对树结构的搜索。通用思路就是，分别递归搜索左子树、右子树，处理二者返回值并返回。
  20. 🔴 301：删除无效的括号。DFS剪枝典范。对每个括号进行是否删除的搜索，但可以结合当前左右括号数量、总的左右括号数量进行一定程度的剪枝。
  21. 🔴 1036：逃离大迷宫。BFS略加优化能过，但题解效率更高。搜索类题目，先看输入数据规模，选择合理的搜索内容。本题就是，不是直接搜索通路，而是判断障碍节点能否单独包围住起始点或终止点。
  22. 🔴 1368：使网格图至少有一条有效路径的最小代价。可以用最短路。但本题更有价值的思路是0-1广度优先搜索。原理很简单，BFS的队列使用双端队列，权为0的边push_front，1的push_back。
  23. 🔴 980：不同路径III。记忆化搜索。通过保存$dp(current_point,unseen_points)$来减少重复搜索。其中unseen_points代表了尚未遍历的节点列表。
  24. 🔴 407：接雨水II。直观上是寻找低点并扩散，但实际本题是从外向内扩展，即假定外围有一圈水，并且从最矮处开始扩展（短板效应）。经典的反向思路的BFS。BFS可以偶尔尝试把从内向外，转为从外向内。

数学

  1. 🟡 1954：收集足够苹果的最小花园周长。自己写的纯暴力，实际上本体是二分加通项公式。平方和通项公式$\frac{n(n+1)(2n+1)}{6}$。
  2. 🟢 914：卡牌分组。简单的gcd（最大公约数）题目。欧几里得gcd、扩展欧几里得
  3. 🟡 343：整数拆分。从数字分析入手，发现所有的拆分方式中，拆出最多的3是最优解。
  4. 🟡 365：水壶问题。基础款可以写个BFS。但由于是判定问题，其实可以直接参考扩展欧几里得、裴蜀定理。
  5. 🟡 279：完全平方数。可以按照无穷背包进行处理。但题解提供了一个数学解法。四平方和定理。只需要记住一点，若数字可表示为$4^k(8m+7)$，其中$k,m \in \mathbb{N}$，则必定只能用4个平方数求和，否则可以用至多3个平方数求和得出。
  6. 🔴 891：子序列宽度之和。逆向思维，寻找子序列中的max/min$\to$固定max/min，计算有多少个序列。固定max/min，需要先对数组排序，然后按顺序取。随后可以通过数学推理，计算出所有序列的和的一个解析解表达式。
  7. 🟡 2028：找出缺失的观测数据。可以写搜索，效率还行（每种数字的数量都有上下限可用）。但题解给出了一种已知均值和整数的总数，可以直接构造出整数数组的方法。
  8. 🔴 1259：不相交的握手。非会员传送门。可以用DP，但用数学更好。卡塔兰数+Lucas定理。
  9. 🟡 1094：拼车。看题解，用差分数组思想，前缀和和差分数组互为逆运算。将上下车视作加减人数，则可把任意位置的乘客数量看作对这个加减法的前缀和，最笨的方式是计算所有位置的前缀和。但实际上本体是一个区间修改，而且区间很小，那么可以做前缀和的逆运算，差分数组，差分数组只需要在区间修改的起始和终止位置进行调整。最后再用差分数组构建前缀和即可。

二分

二分查找，最好的表示方式就是，left边界，remain查找区间长度。注意left+remain就是第一个超出区间的值，但是也有可能是查找结果，参考vector容器的end()。参考C++标准库lower_bound的可能实现。

  1. 🔴 100154：执行操作后的最大分割数量。利用前缀和统计字母的频率，可以用位运算和内置函数popcount加速。修改的时候分成不受影响的前缀，受影响的中间段，不受影响的后缀段。这种二分法最好想到，但自己只二分了一次（前缀），实际上对后缀段还需要再二分一次来达到最高速度，整体是$O(nlogn)$，参考题解。也有DP的解法，性能确实很高$O(n)$，也确实不好想。
  2. 🟡 1901：寻找峰值II。自己写的二分仍不能达到题目的时间复杂度要求。官方题解的办法需要一点巧妙的证明的思路：某一行的最大值一定可以是峰值（之一），求某一行的最大值是$O(n)$的，在此基础上去二分，这个元素的上下如果某一个比这个元素还大，那就抛弃另一侧，因为这个更大的元素所在的一侧，一定有某一行的最大值是峰值（并不是说另一侧没有，只是说这一侧一定有）。其实仍然是迭代爬坡法，只不过是针对每一行的最大值进行爬坡。
  3. 🟡 162：寻找峰值。虽然也知道是二分，但还是看了题解。题解将这种通用思路总结为迭代爬坡法：选中点，根据中点左右的大小，选一个爬坡方向，留那一半的区间。思考过程，先从$O(n)$的方式开始思考，单纯线性爬坡肯定是可以的，那么其实将其改造为二分也就不难想象和证明了。有点像下面题目：山脉数组中查找目标值的前半部分。
  4. 🟡 33：搜索旋转排序数组。自己写了很久总有问题。精选题解。很考虑分类讨论能力和对二分查找的理解。值得二刷。
  5. 🟡 540：有序数组中的单一元素。利用有序性。
  6. 🔴 4：寻找两个正序数组的中位数。经典的二分查找题目。普通的二分$O(log(m+n))$，以及利用中位数性质的二分$O(log(min(m,n))$（典型的数量关系，一个数组划分后，另一个数组理论上的划分位置是固定的）。还要注意特殊情况处理。值得二刷。
  7. 🔴 719：找出第k小的距离对。看的题解：二分查找 + 非常妙的双指针。一般来说，计算全部的距离（本题的求解目标值）的复杂度，是要高于搜索合适的距离值（尤其是使用二分搜索）。可思考求第K大这个经典问题。
  8. 🟡 57：插入区间。C++下本题最快捷的办法就是自己写一个lower_bound、upper_bound所需要的Compare函数。
  9. 🔴 1095：山脉数组中查找目标值。还是区间二分，需要先从数组中查找到最大值。很有新意的一道题目，考验对于各种情况的分析。题解非常简洁，值得二刷。
  10. 🔴 363：矩形区域不超过K的最大数值和。本题是前缀和+二分。注意当题目中出现不超过XXX的字样的时候，说明出现了不等式，而这一般意味着可以对中间结果进行排序（或使用动态有序的数据结构），并用二分进行查找。
  11. 🔴 410：分割数组的最大值。DP和记忆化搜索复杂度太高怎么办？一定要学题解，非常经典的二分思路，对待求结果进行二分测试。先设定一个最大值，超过该值就进行划分，如果划分数组的数量符合要求。再进一步用二分确定最大值的范围。
    • 仔细思考。如果搜索，则相当于是求出了过多的信息（很多种划分方式的最大值都被算出来了）。
    • 只要是结果有大小顺序，都可以用二分测试来计算。只不过二分的指标可能是非常和原始思路有很大区别。
  12. 🟡 2560: 打家劫舍 IV。经典最小化最大值问题。这类问题就是针对这个值进行二分。而不是真的去模拟求出所有的最大值。另外该题需要想明白两点：先选一定不比后选更差（贪心策略的正确性，类似于优先选择最早完成的任务），另一点是二分的最终结果一定会存在于数组中（不用担心二分的结果不在原数组）。

字符串

  1. 🔴 100207：找出数组中的美丽下标 II。先找出所有匹配位置，这一步用KMP就是最方便的。然后对匹配位置之间进行二分。
  2. 🟡 2707：字符串中的额外字符。动态规划的部分很好想，字符串还是Trie树经典优化。Trie特别适合需要按前缀/后缀顺序测试字符串是否存在的情况。一旦发现某个前缀/后缀已经不可能存在，就可以结束当前位置的所有测试。
  3. 🔴 100158：转换字符串的最小成本 II。周赛题目，和题解思路基本一致，但是本题卡常数，必须用Trie树优化，将字符串离散化，提升字符串匹配速度。写烦了，抄了题解。
  4. 🔴 828：统计字符串中唯一字符。和题解的思路是一致的。把计算子串中的唯一字符，转向计算一个字符能在多少个子串中唯一。但是计算这种子串卡了很久。注意理解：计算在$(begin,end)$开区间内，包含middle位置的字符的子串的数量（其中$begin<middle<end$），就是$(middle-begin)*(end-middle)$。
  5. 🔴 1044：最长重复子串。最长重复子串，等价于求所有后缀的最长公共前缀。后缀数组的样板题目。
  6. 🟢 28：实现strstr。平均意义上又好写又快的Sunday算法。其实就是两条策略：失配后对比主串中此次参加匹配的子串后的下一个字符，如果在模式串中没有，则大跳，否则对齐到模式串从右数第一次出现的位置。
  7. 🟢 1071：字符串的最大公因子。有个题解非常精妙，比较str1+str2==str2+str1，如果相等，返回gcd(str1.size(),str2.size())，否则返回0。
  8. 🟡 8：字符串转整数atoi。凡是计算，都要考虑中间步骤、最终结果，是否会溢出。尤其是结果不会溢出，但是粗暴的中间计算会，一定要注意。
  9. :构建回文串检测: 1177：构建回文串检测。计算各个奇偶性并进行判断即可。
  10. 🟡 820：单词的压缩编码。使用Trie树(前缀树、字典树)题解。
  11. 🟡 151：反转字符串里的单词。小技巧，先翻转小单词，再翻转整体，等价于把单词位置进行对调。
  12. 🟡 647：回文子串。先使用Manacher算法求出全部回文子串，结果显然。值得二刷。
  13. 🔴 1044：最长重复子串。二分法+Rabin-Karp算法（实现不好就超时）。后缀数组+最长公共子串。没做完
  14. 🔴 65：有效数字。直接上状态机，参考题解中提到的编译原理DFA。
  15. 🔴 466：统计重复个数。题材非常新颖的一道。统计字符串之间的循环节。注意：参考小数的循环，字符串的循环节不一定从第一节字符串开始（前面可能有一个前缀）。题解传送门。值得二刷。
  16. 🔴 1153：字符串转化。非会员传送门。很新颖的一道题目。判断类题目不需要给出解，只需要判断。本题只需要判断是否可能完成转换：不能具有全部26个字母，不能有相同字母需要修改为不同字母。
  17. 🔴 212：单词搜索II。经典前缀树（字典树、Trie树）题目。可以看一下题解的优化实现。
  18. 🔴 6093：设计一个文本编辑器。（看了题解）脑筋急转弯级别的困难题。很容易陷入到写一个链表结构的数据结构中（很难写）。但实际上，可以看作是类似两个栈，分别是前缀和后缀。左右移动就是两个栈来回压入，插入删除则是对前缀的压入和弹出。

动态规划

  1. 🔴 1883：准时抵达会议现场的最小跳过休息次数。转移方程很好想，问题在于浮点数的精度问题。个人觉得即使使用了极小量EPS和数字相减（比如取$10^-7$），也不能保证ceil的正确性（单纯浮点数的运算没问题，但是对浮点数进行ceil/floor都是有风险的）。最好的办法就是做离散化，用整数直接运算，而且不做浮点除法，速度还能更快。
  2. 🔴 2581：统计可能的树根数目。自己写的是普通的记忆化搜索。题解的意思是树上DP，不过也是DFS实现的。所谓的动态规划，是指每一步，进行换根操作。这在树类题目中是一个很常见的操作，因为一般来说，一次换根，只有两个节点之间的父子关系发生了变化，很容易计算状态转移。不过时间复杂度是一样的。
  3. 🔴 1125：最小的必要团队。想到了状态压缩，但是没想到DP。看了一下题解思路很简单。对状态压缩进行DP，最暴力的方式就是枚举当前所有状态，再加上一个新状态，构成状态转移即可。
  4. 🟡 1567：乘积为正数的最长子数组长度。自己写了一个用前缀乘积的。题解也是类似的分类讨论（dp[i]以i为结尾的正数、负数的最长长度）的动态规划思想。没什么特别的，注意细节就行。
  5. 🔴 2809：使数组和小于等于x的最小时间。抄了题解。问题还是在于状态设计。困难的动态规划一般都是需要进行一系列附加的思考。反而最后的状态转移方程并不一定复杂。本题中有若干个要点需要理解，剩余总和的组成（初始总和+添加总和*i-被减少的总和）。因此最小化剩余总和，就转化为了最大化被减少的总和。当需要选择一系列数据进行最大化，我们就有一个典型的模型：01背包。而本题更复杂的思考就在于，选择的顺序一定是按照nums2从小到大。因此按照从小到大去状态转移，就解决了动态规划问题的无后效性。
  6. 🔴 1349：参加考试的最大学生数。抄了题解。没想到正确的状态设计的思路。每一行的可坐人数和当前行的坐法，以及上一行的坐法有关。而每一行的坐法可以用bitmask来表示，之后再对两行的bitmask进行暴力匹配。从而算出每一个状态下的最多人数。只要能想到正确的状态设计就成功了。可以从题目的数据范围去思考。另外题解中还提到了转换为二分图模型，以及插头DP（轮廓线DP）。
  7. 🔴 1671：得到山形数组的最少删除次数。自己写的是$O(n^2)$的动态规划，对每个位置，求两次递减子序列。但实际上本题可参考最长递增子序列。求LIS类问题，是有$O(nlogn)$方法的。
  8. 🟡 2008：出租车的最大盈利。自己写的是对订单DP+二分。题解中有另一种对位置DP+哈希表，实际上只需要回溯考虑同一终点的所有行程。没有绝对的好坏，不过本题的数据规模确实是哈希表更好。
  9. 🔴 689：三个无重叠子数组的最大和。思考方向比较顺畅：从一个最大和子数组，到两个，再到三个，可以很自然的思考出来动态规划方程。本质还是背包问题。
  10. 🟢 121、122：买卖股票的最佳时机I/II。有通用DP模板。
  11. 🟡 309：最佳买卖股票时机含冷冻期。$dp[i][j]$代表第i天结束，手中有j支股票的最大收益。
  12. 🟡 877：石子游戏。博弈类问题的DP。但实际上，本题先手必胜。值得二刷。
  13. 🟡 241：为运算表达式设计优先级。感觉可以dp。好像没自己写？
  14. 🟡 300：最长递增子序列。$O(n^2)$的好写。思考一下$O(nlogn)$的。题解精妙之处在于状态的设计。dp的优化方向之一，让状态具备单调性。也叫做LIS问题（最长不下降子序列）
  15. 🟡 96：不同的二叉搜索树。dp就可以。也了解一下卡塔兰数。
  16. 🟡 95：不同的二叉搜索树II。本题需要直接返回所有的树，需要快速且不重复的生成。题解中提到了树的同构问题。值得二刷
  17. 🟡 918：环形子数组的最大和。注意子数组（必连续）和子序列（不必连续）的区别。题解为kadane算法及其变种。值得二刷。
  18. 🟡 337：打家劫舍III。不太常见的树形DP。$curNode=f(leftSon,leftSonSon,rightSon,rightSonSon)$。
  19. 🟡 494：目标和。题解经过一定的数学变换，变为0/1背包。$\sum(A)+\sum(B)=\sum(Nums), \sum(A)-\sum(B)=S, \sum(A)=(\sum(Nums)+S)/2$。如此目标就变为了求容量为$(\sum(Nums)+S)/2$的背包中集合$a$的问题。
  20. 🟡 221：最大正方形。二维问题（及以上）设计状态方程的经典例子。题解按照右下角坐标设置状态。$dp[i][j]$代表右下角坐标为$(i,j)$的矩形的最大面积。则状态转移类似$dp[i][j]=f(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])$
  21. 🟡 473：火柴拼正方形。基本解法是多次DFS。但题解给出了更好的状态压缩的动态规划。即标记每一个火柴是否被使用，作为状态。而且规定任意状态下至多有1个边尚未填满。动态规划的一个典型思路就是，并不需要计算所有状态，只需要证明，所计算的状态链必定包含最优解即可。值得二刷。
  22. 🟡 139：单词拆分。自己写了个回溯+前缀树，经典TLE（Time Limit Exceeded）。其实这道题是个DP，字符串的DP其实挺多的。以$dp[i]$记录目标字符串$s$的子串$substr(0,i)$能否被成功过拆分。状态转移类似背包问题。
  23. 🔴 140：单词拆分II。做一定的预处理，获取任意位置分割后的字符串样子，便于使用。
  24. 🟡 131：分割回文串。先预处理回文位置，再做动态规划。$dp[i]=f(dp[0…i])$。
  25. 🟡 698：划分为k个相等的子集。自顶向下是搜索，自底向上是DP。题解又是状态压缩的动态规划，和473题火柴拼正方形类似。值得二刷。
  26. 🟡 516：最长回文子序列。自己写了一个求字符串s和s逆的最长公共子序列的方法，转化为了已知的问题。题解还提到了另外的动态规划方法。$dp[i][j]$代表从$i$到$j$的最长回文子序列，然后比较$s[i-1]$和$s[j+1]$。
  27. 🟡 375：猜数字大小II。不是贪心。一种经典的求解最优化的动态规划问题，还有一道扔鸡蛋的题目。题解中讲明了此题需要进行区间上的动态规划并求出极值。主要的状态转移方程为：$dp[i][j]=min(k+max(dp[i][k],dp[k][j]))，k \in [i,j]$。
  28. 🟡 152：乘积最大子数组。很值得思考的题目。很明显和最大子数组和类似，但是问题在于存在0和负数。此时只需要同时保留max、min，就仍可以获得最终解。因为min中的负数可以再经一次和负数相乘变正。
  29. 🔴 312：戳气球。经典区间DP，模板$dp[l][r]=max/min/···(dp[l][r],f(dp[l][k],dp[k][r],g(l,k,r)))$。
  30. 🔴 943：最短超级串。经典字符串生成类题目。从$O(N!)$降到$O(2^N)$的关键思路，在于并不需要计算全部的排列。题解只需要计算每一次以第j个字符串为结尾时，所能达到的最优长度。再结合对全部二进制子集的枚举。这种思路是通用的：用二进制枚举子集，然后计算当前这一步的最优解。
  31. 🔴 44：通配符匹配。和正则类似的动态规划。但其实还有贪心的题解。
  32. 🔴 72：编辑距离。字符串之间变换的DP方法都比较相似。$dp[i][j]$取最小值：$dp[i-1][j-1]$、$dp[i-1][j-1]+1$、$dp[i][j-1]+1$、$dp[i-1][j]$。对两个串前缀的各情况进行穷举：前缀最后一对儿字符相等，替换字符，添加一个字符，删除一个字符。
  33. 🔴 887：鸡蛋掉落。求给定鸡蛋数量和楼层总数情况下，测得安全楼层所需的最小次数。非常经典的题目，题解提出了3种方法，从二分+动态规划，单调动态规划，再到数学法（逆向思维，将楼层作为目标值）。其中带有决策单调性优化的动态规划非常值得思考。非常值得二刷。
  34. 🔴 546：移除盒子。搜索式的DP写法。本题指出了一类相对复杂的区间DP问题，即区间结构可以由于之前的决策发生改变。使用普通的$[l,r]$不能表示出全部的区间结构。题解指出这种情况下需要引入额外的状态维度，来表示出一次决策所使用的全部区间。如$[l,r,k]$代表范围后还有$k$个。值得二刷。
  35. 🔴 664：奇怪的打印机。其实和546题是一模一样的。锻炼下举一反三的能力。
  36. 🔴 514：自由之路。自己写了个略带优化的搜索。实际可以用DP。比较特别的一道题目。$dp[i][j]$代表对齐$key[i]$时，位于$ring[j]$位置的最小移动步数。注意环是可以逆时针、顺时针转。
  37. 🔴 741：摘樱桃。经典“多线程”DP，其实就是状态方程中同时考虑多个决策。$dp[point_1][point_2]$$=f(dp[prev(point_1)][point_2]$$,dp[point_1][prev(point_2)])$。
  38. 🔴 85：最大矩形。84题的变种，动态规划和单调栈的结合。题解是预处理+单调栈。
  39. 🔴 689：三个无重叠子数组的最大和。经典的多种中间状态输出到最终决策的动态规划。3次预处理，分别是每个位置的子数组和$sum[]$，i之前的子数组和最大值$before[i]$，j之后的子数组和的最大值$after[j]$。求最大值$sum[i]+before[i-k]+after[i+k]$。题解还有更厉害的$O(1)$空间的解法。
  40. 🔴 1531：压缩字符串II。不容易的一道题目。有反方向选取和删除两种题解。值得二刷。
  41. 🔴 956：最高的广告牌。比较特别的一题。题解两种解法，递归式DP方法$dp[i][s]$代表前i个管子正负总和为s时，正数和的最值。细节：实现时需要保证s>0，将总和向正平移5000，不影响结果。第二种是对半搜索，也比较巧妙，也值得一看。递归式DP其实和记忆化搜索非常相似。
  42. 🔴 LCP 57：打地鼠。团体赛题目。自己写了一个$O(nlogk),k=1e9$的dp，但其实可以做到$O(n)$。问题的关键在于理解，以时间向前回溯dp，和用步数向前回溯其实都是对的。但前者慢一些（常数太大了），步数其实最多只需要回溯45步（3 * 3棋盘，最多4步可到任意位置，3 * 3 * 4=45）。

哈希表

  1. 🟢 219：存在重复元素II。滑动窗口+哈希表。
  2. 🟡 945：使数组唯一的最小增量值。把哈希表的线性探测思路应用到算法题目中。题解还结合了路径压缩。
  3. 🟡 694：不同岛屿的数量。非会员链接。本题提供了一个散列化思路，网格散列（岛屿轮廓形状）、路径散列（DFS路径）。如果形状一样，则DFS路径必定相等。可以直接用相对坐标写为字符串，作为散列值。
  4. 🔴 711：不同岛屿的数量II。非会员传送门。和694不同的地方在于这里会有旋转和翻转。其实这个就能很好的考验对于哈希的理解。只要换一个哈希思路，就能保证翻转、旋转不变性。即对形状坐标序列进行排序，并选择字典序最小的作为该形状的记录。

多指针 & 滑动窗口

  1. 🟡 2516：每种字符至少取K个。自己写了对保留部分长度进行二分的。题解是滑动窗口（双指针）效率更高。
  2. 🟢 26：删除数组重复项。输入已经有序，单向双指针扫描。
  3. 🟢 141：环形链表。快慢指针。如果链表中存在循环，一定会相遇。
  4. 🟢 27：移除元素。从左右两侧分别开始，将需要移除的元素覆盖。
  5. 🟡 3：无重复字符的最长子串。
  6. 🟡 15：三数之和。排序加对撞指针（双指针相向运动，一般只有输入有序时这样用）。值得二刷
  7. 🟡 16：最接近的三数之和。依然是排序加对撞。
  8. 🟡 238：除自身外的乘积。有的时候可以从复杂度要求思考方法。
  9. 🟡 18：四数之和。值得二刷。
  10. 🟡 1151：最少交换次数来组合所有的1。非会员链接。滑动窗口+前缀和。滑动窗口的关键之一就是如何设置窗口大小。
  11. 🟡 424：替换后的最长重复字符。DP明显会超时。而本题带有明显的区间的特征，可以考虑使用双指针解法，详见题解。注意其实当我们找到任意一种解之后，区间长度一定不会减小。
  12. 🔴 30：串联所有单词的子串。只要想到是滑动窗口（因为匹配目标长度固定），其实就很好办了。使用双hash，一个统计窗口内单词数，一个统计words中的单词数。遍历多种滑动窗口的起点即可。
  13. 🔴 32：最长有效括号。本题题解有动态规划、栈（括号匹配用栈非常好想）、双指针三种方案。其中贪心策略的双指针最为优越。括号的通用贪心策略：右括号多于左括号时，一定非法。

分治

  1. 🟢 70：爬楼梯。经典斐波那契问题。矩阵快速幂。
  2. 🟡 215：数组中第K个最大的元素。可以使用BFPRT算法，理论上更快，但是其实常数很高，也可以用小顶堆来实现，理论上复杂度高一些。
  3. 🟡 148：排序链表。进阶要求是$O(nlogn)$时间和$O(1)$的空间。只能使用自底向上的原地归并排序。

排序

  1. 🟡 220：存在重复元素III。使用滑动窗口+平衡树的方式可以很容易得到$O(nlogk)$的时间复杂度。但题解使用桶排序的思想来解决abs值是否在一个区间内的判断问题，需要判断当前桶和相邻桶。
  2. 🟡 355：设计推特。思考的时候可以参考下基础算法题。本体实际上是合并k个有序链表。

位运算

  1. 🟡 2397：被列覆盖的最多行数。二进制枚举，但是固定1的数量。可以进行Gosper’s-Hack优化。
  2. 🟢 231：2的幂。直接用n&n-1。
  3. 🟡 201：数字范围按位与。纯暴力遍历不可取。题解即求两个数字的二进制下的公共前缀，里面提到了用于去除二进制串最右侧1的，Brian Kernighan算法。
  4. 🟡 320：列举单词的全部缩写。非会员链接。可以用二进制运算，每个bit位代表是否用数字进行缩写，并最终输出。实现上比回溯的效率高很多。当然本质上还是$O(2^n)$。
  5. 🔴 1178：猜字谜。位运算+优化可以解决。32位以内的状态都可以很容易的用int的二进制位做存储，并和相同状态合并于一个内map计数。另外还利用$j=(j-1)&k$计算所有状态值k的二进制子集，由此利用谜底长度较少，子集数量较少的特性，快速遍历计数。详见题解。

并发

  1. 🟢 1114：按序打印。条件变量、锁。

图论

  1. 🔴 2846：边权重均等查询。想到了是LCA问题，但是没想到路径之后如何优化对路径的求解。这个题的思路非常值得思考，其实是图论、或者是树上问题的一个通用思路，就是如果一个问题的求解，满足结合律。比如两点之间的某种数值，满足结合律、交换律。那么就可以通过求解到同一个点的数值，再求差值来做到。例如求$f(a,b)$可能很难（或者时间复杂度很高），但是可以求$f(x,a)$和$f(x,b)$，再进行$f(x,a)+f(x,b)-2\timesf(0,x)$。另外本题也考察了LCA，必须使用优于朴素算法的解法。
  2. 🟡 1631：最小体力消耗路径。思考了很久，最终意识到仍然是一个特殊的单源最短路题目。每次取出可扩展路径中最短的一个，扩展该点，并将该点所有边加入最小堆中。重复此过程直到终点被加入。注意C++的优先队列，在使用std::less的情况下是大顶堆，如果需要自定义数据结构的小顶堆，可以自定义一个形如std::greater语义的二元比较函数comp，并priority_queue<your_struct, vector<your_struct>, decltype(comp)> small_queue;
  3. 🟡 721：账户合并。基础并查集题目。
  4. 🟡 1162：地图分析。很有代表性的一道题目，巧妙地把问题转换为多源点BFS。题解中甚至还有更精妙的DP解法。值得二刷。
  5. 🟡 207：课程表。拓扑排序。wiki。
  6. 🔴 332：重新安排行程。学习图论概念：欧拉图&半欧拉图&欧拉回路&半欧通路。Hierholzer算法题解。值得二刷。
  7. 🟡 310：最小高度树。自己写的是普通的BFS。题解中揭示了本题实际上是逐步删除度为1的节点，即拓扑排序。或者说这是一类，两端烧香求中点的题目。
  8. 🟡 743：网络延迟时间。基础款单源有向最短路。邻接表+djikstra+堆优化。
  9. 🟡 787：K站中转内最便宜的航班。K轮Bellman-Ford算法。
  10. 🔴 685：冗余连接II。树+并查集。根据冗余连接的不同情况，查找可以断开的边。
  11. 🔴 1168：水资源分配优化。非会员传送门。图论的经典思路：添加超级源点。通过引入超级源点，水井费用也成为一种普通的边。转化后就成为了最小生成树题目。
  12. 🔴 329：矩阵中的最长递增路径。经典转化思路：将原题目中的一些约束，修改为图论中点和点之间的边关系。而最长路径恰好可以用拓扑排序的方式进行计算（或者说是类似BFS的方式）。
  13. 🔴 675：为高尔夫比赛砍树。思路很简单，排序后找最短路。但复杂度也奇高。官方题解和民间题解都提到了优化问题，尤其是间隔搜索值得思考。更厉害的是分治法优化思路。值得二刷。
  14. 🔴 854：相似度为K的字符串。又是字符串变换转为图论变换的题目。本题的题解把字符移动理解为对边的变换。
  15. 🔴 1197：进击的骑士。非会员传送门。使用A*算法，给搜索添加启发式估计值作为排序规则的一部分。这个规则的主要目的是，不让100%恶化的情况入队。
  16. 🔴 2493：将节点分成尽可能多的组。本质上是求若干个连通子图各自的图直径。图的直径的算法就是两次BFS，第一次随机，第二次从第一次BFS最后入队节点开始。可以先用并查集对图做分割。
  17. 🔴 2603: 收集树中金币。看了题解，核心是对图做变换：剪枝、去叶子节点。思考最终路径的规则：任何一条路径最多只需要走两次，路径终点到（最远的）有金币的节点距离为2。因此变换有两条：递归删除所有无金币的叶子节点，对最终树进行2次删除叶子节点的操作。最终剩下的边，每个都会遍历。

数据结构

  1. 🟡 103：二叉树的锯齿形层序遍历。可以正常遍历记录层次遍历结果，再对中间结果进行后处理（隔行反转）。但题解中的方法更简便，对于这种需要调整遍历方向的，使用双向队列的方式更简便。
  2. 🔴 239：滑动窗口的最大值。$O(nlogn)$的大顶堆并不难想。但是题解提到了单调栈思想的双端队列。很有意思。在一个滑动窗口中，统计最大值，考虑一个更大的数加入之后所有更小数均可以从队尾弹出，另外超过窗口范围的大数从队首弹出，因此只需要用一个双端队列即可，能达到$O(n)$复杂度。
  3. 🔴 100213：按距离统计房屋对数目II。周赛，自己想写一个完全基于数学的分类讨论，但是漏洞百出。题解提供的思路是分类讨论，用差分数组统计。总之，差分数组是$O(n)$复杂度的好帮手，可以把若干次区间修改的时间复杂度大大简化。
  4. 🟡 2735：收集巧克力。名为中等，实为困难。自己写的是$O(n^2)$的动态规划，实际上本题有$O(n)$的单调栈+二次差分解法，思路比较复杂，参考题解。
  5. 🟡 2866：美丽塔II。思考过程是从暴力解法入手。很容易发现计算结果就是等价于构造一个递增/递减子数组，就很容易想到单调栈。主要的坑还是int和long long int的转型问题。
  6. 🔴 2276：统计区间中的整数数目。动态开点线段树标准题。记住一个思路，动态开点的根区间是整个区间范围，而不是一点一点扩大的（会出现树不平衡问题）。一个评论中提到的池化技术非常有趣，值得一看。
  7. 🔴 2132：用邮票贴满网格图。看的题解，非常典型的二维前缀和、二维差分数组的题目。凡是计算一个矩形区域，甚至更高维的一个区域，都可以用n维的前缀和。但这道题目更厉害的是对差分数组的理解。最终求是否存在一个点没有被覆盖过。这个时候实际上需要计算出所有点的覆盖次数（一个前缀和），为了求这个，可以先求出其差分数组，即某个顶点开始覆盖一个矩形（四个角分别+1、-1），在对其求和。
  8. 🔴 2454：下一个更大元素IV。自己写了一个单调栈，但是时间复杂度不够好，用记账法估计我觉得也是$O(n)$，但是常数很大。题解值得一看。实际上对于第二大，第三大，都可以用类似的方式解决。思考思路是，先找到第一大（用一个单调栈），将这些有第一大元素的值拿到一个优先队列或者单调栈中，然后再找这些已知有第一大元素的第二大元素。
  9. 🔴 2179：统计数组中好三元组数目。核心题解思路是，以变量y遍历第一个列表，视作三元组的中间元素，并统计第二个列表中，位于y前面的变量中，有多少也在第一个列表中y位置之前出现过。这个统计的信息，恰好可以用树状数组来进行维护。由此达到$O(nlogn)$。
  10. 🟢 496：下一个更大元素I。自己写的是$O(n^2)$，题解中推荐使用单调栈。
  11. 🟡 731：[我的日程安排]。看了题解，第一种是可以用两个set，分别存储无重叠时间段，和有一重重叠的时间段，新加入时间段不允许和一重重叠的时间段再重叠。另有题解边界计数，线段树基础题型，值得二刷。
  12. 🟡 654：最大二叉树。单调栈。
  13. 🟡 1395：统计作战单位数。暴力枚举中间值能过。学习以下题解使用离散化+树状数组高效解决。这里用的离散化方法是通过排序，确定其序号作为关键字。
  14. 🟡 109：从有序链表转换二叉搜索树。锻炼基础能力，熟悉前中后序遍历。值得二刷。
  15. 🟡 146：LRU缓存。LRU缓存是最近最少使用，按照使用时间戳排序。用一个链表，加一个哈希表即可。
  16. 🔴 84：柱状图中最大的矩形。经典单调栈题目。
  17. 🔴 42：接雨水。单调栈。思考的时候可以从三种基本简单情况开始：[2,1,2]，[2,1,3]，[3,1,2]。单调栈其实就是保留有用的单调信息，在出入栈的时候再进行统一计算的一种方法。
  18. 🔴 1157：子数组中占绝大多数的元素。线段树。树中维护的数据是BM众数投票算法的值。重点在于学会线段树。另外还有题解提到[树套树]解法(https://leetcode-cn.com/problems/online-majority-element-in-subarray/solution/wu-nao-shu-ju-jie-gou-zuo-fa-shu-tao-shu-by-wnjxyk/)。
  19. 🔴 23：合并k个排序链表。本题实际上是使用一个k个大小的小顶堆，每次出堆元素所在的链表继续入堆。
  20. 🔴 1354：多次求和构造目标数组。逆向思维，求生成的可能性很多，但是反方向的恢复方式只有一个。使用大顶堆，每次消去当前数组最大的数字，测试是否能反向恢复数组至初始状态。
  21. 🔴 432：全O(1)的数据结构。哈希表+链表。思路很简单。但是在prev、next、swap、iter_swap这方面受了半天苦。
  22. 🔴 460：LFU缓存。结合多种数据结构：散列表、链表、最小频率标记。按照频率设置不同链表存储键值是本题的精髓。
  23. 🔴 99：恢复二叉搜索树。还是中序Morris遍历。
  24. 🔴 440：字典序的第K小数字。数字顺序类题目大都需要思考顺序和数量之间的规律。自己的思路比较繁琐，是按位去生成的，一个数字除最高位是1~9，其他位均为0~9。数量可以逐位累加（如1是最高位的数字每一位分别可以有1，10，100，…）。题解更为简洁，建议学习。题解思路是从思考字符串的字典树构造开始，按照对树的遍历进行。
  25. 🔴 862：和至少为K的最短子数组。结合多种思路，前缀和（加速）+单调栈（因为有负数，不能简单滑动窗口）+二分（加速）。值得思考。
  26. 🔴 1606：找到处理最多请求的服务器。典型的多种数据结构配合。思考思路：需要有一个数据结构有序保存服务器当前任务结束时刻，还需要有一个数据结构有序保存空闲服务器序号。思维上不要局限于单一数据结构解决所有需求。
  27. 🔴 732：我的日程安排表III。经典线段树板子，需要动态增加节点。即抛弃build过程，在update过程中（具体就是push_down）过程中，进行原来的节点分裂。
  28. 🔴 2736：最大和查询。看了题解。还是线段树。同一下标的多维度的值也可以用线段树进行区间维护。线段树并不要求区间之间一定满足什么关系，看题目内容，可能要遍历很多的区间，必要的时候可以通过剪枝。其实仔细思考能发现本题的几个要点：和的极大值可以通过区间维护，两个加数的极小值/极大值也可以通过区间维护。如此就能通过排除

其他

  1. 🔴 LCP24：数字游戏。抄了题解，自己在想差分数组，完全想歪了。本题最厉害的是对数组的预处理。把求满足num[j]==num[j]+1的数组，转换为求令所有num[j]-j相等的数组，从而变成了求中位数，并进一步用对顶堆来解决。有两个题目和这个相关，分别是462：最小操作使数组相等II、295：数据流的中位数。
  2. 🟢 665：非递减数列。不简单的简单题，值得二刷。考虑情况要完整。
  3. 🟡 78：求全部子集。使用vector一定减少内存重分配。
  4. 🟡 169：找众数。Boyer-Moore投票算法。维护当前众数和计数器。相等+1，否则-1。变为0则更换数字。
  5. 🟡 287：寻找重复数。要求$O(n)$复杂度。题解使用等价变换+Floyd判圈法，值得二刷。
  6. 🟡 138：复制带随机指针的链表。题解方法非常有趣，原地将链表复制一遍，变为a->a'->b->b'->…->nil。然后再对random域赋值。这种原地操作的思路值得思考。
  7. 🔴 41：缺失的第一个正数。题目给出了$O(n)$时间，$O(1)$的空间限制。但是输入数组是可以使用的空间。由于寻找正整数，所以忽略负数。原地排序新思路，一个萝卜一个坑，把数字移动到自己的位置上，最后遍历看哪里的下标不是自己。
  8. 🟡 29：两数相除。非常基础的题目，一点快速乘的思想就可以。但是非常考验对于边界溢出情况的考虑。由于负数范围大于正数，实际上我更推荐把数字全转为负数再进行运算和分类讨论（而不是转为正数），转为无符号也行。另外最好单独处理INT_MIN/1和INT_MIN/-1这两种情况。
  9. 🟡 50：Pow(x,n)。快速幂，但n是int全范围。注意INT_MIN。
  10. 🔴 780：到达终点。典型的逆向思维的题。当题目中有以初始状态，变换到结束状态这种描述时，就可以思考是否从结束到初始进行计算是更为简便的。