力扣题目收藏
虽然现在做得不多了，但还是能碰到一些很有意思的题目，在这里记录一下（力扣的收藏夹比较简陋）。
5. 最长回文子串
这里有一个时间复杂度为 O(n) 的 Manacher 算法。
28. 实现 strStr()
题目本身没有难度，但是在题解中介绍的KMP算法可以将时间复杂度降为 O(n+m) 。 这个算法在字符串类的题目中可能较常出现。
137. 只出现一次的数字 II
这道题由于每个数（除了一个特殊的数）出现的次数为3次，故不能使用基本的异或求解。
换一个角度想，基本的异或就是实现了2进制，而这道题需要实现的是3进制。 因此，可以考虑使用两个数（每1位用两位字节来进行计数），实现3进制的计算。
从题解可知，这种方法是数字电路设计里的基本知识。先列举出真值表，再画出电路。
这种方法也可以推广到n进制。
229. 多数元素 II
这道题是“Boyer-Moore投票法”的经典实现， 该方法可以在线性时间复杂度内找到所有可能是“多数元素”的数。
该方法的逻辑如下：当需要寻找频率大于1/n的数时，满足条件的数最多为n-1个， 于是我们在遍历数组时保留n-1个不同的数并统计其出现次数，当出现第n个不同的数时， 则将前面n-1个数的出现次数都减1，并删除频率为0的数。
因此，该方法找到的数是有限的（最多n-1个），可以证明该方法是删选“多数元素”的必要条件。 随后我们只需要再次遍历数组判断每一个候选数是否为“多数元素”即可。
307. 区域和检索 - 数组可修改
这道题可以使用树状数组或线段树。 这两种数据结构都能够更新并查询区间内的最小值、最大值或者总和等信息， 但是树状数组的查询区间必须从首项开始，而线段树可以是任意区间。 在空间占用上，当数据数量n为2的次方项时，树状数组的空间复杂度为O(n)，线段树为O(2n)。
周赛题 6206. 最长递增子序列 II 可用线段树模版。
382. 链表随机节点
该题目询问是否可以不使用额外的空间实现对链表元素对随机选择。 在题解中给出了“水塘抽样”这个用时间换空间的概率学方法。
当然，这个抽样方法的应用场景也很少见。
386. 字典序排数
这道题虽然是常见的BFS，但是枚举边界条件需要手动排几个找一下规律。
432. 全 O(1) 的数据结构
这是一道设计数据结构的题，要求在索引时间为 O(1) 的情况下，在 O(1) 的时间中返回最大最小元素。 因此，可以使用双向链表存储有效的出现频率以及各自对应的元素，同时建立一个哈希表实现数据的反查。
458. 可怜的小猪
这道题涉及到香农信息论中的定理，具有一个非常简洁的计算公式。
1044. 最长重复子串
这解答道题之前可以先考虑一个子问题：是否存在长度为k的重复子串。 如果能在 O(n) 内解答这个子问题，那么通过二分查找k，即可在 O(nlog n) 内解答这道题。
题解中提到了一个 Rabin-Karp 字符串编码方法， 该方法可以在一个字符串哈希的基础上通过简单的计算得到与之重叠的字符串的哈希， 因此可以在线性时间内实现所有子字符串的哈希计算。
1483. 树节点的第 K 个祖先
这道题比较经典，也是通过构造二分查找表来解决，在知道思路后就没什么难点了。
1719. 重构一棵树的方案数
这道题首先得做阅读理解：树中所有的父子关系都出现在了pair中。
然后需要思考下面两个问题：什么情况下存在有效的树？什么情况下具有多个有效答案？
这道题思路比较复杂，难度很大，目前来看也没有什么比较通用的知识点，可以在没事的时候重新看看。
2029. 石子游戏 IX
这道题就是找规律，根据处以3的余数，可以将所有的石子划分为3种类型。 当不考虑余数为0的类型时，为了不让自己立即输掉比赛，根据当前的情况只可能有1种选择。 也就是说，当起点的石子确定以后，后续的石子就也确定了。 最后通过归纳即可得到答案。
2353. 设计食物评分系统
这题也是设计数据结构，考虑到排序比较的对象有两个，最方便的法子就是使用现成的set