合理运用心流通道，科学刷题，快乐刷题！

前言

怎么刷算法题？按照什么顺序刷题？如何科学地提高算法能力？

如果你刚开始刷题，还不熟悉基本编程语法和常用库函数，推荐先刷力扣官方的入门题单：

分布式计算机系统的要求刺激了将相同信息的副本保存在计算机网络中的不同节点的兴趣。

数据复制允许信息位于其使用点附近，可以通过在高使用区域中静态定位副本，也可以根据需要动态创建临时副本。

通过允许许多节点并行处理对相同信息的请求，数据复制也增加了数据的可用性，并掩盖部分系统故障。

因此，在某些情况下，维护副本的成本会被复制数据所提供的性能，通信成本和可靠性优势所抵消。

新算法

我们提出了一种维护复制文件的新算法。

该算法可以通过以下描述简要表征：

• 为复制文件的每个副本分配一定数量的投票。

• 每个事务收集读取法定数量的r票数以读取文件，以及写入法定数量的w票数以写入文件，使得r + w大于分配给文件的总票数。

• 这可确保每个读取仲裁与每个写入仲裁之间存在非空交集。 总是有一个文件代表的子集，其总票数为w当前。

• 因此，所收集的任何读取法定数量都保证具有当前副本。

• 版本号可以确定哪些副本是最新的。

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

暴力匹配算法

首先，先理清楚了暴力匹配算法的流程及内在的逻辑：

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

1. 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；

2. 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

定义

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

算法流程

下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

1. 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

2. 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

3. 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

不同于先进先出队列，其对每一个元素指定了优先级，一般情况下，出队时，优先级越高的元素越先出队。

问题

题目

实现一个优先级队列，此队列具有enqueue（val，prior）和dequeue（）两种操作，分别代表入队和出队。

其中enqueue（val，prior）第一个参数val为值，第二个参数prior为优先级（prior越大，优先级越高），优先级越高越先出队

dequeue（）出队操作，每调用一次从队列中找到一个优先级最高的元素出队，并返回此元素的值（val）

要求：在O（logn）时间复杂度内完成两种操作

不久前，我发现需要一台PNG装载机用于我的一个小项目。作为一个完整的工具，我当然决定自己写一个 - 毕竟，为什么在还有车轮等待重新发明时为自己省力？如果你愿意的话，可以在这里查看inflater代码的来源 - 它写得非常干净。事实上，我专门写它是为了易于阅读，而不是最快的实现。

我当时对Deflate了解不多。我知道它基于LZ系列算法（LZ77 / L7SS等）。我听说有人说它只是“只是”LZSS，除了他们在匹配向量上应用霍夫曼编码。嗯，事实证明这是真的。均田。但是当我更深入地阅读规范时，它让我觉得这里发生了一些非常聪明的事情，我之前没有看到过任何明确提出过的事情。所以我想为什么不试着在这里解释Deflate的本质。我不打算在严格的细节上涵盖整个工作;如果你想要那就去阅读规范。

数据压缩是一门通信原理和计算机科学都会涉及到的学科，在通信原理中，一般称为信源编码，在计算机科学里，一般称为数据压缩，两者本质上没啥区别，在数学家看来，都是映射。

一方面在进行通信的时候，有必要将待传输的数据进行压缩，以减少带宽需求；另一方面，计算机存储数据的时候，为了减少磁盘容量需求，也会将文件进行压缩，尽管现在的网络带宽越来越高，压缩已经不像90年代初那个时候那么迫切，但在很多场合下仍然需要，其中一个原因是压缩后的数据容量减小后，磁盘访问IO的时间也缩短，尽管压缩和解压缩过程会消耗CPU资源，但是CPU计算资源增长得很快，但是磁盘IO资源却变化得很慢，比如目前主流的SATA硬盘仍然是7200转，如果把磁盘的IO压力转化到CPU上，总体上能够提升系统运行速度。