归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  

可以发现合并有序数列的效率是非常高的,有O(N)此时N = len(a)+len(b)。

加上一点分治的想法:
mergesort1

从而对于一个数组,我们可以如下的方式二分分治:
mergesort2

如上图所示,最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次… Read the rest

前言

欧几里德算法作为有着非常简短的实现的算法,可能很多初学者(包括当时的我)都不求甚解。本文给出了GCD、LCM的性质,以及欧几里德算法的实现、证明和时间复杂度推导。

什么是欧几里得算法

最大公约数问题是最早被研究的算法问题之一了,并且是ACM竞赛中能涉及到的很多数论内容,比如模线性方程,模线性方程组的基础。

欧几里得算法 (Euclidean algorithm) ,即大部分选手所知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间内求解两个数的最大公约数。

其核心是:\[gcd(a,b) = gcd(b, a \% b)\]

名词解释

  1. 最大公约数:即最大公因子,能够同时整除a和b的最大因子,记作gcd(a, b),或gcd
  2. 最小公倍数:能够被a和b整除的最小数,记作lcm(a, b),或lcm。
  3. %:指的是取余运算(取模运算),用例: a % b
  4. |:指的是整除运算,a | b表明a可以整除b,即a是b的因子

GCD和LCM的一些性质

  1. a, b都能分解为有限个素数的积
  2. gcd(a, b)中只含a,b的全部公共素因子
  3. lcm(a, b)中含有a,b的所有素因子
  4. \(gcd\%lcm=0\)
  5. \(gcd
Read the rest

什么是哈夫曼树

给定n个权值,作为n个叶结点,构造一棵二叉树,而这棵树的特点是,有n个叶节点,叶节点的值为给定的权值。而内部节点的值为子树的权值和。

这样的二叉树有很多,但树的带权路径和达到最小,则这棵树被称为哈夫曼树。
huffman tree 1

Note:带权路径和指的是所有叶节点的权值*深度和,即\(\Sigma value∗deep=100+2∗50+3∗20+3∗10\)

而我们不妨让内部节点的值为子树的权值和,我们可以发现,实际上一棵树的带权路径和=这棵树的所有节点值之和-根节点的值。(显然)

哈夫曼树有什么用

哈夫曼树主要应用在文本编码上。我们考虑如何将文本中出现的单词编码为二进制数(01串),让文本的总长度最小。

对于文本{1, 1, 2, 2, 3, 3, 3, 5},我们可以将单词1、2、3、5出现的频率作为叶节点的权值,为{2, 2, 3, 1}。那么上述最短编码问题等价于寻找一棵树,其带权路径和最小,也就是找对应的哈夫曼树。

唯一可译码

如果我们直接将单词按照频率的从高到低排序,不就得到了一个编码了吗?

但这样的编码不是一个“唯一可译码”,即对于10001010100101,我们不… Read the rest

前言

Bellman-Ford算法,限于资料匮乏和时间复杂度比Dijkstra算法高,包括白书在内的很多资料,都没说得太明白。对于优化后的SPFA算法也没有提及。
而且最短路问题通常是作为图论的入门问题,学习者通常没有图论基础,不知道图论的一些基本常识,看已有的资料很容易产生疑惑。其实,从Bellman-ford算法优化到SPFA算法实际上是顺理成章的。

本文旨在阐明这两个算法思想和步骤,如果有什么晦涩或者疏漏之处在所难免,烦劳读者们指出。

Bellman-Ford算法有什么用

Bellman-Ford算法是用来解决单源最短路问题的。
在现实生活旅游途中,我们通常想知道一个景点到其他所有景点的最短距离,以方便我们决定去哪些比较近的景点。而这时候,Bellman-Ford算法就有用了。

Bellman-Ford算法的优点是可以发现负圈,缺点是时间复杂度比Dijkstra算法高。
而SPFA算法是使用队列优化的Bellman-Ford版本,其在时间复杂度和编程难度上都比其他算法有优势。

算法流程

(1)初始化:将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0
(2)迭代:遍历图中的每条边,… Read the rest

前言

单调栈和单调队列算是栈和队列的高级应用吧,在公司面试中应该是不怎么会出现的(除非算法岗?)。
因为原理比较简单,网络上的相关资料反而对于这两个东西说得都不甚清楚,尤其是它们的应用方法。最基本的两本中文算法书“紫书”和“白皮”都没有提到。

而我因为平日要做的事情也很多,仓促中写下的这篇文章难免表达上会有不清晰的地方和各种疏漏,希望读者不吝赐教=v=。

栈和队列这两种基础数据结构戳:TBC。

先说明一下,无论是栈还是队列,我们把元素进入的一端称作“尾部”,并用双引号标出,另一端称作“尾部”。对于栈,头部即是栈底,尾部即是栈顶。对于队列,头部对应队首,尾部对应队尾。

monotone queue and stack

注:我不确定单调队列是否翻译成monotone queue,算法导论上没有提到这个数据结构,Bing上也没有搜索到对应它的结果(倒是返回了关于优先队列的结果)。

单调栈

我们都已经非常熟悉栈了,它具有先入后出的性质。而单调栈为了满足单调的要求,增加了一个性质:

  • 从栈顶到栈底的元素是严格递增(or递减)

显然,这和我们的正常的流程有一定矛盾之处——如果栈中是5 4 3 2 1,如果压入3怎么办?
原来我们只需要添加到栈尾即可,现在则需要将3 2 1弹出,再… Read the rest

为什么要使用树状数组

比如说,我这里有一组数1, 2, 3, 2, …, k。我想知道第i到第j的和\(\mathop \sum \limits_{n = i}^j v[i]\)是多少?

朴素算法:

for (int k = 0; k < n; k++)
    if (k >= i && k <= j) ans += v[k];

类似这种的写法,虽然在某些点值改变时也依然可以计算(我们称这种问题为动态问题),但复杂度最高到O(n),实在难以接受。

树状数组是通过前缀和思想,用来完成单点更新和区间查询的数据结构。它比之线段树,所用空间更小,速度更快,而且编程的复杂难度也大大减小。和ST相比,它可以动态更新数据。

前缀和

我们可以把查询区间和问题转化为前缀和问题。
前缀和是指:v[1]~v[i]的和,记作sum(i)。

如果我们能够计算s和t的前缀和,用sum(t)−sum(s−1)可以得到区间[s, t]的和。

而树状数组正是一个支持求前缀和的数据结构。

什么是树状数组

(如果你学过线段树,可以先从最后“树状数组的缺陷”看起,树状数组的灵感来源脉络会更加清晰)
Binary Indexed Tree
我们依据二进制的思想,让”为1的最低位”在第一位的数(即奇数),储存长度为1的区间和… Read the rest

为什么用快速幂

对于求解\({a^b}\)的问题,我们能想到的朴素算法:

int ans = 1;
for (int i = 0; i < b; i++)
    ans *= a;

而快速幂可以在O(logn)时间内解出。

什么是快速幂

先举一个例子,我们计算\({5^8}\)只需要3步,即分别求得\({5^2}\)、\({5^4}\)、\({5^8}\)。
因为每次相乘,幂次都增长一倍,我们只需要logn次就可以让幂逼近n。

所以,我们可以将b通过二进制分解为形如10011的数,则\({\rm{b}} = {2^{k1}} + {2^{k2}} + {2^{k3}} \ldots \)。
因为\({a^{{2^{k1}}}}\)到\({a^{{2^{kmax}}}}\)可以通过\({a^{{2^1}}}\)、\({a^{{2^2}}}\)\({a^{{2^3}}}\)这样在递推kmax次中得到,所以\({a^b} = {a^{{2^{k1}}}} * {a^{{2^{k2}}}}\)可以在O(lo… Read the rest