LeetCode刷题精选篇

2020年09月20日

Author: Guofei

文章归类: 8-数据结构与算法，文章编号: 590

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2020/09/20/lc.html

Edit

数学类

数学类的解法一般泛用性低，但巧妙。

水库算法

有一个链表，我们不知道其长度，设计一个算法对其节点做均匀随机采样。要求最多做一次遍历。

水库算法：遍历这个链表，在遍历到第i个节点时，有 1i1i 的概率选择这个节点覆盖掉之前的节点选择。
(整个算法只需要遍历一次)

水库算法随机性的证明：
长度为n的链表，第i个节点被选中的充要条件是：第i个节点被选中，并且之后遍历第i+1到n个节点时，都未被替换。

这个概率就是 1i×ii+1×i+1i+2×…×n−1n=1n1i×ii+1×i+1i+2×…×n−1n=1n

技巧类

最大回文

基础方法:遍历，第i到j是否是回文，遍历过程复杂度 O(n2)O(n2)，判断是否是回文复杂度是 O(n) ，全局复杂度 O(n3)O(n3)

改进1:遍历一次，每个值是回文的中心，复杂度是O(n)，判断回文的复杂度O(n)，全局复杂度是 O(n2)O(n2)

改进2:假设已经判断出n点左右各l距离是回文，那么右边n+l范围内是否是回文其实与左边n-l范围内的情况完全一样。那么n到n+l这个范围内的情况就不用判断了。

改进3:其实回文可以是奇数或偶数，只需要隔板插入一个字符串即可统一为一种算法。复杂度 O(n)

40亿个单词找某个单词，并且给定某个前缀，找到多少个单词的前缀是这个

其实就是 trie 树

不用1个节点对应1个字母，也可以1个节点对应一段字母。例如，in-intrest-intrested/interesting，这样。

40亿个数字找TOP1000

遍历40亿个数字，维护一个TOP1000的堆

如果允许多台机器，可以上分布式，每个 partition 求 top1000，最后合并

B+树基本知识

底层是mysql，redis是缓存；dao层操作mysql，cache层操作redis

如果某个sql查询比较慢，怎么办？
如果条件字段有索引，建立索引
mysql底层是 B+ 树，查询复杂度 log(n)
如果用 hash，复杂度是 O(1)

您的支持将鼓励我继续创作！

LeetCode刷题精选篇