(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

综述

基本概念

使用双端队列(deque)实现单调的优先队列，保证队列中的元素始终是单调的。

示例

下面构造一个单调递增的优先队列，每次从队首插入元素，如果队首的元素小于该元素， 则弹出队首的元素，直至队首元素不小于插入元素。

1

[2,3,5,1,4]
//依次插入单调队列
#1: [2]
#2: [3]
#3: [5]
#4: [1,5]
#5: [4,5]

应用

题目

leetcode 239. Sliding Window Maximum

解决方案

此题是单调优先队列的完美的应用场景，每次都要获取sliding window内的最大值。

解决方案也很简单，构建一个单调递减的优先队列，每次插入新加入sliding window 的元素，但是，有一点要注意，一定要删除已经移出sliding window的那个元素。

算法流程：

1. 检查单调优先队列队首元素是否等于移出sliding window的那个元素，如果是那就弹出队首元素;
2. 将新元素插入单调优先队列
3. 将队首的最大元素插入到结果数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    	vector<int> ans;
    	deque<int> queue;
    	int i, size;
    	size = nums.size();
    	for(i = 0; i < size; ++i){
    		if(!queue.empty() && queue.front() == i-k){
    			queue.pop_front();
    		}
    		while(!queue.empty() && nums[queue.back()] < nums[i]){
    			queue.pop_back();
    		}
    		queue.push_back(i);
    		if(i >= k-1){
    			ans.push_back(nums[queue.front()]);
    		}
    	}
    	return ans;
    }
};

证明

问题是解决了，但是还是感觉心里不踏实，这样随便说两句总是难以说服自己算法 是正确的，所以还是证明一下比较靠谱。

要证明算法的正确性，也就是证明单调优先队列始终存储的是sliding window内的 元素，由于数组中的每个元素都会插入到单调优先队列中，所以只需证明单调优先队列 中保存的索引值始终都介于sliding window内。

方案中单调优先队列既保证了队列中元素的单调性又保证了元素所对应索引的单调性。 队列中所存储的索引单调递增，队列中索引所对应的值是单调递减的。

命题：单调优先队列中保存的索引值始终都介于sliding window内

使用数学归纳法(induction)。

1.当i=0时:

此时单调优先队列为空，单调优先队列中只会插入0，显然满足命题。

2.假设当i=m时，命题成立，那么当i=m+1时：

当i=m时，队列中所有元素x都满足m-k< x <= m，当插入第m+1个元素时，如果 队首元素等于m+1-k则弹出队首元素，否则就不弹出，这样就保证了队列中的所有元素 都满足m+1-k<x<=m+1。

综上所述，命题得证。

时间复杂度

利用摊还分析，数组中的每个元素最多只会进入队列一次和弹出一次，所以最坏的情况下 的时间复杂度为O(n)。

区间型动态规划：合并石子

状态转移方程：

显而易见，这种方法时间复杂度是O(n^3)，如何去优化？

四边形不等式

通过四边形不等式的优化，可以进一步限定k的范围，从而可以将事件复杂度降为 O(n^2)，我们最终的目的是证明决策变量k的单调性。

通过不断的搜索，发现此优化方法原来是姚期智的夫人储枫(Frances Yao)所写，默默 膜拜了一番。

算法相关论文地址：论文

价值函数c[i,j]

公式1：

满足公式1，说明价值函数c[i,j]满足区间的单调性。

公式2：

满足公式2，说明价值函数c[i,j]满足四边形不等式。

对于石子合并问题，价值函数显然满足上述两个公式。

状态转移函数m[i,j]

要证明状态转移函数也满足四变形不等式.

引理1:

具体的证明过程是通过数学归纳法来的，相关证明过程可参看论文，本人愚顿，看了 好久，才感觉明白了，最重要的一步则是： 证明的过程中又引用了需要证明的结论，我的理解是数学归纳法，上述公式的范围 比结论的范围小，故可以引用。

决策变量的单调性

假设k[i,j]表示m[i,j]取得最小值时的决策值。

引理2： 根据对称性只需证明k[i,j-1]<=k[i,j], 假设x=k[i,j-1]，对任意i<y<x<j-1<j.

不等式两侧同时加上：

then:

因为：

所以:

从而可以确定k[i,j]不可能小于x，也就是说k[i,j-1]<=k[i,j].

石子合并代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int piles[5001];

int *status[5001];
int *cv[5001];

void quard_dp(){
	int n, i, j, k, dis;
	int min ,tmp;
	scanf("%d", &n);
	piles[0] = 0;
	while(n != 0) {
		for(i = 1; i <= n; i++){
			scanf("%d", &piles[i]);
			piles[i] += piles[i-1];
			status[i] = (int*)malloc((n+1) * sizeof(int));
			status[i][i] = 0;
			cv[i] = (int*)malloc((n+1) * sizeof(int));
			cv[i][i] = i;
		}

		for(dis = 1; dis < n; ++dis){
			for(i = 1; i <= n-dis; i++){
				j = i + dis;
				min = INT_MAX;
				for(k = cv[i][j-1]; k <= cv[i+1][j] && k < n; ++k){
					tmp = status[i][k] + status[k+1][j] + piles[j]- piles[i-1];
					if(tmp < min) {
						min = tmp;
						cv[i][j] = k;
					}
				}
				status[i][j] = min;
			}
		}
		printf("%d\n", status[1][n]);
		for(i = 0; i < n; i++){
			free(status[i]);
			free(cv[i]);
		}

		scanf("%d", &n);
	}
}

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

前言

通过将近一个月时间的学习，终于敢开始写着篇博客，如果有什么不对或者不足的地方， 还望大家斧正。

本文主要讨论分布式存储系统的主要的容错机制，以两种主流的一致性算法为主线， 结合实际的分布式存储系统，看这些算法和系统是如何解决分布式存储中的一致性 问题的。

本文以问题的形式进行推进，希望大家在看的时候，能够站在一个系统设计者的角度 去思考这些问题，当你思考过后再去看答案，没准你的想法会更好。

综述

分布式存储系统的一个主要目标就是实现容错，系统要保证在服务器/网络/程序 任何一方面挂掉的情况下保持可用性，正确性。

Q1: 如何实现系统的正确性和可用性？

答案很简单，使用backup（副本），当系统中某个服务不可用了，立即切换到backup， 由backup继续提供服务。那么问题又来了，backup接替了原来的primary，如果它的 状态和原来的master不一致的话，就会导致client在不同时刻看到的系统状态不一致。 就好比你的银行卡里今天有￥1M，明天看却只有￥1K了，这怎么能忍。

换句话说，我们要保证整个系统在任何时候都要以相同的顺序执行相同的操作，前面 已经执行完的操作也被后续的操作所继承，并且所有的操作只执行一次。

所以接下来就看看如何解决这个一致性问题。

一致性

其实，我们要解决的问题就是如何保证primary和backups之间的一致性。可能有人就会 说了，这还不简单，只要保证primary和backups都执行了client的所有操作不就可以 保证一致性了嘛。很好，那我们就按照这个思路继续往下走。

首先，来看一看基本的消息模型。 那么问题来了。

Q2：Primary 挂掉，该怎么办？

如果Primary挂掉，我们首先想到的是把一个backup提成为Primary。接着，问题又来了 提哪个backup呢？最naive的方法就是随机选一个backup作为新的Primary。如果这样， 我们就必须保证所有的backup都是实时跟Primary同步的，这对系统的要求是极高的， 也是不太现实的，由于网络，主机问题，如果要实现实时同步，会导致系统的响应延迟变得 很高。那么有没有什么解决方案呢？显然是有的。下面就引出一致性算法里面极其重要 的一个思想：“Overlapping Majorities”。

“Overlapping Majorities”的意思就是对每个操作，集群中至少有一半servers保存了 该操作的状态，这样就至少有一台server执行了所有的操作，在通过适当的leader 选举机制，就能够确保新的leader也执行了前面所有的操作。

那么问题又来了，怎么去选举一个leader呢？

Q3: 如何选举leader？

我目前看到比较好的方案是raft算法的，给每台server设定一个随机时间，当该随机时间到达 以后，这台server就会成为candidate，然后进行投票来实现leader选举。

Raft演示

Q4: 如何保证所有的操作只执行一次(Exactly once)

方法也很简单。给Client的每个请求都设置一个Unique ID来唯一标识请求，这样在Server 执行每个请求时就可以过滤掉重复的请求。

场景分析

现在基本概念说清楚以后，我们来对消息传输的每个步骤来分析。

1.Client发送Op到Primary

如果这一步挂掉，相当于客户端没有发起请求，所以不会影响系统的一致性。

2.Primary接收到Client的请求，转发该请求到Backups；

如果这一步挂掉，Primary不会接收到Majority of Backups的确认信息，然后就会 返回给Client一个失败的Reply。

3.Backups返回Acks到Primary。

如果某些Backups返回信息失败，但是只要Primary没有收到Majority of Backups的确认 信息，它就会返回给Client失败的Reply。

4.Primary接收到Majority of Backups的Acks信息后，Reply to Client.

如果这一步失败，系统此时已经成功执行该操作，但是Client却没有收到成功的 反馈，此时Client会处于一个Unknown state，Client重新发起该请求，由于是 同一个请求（有相同的UUID），所以该请求会被过滤掉，直接返回给Client结果。

5.Primary发送Commit信息给Backups。

如果这一步失败，可以在以后的请求中在进行同步。Commit信息的目的是让Backups 去执行所记录的操作。

6.network partition

如果出现网络划分。比如A，B，C，现在A是Primary，如果A被划分出去，那么A再 接收到Client的请求后，就不会得到Majority of Backups的Acks了，就没有办法 执行用户的操作。而B&C会重新选举出一个Primary，执行用户的操作。

如果网络修复以后，A就会回滚它的Uncommited的操作，然后去匹配新Leader的操作。

后记

以上就是基于leader选举的一致性算法，也是RAFT 算法的基本思想。

当然还有一种很出名的一致性算法Paxos。 有兴趣可以学习一下。

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

问题

Rotate a one-dimensional vector of n elements left by i positions. For instance, with n = 8 and i = 3, the vector abcdefg is rotated to deftabc.

Naive idea

1. 另外声明一个数组存储前i个元素，然后把后面的元素左移i位，最后再把数组里面 的i个元素复制到原数组的最右边的i个位置。显然这种方法是空间复杂度是O(i)，时间 复杂度O(n).
2. 另t=x[0],然后move x[i] to x[0], x[2i] to x[i]，依次类推，然后再 把t放到最后的位置；然后是x[1]，最后一直到x[i-1]。空间复杂度O(1)，时间 复杂度O(n).

   Aha!

首先，show the code:

1
2
3

reverse(0, i-1);    /* cbadefgh */
reverse(i, n-1);    /* cbahgfed */
reverse(0, n-1);    /* defghcba */

这算法的过程的有点神奇，过程比较清楚，分为三步：

1. 反转前i个元素;
2. 反转后面n-i个元素;
3. 反转所有的n个元素。

虽然结果正确，但难免没有说服力，先面就证明一下。

1. 对于0 <= x < i的元素，第一步反转以后,x的位置为x', 因为x'和x关于 i/2对称，所以

   x' = i-x

2. 对于0 <= y < i的元素，第二步反转以后,y的位置为y', 因为y'和y关于 (n-1+i)/2对称，所以

   y' = n-1+i-y

3. 对于x，平移以后最终的位置是x => n-1+x-i。 第三步反转后，x'的位置为:

   x' => n-1 - x' = n-1+x-i

4. 对于y，平移以后最终的位置是y => y-i。 第三步反转后，y'的位置为:

   y' => n-1 - y' = y-i

证明结束。

同时可以引出一个公式： 该公式推广：

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

题目

Leetcode 222 : Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2th nodes inclusive at the last level h.

题解

对于此问题，稍加思考就会想到使用binary search的方法。

首先的一个想法是，先算出树的高度，然后再用二分的方法求出最后一层节点的数量， 从而就能够统计出有多少节点。然后当我写完提交AC后，高兴了两秒，然后看到算法 时间上跟最优的差距有点大。然后有修补了一下，再提交发现还是有质的差距。

然后在discuss发现了高手的解法，但是只有代码，没有解释，我在此记录一下我的理解过程。

首先，贴出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int result,height,RTreeHeight;
TreeNode* visit,*p;

if (root==NULL) return 0;

p = visit = root;
height = 0;
for(;p;p = p -> left) height++;
result = 1;

while(--height)
{
    result <<= 1;

    RTreeHeight = 0;
    p = visit->right;
    for(;p;p = p -> left) RTreeHeight++;

    if (RTreeHeight < height) visit = visit->left;
    else
    {
        result |= 1;
        visit = visit->right;
    }
}
return result;

算法的过程就是每次计算右儿子的高度，如果右儿子的高度和树的高度一样就加1。

算法比较难理解的是result的计算方式，每次左移一位。如果理解后发现其实挺 巧妙的。

例子

首先，这棵树高度为3，result初始为1，所以1<<3=8刚好等于树中节点的数量， 大家就可以发现这其中的巧妙了。

然后，当再加几个node（红色）时，你又会发现4=1<<2。

所以，通过上面这两个图，我们可以总结出算法的思想。

1. 首先，求出树的高度height，然后这部分节点的数量是1<<height;
2. 然后，再利用二分的思想求出最底层的节点。

前言

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

网上已经有很多类似主题的博客了，为什么还要再写一篇呢， 因为网上基本上都是写到搭建完成就完了， 而不告诉我们后续如何使用，看来只能由本博主来完成这个任务了。

文章中所有操作均是在Fedora下完成的.

本文包含以下几部分：

1. 博客搭建
2. 添加Categories/Tags/About页面
3. Markdown语法
4. 添加评论系统
5. 如何写一篇博客直到发表出去

1. 博客搭建

声明：这部分我只是互联网的搬运工,具体Hexo，git，node.js是什么，请自行google.

转至：根据这篇文章足以完成建站

本博客使用的是icarus主题，一下所有操作也均是 基于此主题的。

Milestone 0 ：至此建站完成

2. 添加Categories/Tags/About页面

由于主题里面的这三个页面都是空缺的，需要手动添加。当然也很简单，一条命令了事。

以创建categories为例。

1
2

$ hexo new page "categories"
INFO  Created: xxx/source/categories/index.md

创建完以后，如果你懂markdown语法尽可在生成的index.md文件中添加东西。 不懂也没有关系，只要你愿意学，我想也是分分钟的事情，接下来就来学习一下 Markdown怎么写。

通过hexo server命令来预览

1
2

$ hexo server 
INFO  Hexo is running at http://0.0.0.0:4000/. Press Ctrl+C to stop.

Milestone 1 ：至此网站成型

3. Markdown语法

网上资料甚多，在此我只列出几篇文章，然后再贴出一个About页面的md内容，请大家自行学习。

修改GFM换行规则

首先，我想说明hexo使用的GFM 版本的Markdown语法，与标准Markdown的稍有不同。

最不爽的GFM中文档的换行就对应到页面中的换行，所以你必须把一段长文放在一行中， 这样看着就很不爽（特别是对某些vi的大神）。

我们希望使用Markdown的换行规则(即使用空行来换行)。

解决方案如下(icarus主题)：将第11行的breaks设为false。

1
2

$ vi node_modules/hexo-renderer-marked/index.js
# breaks: true 改为 breaks: false

重新生成即可

1

$ hexo g

Markdown语法资料

• Markdown语法
• Markdown实例
• Markdown简明语法

通过这三篇文章足以满足平时写博客的需求。

下面贴出一段About页面的md示例

1
2
3
4
5
6
7
8
9
10
11
12

title: 关于
date: 2015-10-14 16:20:42
comments: true
---
## 个人简介
---
我是一个有追求的人，一直未来的世界必然有属于我的一片天。
## 喜欢的句子
---
* __生活不易，全靠演技__
## 联系方式
__Email: liuqi.edward(AT)gmail.com__

Milestone 2 ：恭喜你，至此你已经具备了写博客的所有条件了。

4. 添加评论系统

添加多说评论：http://popozhu.github.io/2013/06/04/add-comment-of-duoshuo/

Milestone 3 ：你的博客看起来更完善了。

5. 如何写一篇博客并发表出去

1. 新建一篇博文

   1 2	$ hexo new post "tmp" INFO Created: xxx/source/_posts/tmp.md

2. 启动hexo server来查看博文的展示效果（相当于调试）

   1	$ hexo server

3. 编写博文(写的时候可定时查看相关页面，看看效果。)

   1	$ vi source/_posts/tmp.md

4. 编写完成无误后，即可生成静态页面，提交到github上

   1 2	$ hexo g $ hexo deploy

就是这么简单，感谢hexo，感谢github

Milestone 4 ：至此你已经具备控制博客的能力了。

参考

hexo官方文档