文章目录

• 链表
  • 单链表
  • 双链表
• 栈与队列
  • 栈
  • 队列
  • 循环队列
  • 单调栈
  • 单调队列
• KMP
• Tire树
• 并查集
• 堆
• 哈希表
  • 拉链法
  • 开放地址法
  • 字符哈希
• 算法竞赛中C++常用容器

一、链表

利用数组来进行模拟链表效率比较高。

1.单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;// 初始化
void init()
{head = -1;idx = 0;
}// 在链表头插入一个数a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}// 将头结点删除，需要保证头结点存在
void remove()
{head = ne[head];
}

2.双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;// 初始化
void init()
{//0是左端点，1是右端点r[0] = 1, l[1] = 0;idx = 2;
}// 在节点a的右边插入一个数x
void insert(int a, int x)
{e[idx] = x;l[idx] = a, r[idx] = r[a];l[r[a]] = idx, r[a] = idx ++ ;
}// 删除节点a
void remove(int a)
{l[r[a]] = l[a];r[l[a]] = r[a];
}

二、栈和队列

1.栈

定义：栈（Stack）是一个有序线性表，只能在表的一端（称为栈顶，top）执行插入和删除操作。最后插入的元素将第一个被删除，所以栈也称为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out）线性表；

两个改变栈的操作都有专用名称。一个称为入栈（push），表示在栈中插入一个元素；另一个称为出栈（pop），表示从栈中删除一个元素。试图对一个空栈执行栈操作称为下溢（underflow）；试图对一个满栈执行栈操作称为溢出（overflow）。通常，溢出和下溢均认为是异常；

// tt表示栈顶
int stk[N], tt = 0;// 向栈顶插入一个数
stk[ ++ tt] = x;// 从栈顶弹出一个数
tt -- ;// 栈顶的值
stk[tt];// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}

2.队列

定义：队列是一种只能在一端插入（队尾），在另一端删除（队首）的有序线性表。队列中第一个插入的元素也是第一个被删除的元素，所以队列是一种先进先出（FIFO,First In First Out）或后进后出（LiLO,Last In Last Out）线性表；

与栈类似，两个改变队列的操作各有专用名称；在队列中插入一个元素，称为入队（EnQueue），从队列中删除一个元素，称为出队（DeQueue）；试图对一个空队列执行出队操作称为下溢（underflow），试图对一个满队列执行入队操作称为溢出（overflow）；通常认为溢出和下溢是异常。

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;// 向队尾插入一个数
q[ ++ tt] = x;// 从队头弹出一个数
hh ++ ;// 队头的值
q[hh];// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{}

3.循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;// 队头的值
q[hh];// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{}

4.单调栈

单调栈 ：在栈的 先进后出 基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增或者是递减。

具体进栈过程如下：

• 对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。

• 对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素。

//常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i;
}

5.单调队列

单调队列 就是能够完美支持下面三种操作的一种容器：
（1）通过 O(1) 的时间，获取容器中元素的最大值。
（2）通过 O(1) 的时间，删除元素。
（3）通过 O(1) 的时间，插入元素。

//常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口while (hh <= tt && check(q[tt], i)) tt -- ;q[ ++ tt] = i;
}

三、KMP

kmp算法思想

        我们首先用一个图来描述kmp算法的思想。在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论：

• A段字符串是f的一个前缀。

• B段字符串是f的一个后缀。

• A段字符串和B段字符串相等。

    所以前移k位之后，可以继续比较位置i的前提是f的前i-1个位置满足：长度为i-k-1的前缀A和后缀B相同。只有这样，我们才可以前移k位后从新的位置继续比较。

        所以kmp算法的核心即是计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。

next数组计算

            理解了kmp算法的基本原理，下一步就是要获得字符串f每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next数组。在这里要注意一点，next数组表示的是长度，下标从1开始；但是在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。由上图我们可以看到，如果位置i和位置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。由此我们可以写出求next数组的代码：

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;
}// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的逻辑}
}

四、Tire树

字典树：（Trie树、前缀树）是一种用于快速检索的多叉树结构。字典树把字符串看成字符序列，根据字符串中字符序列的先后顺序构造从上到下的树结构，树结构中的每一条边都对应着一个字符。字典树上存储的字符串被视为从根节点到某个节点之间的一条路径，并在终点节点上做个标记"该节点对应词语的结尾"。

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
void insert(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++ ;
}// 查询字符串出现的次数
int query(char *str)
{int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}

五、并查集

并查集：用于处理一些不交集（一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

• 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。

• 合并：将两个集合合并为一个。

• 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

(1)朴素并查集：int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b);(2)维护size的并查集：int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;size[i] = 1;}// 合并a和b所在的两个集合：size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)维护到祖宗节点距离的并查集：int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合：p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

六、堆

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]);
}void down(int u)
{int t = u;if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

七、哈希表

1.拉链法

拉链法：将大小为N的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。

    //拉链法int h[N], e[N], ne[N], idx;// 向哈希表中插入一个数void insert(int x){int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx ++ ;}// 在哈希表中查询某个数是否存在bool find(int x){int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;}

2.开放地址法

开放地址法：开放地址法是另一种（相对于分离链接法）解决散列冲突的方法。适用于装填因子（散列表中元素个数和散列表长度比）较小（小于0.5）的散列表。

    //开放寻址法int h[N];// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置int find(int x){int t = (x % N + N) % N;while (h[t] != null && h[t] != x){t ++ ;if (t == N) t = 0;}return t;}

3.字符串哈希       

 核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果。

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;
}// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}

八、算法竞赛中C++常用容器

vector, 变长数组，倍增的思想size()  返回元素个数empty()  返回是否为空clear()  清空front()/back()push_back()/pop_back()begin()/end()[]支持比较运算，按字典序pairfirst, 第一个元素second, 第二个元素支持比较运算，以first为第一关键字，以second为第二关键字（字典序）string，字符串size()/length()  返回字符串长度empty()clear()substr(起始下标，(子串长度))  返回子串c_str()  返回字符串所在字符数组的起始地址queue, 队列size()empty()push()  向队尾插入一个元素front()  返回队头元素back()  返回队尾元素pop()  弹出队头元素priority_queue, 优先队列，默认是大根堆size()empty()push()  插入一个元素top()  返回堆顶元素pop()  弹出堆顶元素定义成小根堆的方式：priority_queue, greater> q;stack, 栈size()empty()push()  向栈顶插入一个元素top()  返回栈顶元素pop()  弹出栈顶元素deque, 双端队列size()empty()clear()front()/back()push_back()/pop_back()push_front()/pop_front()begin()/end()[]set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列size()empty()clear()begin()/end()++, -- 返回前驱和后继，时间复杂度 O(logn)set/multisetinsert()  插入一个数find()  查找一个数count()  返回某一个数的个数erase()(1) 输入是一个数x，删除所有x   O(k + logn)(2) 输入一个迭代器，删除这个迭代器lower_bound()/upper_bound()lower_bound(x)  返回大于等于x的最小的数的迭代器upper_bound(x)  返回大于x的最小的数的迭代器map/multimapinsert()  插入的数是一个pairerase()  输入的参数是pair或者迭代器find()[]  注意multimap不支持此操作。 时间复杂度是 O(logn)lower_bound()/upper_bound()unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表和上面类似，增删改查的时间复杂度是 O(1)不支持 lower_bound()/upper_bound()， 迭代器的++，--bitset, 圧位bitset<10000> s;~, &, |, ^>>, <<==, !=[]count()  返回有多少个1any()  判断是否至少有一个1none()  判断是否全为0set()  把所有位置成1set(k, v)  将第k位变成vreset()  把所有位变成0flip()  等价于~flip(k) 把第k位取反