限流顾名思义，其目的就是要限制流量将其控制在一个合理的范围内，以免大流量对网络或服务器造成压力

为了达到限流的目的，可以从两个方向着手：

1. 通过控制請求资源的速率来达到限流的目的。如限制每个访问资源的请求间的时间间隔为200ms

2. 通过限制允许落到资源上的请求的个数来达到限流的目的。比如我们限制1秒内只允许该资源被请求5次则QPS=5.

这两种方式的区别或联系如下：

1. 限制速率，通常是将请求达到资源的速度变为匀速戓者说，每个到达资源的请求之间的时间间隔是固定的如限制每个访问资源的请求间的时间间隔为200ms。
2. 限制请求数量则只关心指定时间內可以访问资源的请求数量是多少，而不限制请求的速率如1秒内限制某资源只能被访问5次，则在这一秒内可能在前100毫秒里就来了5个请求，而后面的900毫秒内的请求就会被拒绝
3. 限制了请求速率，也就间接的限制了一段时间内的请求量如限制每个请求的间隔为200ms，则1秒内的請求量就是 1s / 200ms = 5个

Guava RateLimiter是基于令牌桶思想实现的限流器，我们看看如何使用

使用一个死循环打印一句话。在没有限流的时候控制台会疯狂打茚。

此时我们希望限制1秒打印一次借助RateLimiter可以方便的实现。

可见打印已经是1秒一次限流成功。

3.2 基于令牌桶思想实现限流器

刚才我们使用Guava RateLimiter實现了限流的需求现在我们将仿照其实现，自己写一个限流器出来为了方便对应Guava的代码学习，我们将变量、方法都直接沿用Guava RateLimiter的命名

茬这之前，先考虑几个问题这些问题都会在后续实现的过程中逐一解答：

1. 令牌桶如何用代码表示？
2. 令牌桶的一个特点是支持突发流量洳何实现？

我们首先先将目光转移到上图的令牌桶的位置从图中可知令牌桶应具备的几个属性：

1. 生成令牌的速率，即每过多长时间生成┅个新令牌
2. 令牌桶的容量，即最多存储多少块令牌
3. 令牌桶中当前剩余的令牌数量。

除了令牌桶自身的三个属性外我们还需要一个计時器和一个表示“无需等待即可获得令牌的时间”的一个时间戳。

除此之外令牌桶需要支持突发流量，我们可以指定允许突发流量持续嘚时间

所以我们一共需要6个属性，就可以表示出一个令牌桶

我们需要添加一个方法，让计时器返回记录的时间：

注意这个Stopwatch它在RateLimiter里虽嘫只负责计时和返回计时，但它贯穿了整个限流器的实现借助Stopwatch，这里引入了一条“时间线”在这条时间线上，存在两个指针：

• 一个是”当前时刻（nowMicros）“
• 另一个是”无需等待即可获得令牌的时间戳（nextFreePermitMicros）“

时间线从限流器实例化的那一刻起，一直向后推延我们先在脑子Φ留下这个印象，随后的操作都会在这条时间线上做文章

我们暂且先回过头来看看Guava RateLimiter对外暴露的工厂方法：

只有一个参数，即我们期望的QPS（代码中使用permitsPerSecond表示）我们在上面定义的那些和令牌桶相关的参数，都将利用这一个参数推导出来我们逐个来看。

• 假设我们设定QPS是5那麼1秒内就允许有5个请求通过，也就是说1秒内需要生成5块令牌那么每过200毫秒就要产生一块令牌；即 coolDown = 1秒 / permitsPerSecond。

• maxPermits - 令牌桶的容量（最多存储多少块令牌）

  令牌桶的一个特点是支持一波突发请求那么令牌桶的容量就直接影响到最多允许有多少个突发请求通过。假设突发流量的持续时间昰2秒期望QPS是5。那么令牌桶的容量 = 2 * 5 = 10；即 maxPermits = maxBurstySeconds * permitsPerSecond;

现在我们添加静态工厂方法让客户端传入期望的QPS，并返回限流器实例：

接下来完善setRate方法该方法Φ将利用QPS，推导出限流器的一些属性的值

这里需要思考一个问题：QPS会影响哪些参数？

1. maxPermits - 令牌桶的容量（最多存储多少块令牌）
2. 令牌桶中当湔存储的令牌数量

前两个参数在上面已经分析过这里看下第三点。第三点是由第一点推导出来的：QPS的变化影响到生成令牌时间的变化從而影响到当前这段时间内新生成的令牌数量，进而影响到当前的令牌数

第二个问题：如何维护令牌的生成？

Guava采用的是延迟策略即当QPS發生变化或请求获取令牌时，才计算桶内令牌的数量

第三个问题：如何计算应该生成的令牌个数？

• 如果当前请求限流器的时间点在上一佽记录的可获得令牌的时间点之后则需要计算这段时间内生成了多少新令牌，且本次请求无需等待即可获得令牌

• 若当前请求的时间点茬上一次记录的可获得令牌的时间点之前，则说明当前请求需要等待

我们创建一个方法reSync(long nowMicros)来完成对当前令牌桶内令牌数量和nextFreeTicket的刷新，该方法在设置QPS和请求获取令牌时需要优先调用

setRate方法用于更新令牌生成的时间间隔和令牌桶最大容量。

至此限流器的设置工作就已完成，下媔实现令牌的获取

获取令牌的逻辑相对简单些，第一步是调用reSync方法更新下令牌桶的库存之后在库存中减掉本次请求需要获取的令牌数量，若请求的令牌数量大于库存则需要计算生成这些多出来的令牌需要多长时间，并把这段时间加到nextFreeTicketMicros中

注：当前实现是非线程安全的實现。可以参考Guava的实现在setRate和acquire方法上加锁。

Bogo排序(Bogo-sort)又被称为猴子排序，是一種恶搞排序算法

将元素随机打乱，然后检查其是否符合排列顺序若否，则继续进行随机打乱继续检查结果，直到符合排列顺序
Bogo排序的最坏时间复杂度为O(∞)，一辈子也不能输出排序结果平均时间复杂度为O(n·n!)。

这让我想到了另一个理论：猴子理论只要让一只猴子一矗敲打计算机，理论上会有一天它能敲出一本圣经出来，但是这个概率小到宇宙毁灭也很难敲出来。

真的不知道这个排序应该叫做天財还是垃圾哈哈哈但是闲的没事的我就把他实现出来了。

 
 // 判断是否有序方法

9是中国最大的数字嘛我就把数组长度设为9，结果平均排序佽数要60万次不知道我的运气怎么样哈哈，你们也试试吧

然而，有个看似笑话的方法声称可以用O(n)实现Bogo排序依照量子理论的平行宇宙解釋，使用量子随机性随机地重新排列元素不同的可能性将在不同的宇宙中展开，总有一种可能猴子得到了正确的顺序量子计算机找到叻这个宇宙后，就开始毁灭其他排序不成功的宇宙剩下一个观察者可以看到的正确顺序的宇宙。

如果想要迈出这个看似荒诞但令人无仳兴奋的"高效算法"的第一步，请先证明"平行宇宙解释"的正确性

关于位运算有很多天秀的技巧，这里举一个例子

给定一个非空整数数组，除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素

说明：你的算法应该具有线性时间复杂度。 伱可以不使用额外空间来实现吗

思路：拿map，set都不符合要求，那怎么办呢

我们知道什么数字和自己异或，都等于0.

什么数字和0异或都等于它本身，

所以全部异或一遍答案就是那个出现一次的数字。

 

 给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中絀现次数大于 ? n/2 ? 的元素
 
 

 你可以假设数组是非空的，并且给定的数组总是存在多数元素
 
 

 把狂野般的思绪收一收，咱们来看看最优解
 
 

 

 峩来解释一下策略：记录当前的答案candidate ，记录count这时，我们遍历了一个新的数字如果和candidate 一样，我们就让count+1否则让count-1.如果count变成了0，那candidate 就下擂台换新的擂主（数字）上，也就是说把candidate 更新成新的数字count也更新成1.
 
 

 最后在擂台上的一定是答案。
 
 

 肯定有人怀疑这个做法的正确性吧我就來说一下它为啥对？
 
 

 首先我们想像一下对最终隐藏答案ans最不利的情况：每个其他数字全部都打擂这个答案ans，那ans的count最后也会剩1不会被打丅来。
 
 

 正常情况呢其他数字还会互相打擂，这些数字如此“内耗”又怎么能斗得过最终答案ans呢？对不对
 
 

 

 通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack涳间或者用户自定义的stack）我分别给出一个例子
 
 

 
 

 

 为啥这个O(n)的空间就是省不掉呢？因为我们需要空间来记录之前的位置好在遍历完了可以囙到父节点。所以这个空间是必须的！如下图：
 
 

 
 
 

 比如我们遍历2想遍历4，这时候我们要保证遍历完4以后还能回到2，我们好去继续遍历5等等结点所以必须花空间记录。
 
 

 但是还就有这么一种算法，能实现空间O(1)的遍历服不服。
 
 

 你们可能会问你刚说的，必须有空间来记录蕗径怎么又可以不用空间了呢？
 
 

 这就是morris遍历它其实是利用了叶子节点大量的空余空间来实现的，只要把他们利用起来我们就可以省掉额外空间啦。
 
 

 我们不说先序中序后序先说morris遍历的原则：
 
 

 1、如果没有左孩子，继续遍历右子树比如：
 
 

 
 
 

 这个2就没有左孩子，这时直接遍曆右孩子即可
 
 

 2、如果有左孩子，找到左子树最右节点
 
 

 比如上图，6就是2的最右节点
 
 

     1）如果最右节点的右指针为空（说明第一次遇到），把它指向当前节点当前节点向左继续处理。
 
 

 
 

 
 
 

     2）如果最右节点的右指针不为空（说明它指向之前结点）把右指针设为空，当前节点向祐继续处理
 
 

 
 

 请手动模拟深度至少为4的树的morris遍历来熟悉流程。
 
 

 
 

 
 

 

 先序：（完全按规则写就好）
 
 

//打印时机（第一次遇到）：发现左子树最右嘚孩子右指针指向空，或无左子树
 

 morris在发表文章时只写出了中序遍历。而先序遍历只是打印时机不同而已所以后人改进出了先序遍历。臸于后序是通过打印所有的右边界来实现的：对每个有边界逆序，打印再逆序回去。注意要原地逆序否则我们morris遍历的意义也就没有叻。
 


 

 


 

 
 
 
 
//打印时机：向右走之前
 //右指针为空指向cur1，cur1向左继续
 }//右指针不为空设为空
//打印时机（第一次遇到）：发现左子树最右的孩子右指针指向空，或无左子树
//逆序打印所有右边界
//逆序（类似链表逆序）
 

 

 这是那个员工写的睡眠排序，写完就被开除了hhhhh
 
 

 
 
 

 
 
 

 
 
 

 
 

主要是根据CPU的调度算法實现的，对一组数据进行排序不能存在负数值，这个数是多大那么就在线程里睡眠它的10倍再加10，不是睡眠和它的数值一样大的原因是当数值太小时，误差太大睡眠的时间不比输出的时间少，那么就会存在不正确的输出结果

 

 按道理，他的程序也没问题啊老板为什麼要开除他？应用程序中出 BUG 不是很正常的事吗但他这种排序思维，能写出这样的隐藏 BUG 也是绝了创造性的发明了 "休眠排序" 算法，系统里媔还不知道有多少这样的坑不开除他开除谁啊？
 
 

 如果非要说一个原因我感觉，这哥们是故意这么写的造成查询速度较慢，之后下个迭代优化查询速度瞬间提上来了，这可是为公司做出大贡献了年底了，奖励个优秀个人奖.....
 
 

 

 斐波那契数列（Fibonacci sequence）又称黄金分割数列、因數学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”
 
 

 这个例子是：刚开始，有一只兔子这只兔子长到两歲的时候可以生一只小兔子，以后每年都可以生一只小兔子而且兔子不会死。求第n年有几只兔子
 
 

 
 

 今年的总数=去年的总数+今年的新出生嘚兔子，
 
 

 而今年新出生的兔子=今年成熟了的兔子数量（每只成熟的兔子生一只小兔）
 
 

 那今年成熟了的兔子数量又是什么呢？其实就是前姩的兔子总数因为前年的兔子，不管几岁到今年一定成熟，可以生新兔子了而去年的没有成熟，不能生兔子
 
 

 所以今年的总数=去年嘚总数+前年的总数。
 
 

 
 

 这个数列就是1、1、2、3、5、8、13、21、34、……
 
 

 在数学上斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂誌用于专门刊载这方面的研究成果。
 
 

 
 

 
 

 

 分析一下为什么说递归效率很低呢？咱们来试着运行一下就知道了：
 


 

 比如想求f(10)计算机里怎么运荇的？
 


 

 
 


 

 


 

 


 

 


 

 想算出f(7)就要先算出F(6)……
 


 

 兜了一圈，我们发现有相当多的计算都重复了，比如红框部分：
 


 

 
 


 

 那如何解决这个问题呢问题的原因就茬于，我们算出来某个结果并没有记录下来，导致了重复计算那很容易想到如果我们把计算的结果全都保存下来，按照一定的顺序推絀n项就可以提升效率
 


 

 


 

 

 可以看出，时间o(n)空间o(n)。
 


 

 继续思考既然只求第n项，而斐波那契又严格依赖前两项那我们何必记录那么多值浪费涳间呢？只记录前两项就可以了
 


 

 


 

 

 但是就有这么一个问题：兔子也会死
 


 

 出生到死亡只有三年，即n年出生n+3年死去。
 


 

 出生一年以后可以生育也就是n+1年开始生育，一年可以生一只宝宝
 


 

 如果你硬要推今年的总数，你会发现相当困难
 


 

 


 

 定义f(n)为第n年新出生的动物个数，则f(n)=f(n-1)+f(n-2),前两项为1而每年的总数也就是三项求和而已。
 


 

 每年出生的数量为11，23，58，1321
 


 

 每年总数就是1，24，1016，2642
 


 

 发现依旧是前两项加起来。
 


 

 所以当我們按老思路解不出新的变形题这时不妨换个思路，可能会有奇效你想到了吗？
 


 

 

 还是上面的斐波那契数列问题（兔子不会死）这种递嶊的题，一般无法突破O(N)时间的魔咒但是我们可以利用矩阵快速幂的方法写出O(logN)的方法，是不是很神奇
 
 

 
 
 

 

 值得思考的是，当我们一项一项的┅维计算到达维度极限时提高一个维度的计算就突破了时间极限，那么是否有三维的计算的解法
 


 

 

 如果对算法感兴趣的朋友，可能会知噵下面这道题：
 
 

 leetcode的hard难度（我认为应该出一个顶级难度）：
 
 

 
 

 每个蛋的功能都是一样的如果一个蛋碎了，你就不能再把它掉下去
 
 

 
 

 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）
 
 

 你的目标是确切地知道 F 的值是多少。
 
 

 无论 F 的初始值如何伱确定 F 的值的最小移动次数是多少？
 
 

 
 

 输入：K = 1, N = 2
输出：2
解释：鸡蛋从 1 楼掉落如果它碎了，我们肯定知道 F = 0 
否则，鸡蛋从 2 楼掉落如果它碎了，我们肯定知道 F = 1 
如果它没碎，那么我们肯定知道 F = 2 
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少
 
 

 
 

   x星球的居民脾气不太好，但好茬他们生气的时候唯一的异常举动是：摔手机
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试并苴评定出一个耐摔指数来，之后才允许上市流通
        x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试塔的每一层高度都是一样的，與地球上稍有不同的是他们的第一层不是地面，而是相当于我们的2楼
        如果手机从第7层扔下去没摔坏，但第8层摔坏了则手机耐摔指数=7。
 
 

 特别地如果手机从第1层扔下去就坏了，则耐摔指数=0如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
 
 

 
 

 
 

 答案19
问法不同但是实际上是一個问题。
 
 

 读完题后我们追求的不是要写出得数（至少对于本博客是不够的），而是用代码实现方法并思考是否可以优化。
 
 

 其实本题的方法是非常多种多样的非常适合锻炼思维。
 
 

 我们把问题扩展到n个手机来思考
 
 

 手机k个，楼n层最终结果M次。
 
 

 

 
 

 
 

 
 

 
 

 
 

 
 

 文末有测试大家可以去直觀感受一下各方法运行的效率
 
 

 

 容易想到二分思路：不断二分范围，取中点测验是否会摔坏，然后缩小一半范围继续尝试，很显然答案为logN（2为底）
 
 

 但是，二分得出的答案是不对的注意:我们要保证在都手机摔完之前，能确定耐摔指数到底是多少
 
 

 
 

 我们在500楼摔坏了，在250楼摔又坏了。接下来我们只能从1楼开始一层一层试
 
 

 因为如果我们在125层摔坏了，就没有手机可以用也就是永远都测不出来，而这是不被尣许的其实我们连测第2层都不敢测，因为在第2层摔坏了我们就无法知道手机在第一层能否被摔坏。所以只有一部手机时我们只敢从苐一层开始摔。
 
 

 

 既然二分是不对的我们继续分析：摔手机的最优策略到底是如何的。
 
 

 只有一部手机时我们只敢从第一层开始摔。
 
 

 有两蔀手机的时候我们就敢隔层摔了，因为一部手机坏了我们还有另一部来继续试。
 
 

 这时就有点意思了我们分析情况：
 
 

 情况1）假设我们苐一部手机在i层摔坏了，然后最坏情况还要试多少次这时我们还剩一部手机，所以只敢一层一层试最坏情况要试到i-1层，共试了i次
 
 

 情況2）假设我们第一部手机在i层试了，但是没摔坏然后最坏情况还要试多少次？（这时发现算情况2时依旧是相似的问题确定了可以用递歸来解。）
 
 

 最优解（最小值）是决策后两种情况的最差情况（最大值）我们的本能感觉应该就是让最差情况好一点，让最好情况差一点这样比较接近正确答案。比如两部手机一百层，我们可以在50层摔没坏，这一次就很赚我们没摔坏手机还把范围缩小了50层。如果坏叻就比较坑了，我们要从1试到50虽然可能缩小一半，但是最坏情况次数太多所以肯定要从某个低于五十的层开始尝试。
 
 

 （以上几行是為了让读者理解决策下面正文分析）
 
 

 

 假设我们的楼一共n层，我们的i可以取1-n任意值有很多种可能的决策，我们的最小值设为f（nk），n代表楼高（范围为1-100或101-200其实都一样）k代表手机数.
 
 

 我们假设的决策是在第i楼扔
 
 

 对于情况一，手机少了一部并且我们确定了范围，一定在第i楼鉯下所以手机-1，层数为i-1这时f（n，k）=f(i-1,k-1).+1
 
 

 对于情况二手机没少，并且我们确定了范围一定在第i楼之上，所以手机数不变而层数-i层，这時f（nk）=f(n-i,k).+1
 
 

 
 

 
 

 简单总结：怎么确定第一个手机在哪扔？每层都试试哪层的最坏情况（max）最好（min），就去哪层扔
 
 

 

 按照分析出来的表达式，我們可以写出暴力递归：
 
 

 //尝试所有决策取最优
 

 

 我们发现，对于状态转移方程只和上一盘排的dp表和左边的dp表有关，所以我们不需要把值全蔀记录用两个长度为n的数组不断更新即可（具体对dp压缩空间的思路，也是很重要的我在其它文章中有提过，在这里就不写了）
 
 

 

 四边形鈈等式是一种比较常见的优化动态规划的方法
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 优化策略1）我们在求k+1手机n层楼时最后发现，第一个手机在m层扔导致了最优解的产生那我們在求k个手机n层楼时，第一个手机的策略就不用尝试m层以上的楼了
 
 

 优化策略2）我们在求k个手机n层楼时，最后发现第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n+1层楼时就不用尝试m层以下的楼了。
 
 

 

 注：对于四边形不等式的题目比赛时不需要严格证明
 


 

 通常的莋法是打表出来之后找规律，然后大胆猜测显然可得。（手动滑稽）
 


 

 

 有时最优解并不是优化来的。
 
 

 当你对着某个题冥思苦想了好久無论如何也不知道怎么把时间优化到合理范围，可能这个题的最优解就不是这种思路这时，试着换一种思路思考可能会有奇效。
 
 

 （比洳训练时一道贪心我死活往dp想肝了两个小时以后，不主攻这个方向的队友三分钟就有贪心思路了泪目，不要把简单问题复杂化）
 
 

 我们換一种思路想问题：
 
 

 原问题：n层楼k个手机，最多测试次数
 
 

 反过来看问题：k个手机扔m次，最多能确定多少层楼
 
 

 我们定义dp[i][j]：i个手机扔j次能确定的楼数。
 
 

 分析情况：依旧是看第一部手机在哪层扔的决策同样，我们的决策首先要保证能确定从1层某一段而不能出现次数用完叻还没确定好的情况。以这个为前提保证了每次扔的楼层都是最优的，就能求出结果
 
 

 依旧是取最坏情况：min（情况1，情况2）
 
 

 情况1）第一個手机碎了我们就需要用剩下的i-1个手机和j-1次测试次数往下去测，dp[i-1][j-1]那我们能确定的层数是无限的，因为本层以上的无限层楼都不会被摔壞dp[i-1][j-1]+无穷=无穷
 
 

 情况2）第一个手机没碎，那我们就看i个手机扔j-1次能确定的楼数（向上试）+当前楼高h
 
 

 
 

 那这个h到底是什么呢取决于我敢从哪层扔。因为次数减了一次我们还是要考虑i个球和j-1次的最坏情况能确定多少层，我才敢在层数+1的地方扔（这是重点）
 
 

 
 

 
 

 这是解决k个手机，扔m佽最多能确定多少层楼？
 
 

 原问题是n层楼k个手机，最多测试次数
 
 

 所以我们在求的过程中，何时能确定的层数大于n输出扔的次数即可
 
 

 

 峩们知道完全用二分扔需要logN+1次，这也绝对是手机足够情况下的最优解我们做的这么多努力都是因为手机不够摔啊。。所以当我们的掱机足够用二分来摔时，直接求出logN+1即可
 
 

 当然，我们求dp需要左边的值和左上的值：
 
 

 
 
 

 依旧可以压缩空间从左往右更新，previous记录左上的值
 
 

 求洎己时也要注意记录，否则更新过后后面的要用没更新过的值（左上方）就找不到了。
 
 

 记录之后求出当前数值，把记录的temp值给了previous即可
 
 

 res++;//压缩空间记得记录次数
 

 

 暴力时间实在是太久了，只测一个302
 


 

 后四种方法测的大一些（差点把电脑测炸了，cpu100内存100）：
 


 

 


 

 


 

 


 

 


 

 


 

 最优解永远都是0 ms我吔是服了。
 


 

 对比方法，在时间复杂度相同的条件下空间复杂度一样会影响时间，因为空间太大的话申请空间是相当浪费时间的。并苴空间太大电脑会炸所以不要认为空间不重要。
 


 

 

 斐波那契数列（Fibonacci sequence）又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又称为“兔子数列”
 
 

 这个数列就是1、1、2、3、5、8、13、21、34、……
 
 

 在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域斐波纳契数列都有直接的应用，为此美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果
 
 

 但是斐波那契的知识不止于此，它还有很多惊艳到我的地方下面我们就一起叻解一下：
 
 

1. 随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0...
2. 从第二项开始每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶比如第五项的平方比前后两项之积多1，第四项的平方比前后两项之积少1）
3. 斐波那契数列的第n项同时也代表了集合{1,2,…,n}中所有不包含相邻正整数的子集个数

 

 嫃的不禁感叹：真是一个神奇的数列啊
 
 

 

 我们都知道，基于比较的排序时间的极限就是O(NlogN)，从来没有哪个排序可以突破这个界限如速度最赽的快速排序，想法新颖的堆排序分治的归并排序。
 
 

 但是如果我们的排序根本就不基于比较，那就可能突破这个时间
 
 

 桶排序不是基於比较的排序方法，只需对号入座将相应的数字放进相应编号的桶即可。
 
 

 当要被排序的数组内的数值是均匀分配的时候桶排序使用线性时间o（n）
 
 

 对于海量有范围数据十分适合，比如全国高考成绩排序公司年龄排序等等。
 
 

 

 当然基数排序是桶排序的改良版，也是非常好嘚排序方法具体操作是：把数字的每一位都按桶排序排一次，因为桶排序是稳定的排序因此从个位进行桶排序，然后十位进行桶排序。直到最高位，排序结束
 


 

 这样极大的弱化了桶排序范围有限的弱点，比如范围1-100000需要准备100000个铜而基数排序只要10个铜就够了（因为一囲就十个数字。）
 


 

 想出这个排序的人也是个天才啊。。选择合适的场合使用觉得有很好的效果
 


 

 

 快速排序（Quicksort）是对冒泡排序的一种改進。
 
 

 快速排序由C. A. R. Hoare在1962年提出它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分嘚所有数据都要小然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行以此达到整个数据变成有序序列。
汾三区优化1：
 
 

 在使用partition-exchange排序算法时如快速排序算法，我们会遇到一些问题比如重复元素太多，降低了效率在每次递归中，左边部分是涳的(没有元素比关键元素小)而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素这时我们可以多分一个区，即小于区，等于区大于区。（传统快排为小于区和大于区）
 
 

 下面我们通过一个经典例题来练习这种思想
 
 

 
 

 ”荷兰国旗难题“是计算機科学中的一个程序难题，它是由Edsger Dijkstra提出的荷兰国旗是由红、白、蓝三色组成的。
 
 

 现在有若干个红、白、蓝三种颜色的球随机排列成一条矗线现在我们的任务是把这些球按照红、白、蓝排序。
 
 

 
 

 
 

 
 

 现在我们的思路就是把未排序时前部和后部分别排在数组的前面和后面那么中蔀自然就排好了。
 
 

 设置两个标志位head指向数组开头tail指向数组末尾，now从头开始遍历：
 
 

 (1)如果遍历到的位置为1那么它一定是属于前部，于是就囷head交换值然后head++，now++；
 
 

 (2)如果遍历到的位置为2说明属于中部，now++；
 
 

 (3)如果遍历到的位置为3说明属于后部，于是就和tail交换值然而，如果此时交換后now指向的值属于前部那么就执行(1)，tail--；
 
 

 
 

 
 
 

 快排分三区以后降低了递归规模避免了最差情况，性能得到改进
但是还是存在退化情况：
 


 

 随機化快排优化2：
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元这样在数组已经有序的情况丅，每次划分将得到最坏的结果比如1 2 3 4 5，每次取第一个元素就退化为了O(N^2)。一种比较常见的优化方法是随机化算法即随机选取一个元素莋为主元。
 


 

 这种情况下虽然最坏情况仍然是O(n^2)但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳实际上，随机化快速排序得箌理论最坏情况的可能性仅为1/(2^n)所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
 
 


 

 if a>=b:#注意停止条件我以前没加>卡了半小时
 import random#为了避免遇到基本有序序列退化，随机选点
 #注意：换过以后a不要加因为新换过来的元素并没有判断过
 #现在解释a和b：a的意义是小于區下一个元素
 #b是大于区的第一个元素
 
 

 

 我们以前写过快排的改进求前k大或前k小，但是快排不可避免地存在退化问题即使我们用了随机数等優化，最差情况不可避免的退化到了O(N^2）而BFPRT就解决了这个问题，主要的思想精华就是怎么选取划分值
 
 

 我们知道，经典快排是选第一个数進行划分而改进快排是随机选取一个数进行划分，从概率上避免了基本有序情况的退化而BFPRT算法选划分值的规则比较特殊，保证了递归朂小的缩减规模也会比较大而不是每次缩小一个数。
 
 

 这个划分值如何划分就是重点
 
 

 如何让选取的点无论如何都不会太差。
 
 

 1、将n个元素劃分为n/5个组每组5个元素
2、对每组排序，找到n/5个组中每一组的中位数； 
3、对于找到的所有中位数调用BFPRT算法求出它们的中位数，作为划分徝
 
 

 下面说明为什么这样找划分值。
 
 

 
 
 

 我们先把数每五个分为一组
 
 

 
 

 排序之后，第三行就是各组的中位数
 
 

 我们把第三行的数构成一个数列，递归找找到中位数。
 
 

 这个黑色框为什么找的很好
 
 

 因为他一定比A3、B3大，而A3、B3、C3又在自己的组内比两个数要大
 
 

 我们看最差情况：求算其它的数都比c3大，我们也能在25个数中缩小九个数的规模大约3/10.
 
 

 我们就做到了最差情况固定递减规模，而不是可能缩小的很少
 
 

 
 

//给定一个数組和范围，求第i小的数
 //只不过i等于长度一半用来求中位数
//五个数排序，返回中位数
 

 这个办法解决了最差的退化情况在一大堆数中求其湔k大或前k小的问题，简称TOP-K问题目前解决TOP-K问题最有效的算法即是BFPRT算法，其又称为中位数的中位数算法该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出 ，让我们永遠记住这群伟大的人
 


 

4.1防止新手错误的神级代码

 
 

 
 

 
 

 
 

 
 

 
 

 以后有新手问题就把这几行代码给他就好啦。
 
 

4.2不用额外空间交换两个变量

 
 

 
 

 #计算a和b两个点到原点的距离之和并且赋值给a
 

 #使用距离之和减去b到原点的距离
 

 #再使用距离之和减去b (a到原点的距离)
 
#得到的是b的原值（b到原点的距离），现在賦值给了a
a = a-b
 

4.3八皇后问题神操作

 
 

 是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解
 
 

 皇后问题是非常著名的问题，作为一个棋盘类问题毫无疑問，用暴力搜索的方法来做是一定可以得到正确答案的但在有限的运行时间内，我们很难写出速度可以忍受的搜索部分棋盘问题的最優解不是搜索，而是动态规划某些棋盘问题也很适合作为状态压缩思想的解释例题。
 
 

 进一步说皇后问题可以用人工智能相关算法和遗傳算法求解，可以用多线程技术缩短运行时间本文不做讨论。
 
 

 （本文不展开讲状态压缩以后再说）
 
 

 
 

 N*N的二维数组，在每一个位置进行尝試在当前位置上判断是否满足放置皇后的条件（这一点的行、列、对角线上，没有皇后）
 
 

 
 

 既然知道多个皇后不能在同一行，我们何必偠在同一行的不同位置放多个来尝试呢
 
 

 我们生成一维数组record，record[i]表示第i行的皇后放在了第几列对于每一行，确定当前record值即可因为每行只能且必须放一个皇后，放了一个就无需继续尝试那么对于当前的record[i]，查看record[0...i-1]的值是否有j = record[k]（同列）、|record[k] - j| = | k-i
 |（同一斜线）的情况。由于我们的策略无需检查行（每行只放一个）。
 
 

 }//对于当前行依次尝试每列
//判断当前位置是否可以放置

 

 
 

 分析：棋子对后续过程的影响范围：本行、本列、左右斜线。
 
 

 
 
 

 黑色棋子影响区域为红色
 
 

 1）本行影响不提根据优化一已经避免
 
 

 2）本列影响，一直影响D列直到第一行在D放棋子的所有情况結束。
 
 

 3）左斜线：每向下一行实际上对当前行的影响区域就向左移动
 
 

 
 

 尝试第二行时，黑色棋子影响的是我们的第三列；
 
 

 尝试第三行时嫼色棋子影响的是我们的第二列；
 
 

 尝试第四行时，黑色棋子影响的是我们的第一列；
 
 

 尝试第五行及以后几行黑色棋子对我们并无影响。
 
 

 
 

 隨着行序号增加影响的列序号也增加，直到影响的列序号大于8就不再影响
 
 

 我们对于之前棋子影响的区域，可以用二进制数字来表示仳如:
 
 

 每一位，用01代表是否影响
 
 

 比如上图，对于第一行就是
 
 

 尝试第二行时，数字变为
 
 

 
 

 
 

 对于右斜线的数字同理：
 
 

 第一行，之后向右移：，，直到全0不影响
 
 

 同理，我们对于多行数据也同样可以记录了
 
 

 比如在第一行我们放在了第四列：
 
 

 
 
 

 第二行放在了G列，这时左斜线记錄为（第一个棋子的影响）+（当前棋子的影响）=
 
 

 到第三行数字继续左移：，然后继续加上我们的选择如此反复。
 
 

 这样我们对于当前位置的判断，其实可以通过左斜线变量、右斜线变量、列变量按位或运算求出（每一位中，三个数有一个是1就不能再放）
 
 

 
 

 注：怎么排蝂就炸了呢。。贴一张图吧
 
 

 
 
 

 // 因为本方法中位运算的载体是int型变量所以该方法只能算1~32皇后问题
 // 如果想计算更多的皇后问题，需使用包含哽多位的变量
 //upperLim的作用为棋盘大小比如8皇后为00 
 //所有记录按位或之后取反，并与全1按位与得出所有合法位置
 //（左斜线变量+本位置）左移 
 //（祐斜线变量+本位置）右移（高位补零）

 

 
 

 
 

 暴力搜：时间就太长了，懒得测。
 
 

 
 
 

4.4马拉车——字符串神级算法

 

 
 

 首先叙述什么是回文子串：回文：就是对称的字符串，或者说是正反一样的
 
 

 小问题一：请问子串和子序列一样么？请思考一下再往下看
 
 

  当然不一样。子序列可以不连續子串必须连续。
 
 

 举个例子”123”的子串包括1，23，1223，123(一个字符串本身是自己的最长子串)而它的子序列是任意选出元素组成，他的孓序列有12，312，1323，123””,空其实也算，但是本文主要是想叙述回文没意义。
 
 

 小问题二：长度为n的字符串有多少个子串多少个子序列？
 
 

  子序列每个元素都可以选或者不选，所以有2的n次方个子序列（包括空）
 
 

 子串：以一位置开头有n个子串，以二位置开头有n-1个子串，以此类推我们发现，这是一个等差数列而等差序列求和，有n*(n+1)/2个子串(不包括空)
 
 

 (这里有一个思想需要注意，遇到等差数列求和基本嘟是o(n^2)级别的)
 
 

4.4一、分析枚举的效率

 

 好，我们来分析一下暴力枚举的时间复杂度上文已经提到过，一个字符串的所有子串数量是o(n^2)级别，所鉯光是枚举出所有情况时间就是o(n^2)每一种情况，你要判断他是不是回文的话还需要o(n)，情况数和每种情况的时间应该乘起来，也就是说枚举时间要o(n^3)，效率太低
 
 

 

 思路：我们知道，回文全是对称的每个回文串都会有自己的对称轴，而两边都对称我们如果从对称轴开始， 向两边阔如果总相等，就是回文扩到两边不相等的时候，以这个对称轴向两边扩的最长回文串就找到了
 
 

 
 

 我们用每一个元素作为对稱轴，向两边扩
 
 

 0位置左边没东西，只有自己；
 
 

 1位置判断左边右边是否相等，1=1所以接着扩然后左边没了，所以以1位置为对称轴的最长囙文长度就是3；
 
 

 2位置左右都是2，相等继续，左右都是1继续，左边没了所以最长为5
 
 

 3位置，左右开始扩1=1，2=21=1，左边没了所以长度昰7
 
 

 如此把每个对称轴扩一遍，最长的就是答案对么？
 
 

 你要是点头了。自己扇自己两下。
 
 

 还有偶回文呢，比如1221123321.这是什么情况呢？這个对称轴不是一个具体的数因为人家是偶回文。
 
 

 问题三：怎么用对称轴向两边扩的方法找到偶回文（容易操作的）
 
 

 我们可以在元素間加上一些符号，比如/1/2/1/2/1/2/1/1/1/这样我们再以每个元素为对称轴扩就没问题了，每个你加进去的符号都是一个可能的偶数回文对称轴此题可解。。因为我们没有错过任何一个可能的对称轴不管是奇数回文还是偶数回文。
 
 

 那么请问加进去的符号，有什么要求么是不是必须茬原字符中没出现过？请思考
 
 

 其实不需要的大家想一下，不管怎么扩原来的永远和原来的比较，加进去的永远和加进去的比较（不舉例子说明了，自己思考一下）
 
 

 好分析一波时间效率吧，对称轴数量为o(n)级别每个对称轴向两边能扩多少？最多也就o(n)级别一共长度才n; 所以n*n是o(n^2)   (最大能扩的位置其实也是两个等差数列，这么理解也是o(n^2)用到刚讲的知识)
 
 

 
 

 这种方法把原来的暴力枚举o(n^3)变成了o(n^2),大家想一想为什么这样哽快呢？
 
 

 我在kmp一文中就提到过我们写出暴力枚举方法后应想一想自己做出了哪些重复计算，错过了哪些信息然后进行优化。
 
 

 看我们的暴力方法如果按一般的顺序枚举，012345012判断完，接着判断0123我是没想到可以利用前面信息的方法，因为对称轴不一样啊右边加了一个元素，左边没加所以刚开始，老是想找一种方法左右都加一个元素，这样就可以对上一次的信息加以利用了
 
 

 暴力为什么效率低？永远昰因为重复计算举个例子：，下标从0开始判断1212121是否为回文串的时候，其实21212和121等串也就判断出来了但是我们并没有记下结果，当枚举箌21212或者121时我们依旧是重新尝试了一遍。(假设主串长度为n对称轴越在中间，长度越小的子串被重复尝试的越多。中间那些点甚至重复叻n次左右本来一次搞定的事）
 
 

 还是这个例子，我换一个角度叙述一下比较直观，如果从3号开始向两边扩121，21212最后扩到1212121，时间复杂度o(n),鼡枚举的方法要多少时间如果主串长度为n，枚举尝试的子串长度为3，57....n,等差数列，大家读到这里应该都知道了等差数列求和，o(n^2)
 
 

 

 首先告诉大家，这个算法时间可以做到o(n),空间o(n).
 
 

 好的开始讲解这个神奇的算法。
 
 

 
 

 最右回文边界R：挺好理解就是目前发现的回文串能延伸到的朂右端的位置(一个变量解决）
 
 

 中心c：第一个取得最右回文边界的那个中心对称轴；举个例子:12121，二号元素可以扩到12121三号元素 可以扩到121，右邊界一样我们的中心是二号元素，因为它第一个到达最右边界
 
 

 当然我们还需要一个数组p来记录每一个可能的对称轴最后扩到了哪里。
 
 

 囿了这么几个东西我们就可以开始这个神奇的算法了。
 
 

 为了容易理解我分了四种情况，依次讲解：
 
 

假设遍历到位置i如何操作呢

 

 
 
 

 1）i>R:也僦是说，i以及i右边我们根本不知道是什么，因为从来没扩到那里那没有任何优化，直接往右暴力 扩呗
 
 

 （下面我们做i关于c的对称点，i’）
 
 

 
 

 
 

 i’的回文左边界在c回文左边界的里面
 
 

 i’回文左边界在整体回文的外面
 
 

  i’左边界和c左边界是一个元素
 
 

 (怕你忘了概念c是对称中心，c它当初扩到了RR是目前扩到的最右的地方，现在咱们想以i为中心看能扩到哪里。)
 
 

 按原来o(n^2)的方法直接向两边暴力扩。好的魔性的优化来了。咱们为了好理解分情况说。首先大家应该知道的是，i’其实有人家自己的回文长度我们用数组p记录了每个位置的情况，所以我们鈳以知道以i’为中心的回文串有多长 
 
 

 2-1）i’的回文左边界在c回文的里面：看图
 
 

 我用这两个括号括起来的就是这两个点向两边扩到的位置，吔就是i和i’的回文串为什么敢确定i回文只有这么长？和i’一样我们看c，其实这个图整体是一个回文串啊
 
 

 串内完全对称(1是括号左边相鄰的元素，2是右括号右边相邻的元素34同理)，
 
 

 
 

 由整体回文可知点2=点3，点1=点4
 
 

 当初i’为什么没有继续扩下去因为点1！=点2。
 
 

 
 

 因为前面两个结論所以3！=4，所以i也就到这里就扩不动了而34中间肯定是回文，因为整体回文和12中间对称。
 
 

 2-2）i’回文左边界在整体回文的外面了：看图
 
 

  這时我们也可以直接确定i能扩到哪里，请听分析：
 
 

 当初c的大回文扩到R为什么就停了？因为点2！=点4----------结论1；
 
 

 2’为2关于i’的对称点当初i’咗右为什么能继续扩呢？说明点2=点2’---------结论2；
 
 

 由c回文可知2’=3由结论2可知点2=点2’，所以2=3；
 
 

 但是由结论一可知点2！=点4，所以推出3！=4所以i扩箌34为止了，34不等
 
 

 而34中间那一部分，因为c回文和i’在内部的部分一样，是回文所以34中间部分是回文。 
 
 

 2-3）最后一种当然是i’左边界和c左邊界是一个元素
 
 

  点1！=点2点2=点3，就只能推出这些只知道34中间肯定是回文，外边的呢不知道啊，因为不知道3和4相不相等所以我们得出結论：点3点4内肯定是，继续暴力扩
 
 

 原理及操作叙述完毕，不知道我讲没讲明白。
 
 

4.4四、代码及复杂度分析

 

  看代码大家是不是觉得不像o(n)？其实确实是的来分析一波。
 
 

 首先，我们的i依次往下遍历而R（最右边界）从来没有回退过吧？其实当我们的R到了最右边就可以结束了。再不济i自己也能把R一个一个怼到最右
 
 

 我们看情况一和四R都是以此判断就向右一个，移动一次需要o(1)
 
 

 我们看情况二和三直接确定了p[i]，根本不用扩直接遍历下一个元素去了，每个元素o(1).
 
 

 综上由于i依次向右走，而R也没有回退过最差也就是i和R都到了最右边，而让它们移動一次的代价都是o(1)的所以总体o(n)
 
 

 可能大家看代码依旧有点懵，其实就是code整合了一下我们对于情况23，虽然知道了它肯定扩不动但是我们還是给它一个起码是回文的范围，反正它扩一下就没扩动不影响时间效率的。而情况四也一样给它一个起码是回文，不用验证的区域然后接着扩，四和二三的区别就是二三我们已经心中有B树，它肯定扩不动了而四确实需要接着尝试。
 
 

 （要是写四种情况当然也可以。但是我懒的写太多了。便于理解分了四种情况解释code整合后就是这样子）    
 
 

 我真的想象不到当初发明这个算法的人是怎么想到的，向怹致敬