单链表
const int N=1e5+10;
int head[N],e[N],ne[N],idx;
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
//初始化
void init()
{
head=-1,idx=0;
}
//在表头插入一个值为X的点
void add_to_head(int x)
{
e[idx]=x,ne[idx]=head,head=idx++;
}
//在第k个节点后面加入x
void add(int k,int x)
{
e[idx]=x, ne[idx]=ne[k],ne[k]=idx,idx++;
}
// 删除第k个节点
void remove(int k)
{
ne[k] = ne[ne[k]];//y总的删除避免删除头尾,nice
}
/** 遍历链表 */
void print()
{
for (int i = ne[head]; i != -1; i = ne[i]) cout << e[i] << " ";
}
**`采用含头结点的单链表,头结点存储链表长度`**
**`元素从下标1开始存储`**
双链表
const int N = 100005;
int e[N], l[N], r[N], idx;
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
//初始化
void init()
{
r[0]=1,l[1]=0,idx=2;
}
// 在第k个节点与第k+1个节点之间插入值为x的点
void insert(int k, int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[l[k]]=k;
idx++;
}
// 删除第k个点
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
/** 输出 */
void print()
{
for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
//从左往右,从右往左都可以输出
}
**`实现的双链表含头结点和尾结点,下标分别为0和1`**
**`insert()函数可根据参数的选取实现在链表任意位置插入的功能(包括头插和尾插)`**
**`遍历时从头结点的下一个位置开始(r[0]),直到遍历到尾结点(下标为0)`**
栈模拟
const int N = 100005;
int stk[N], tt = 0;
// stk为栈,tt为栈顶
// 插入值为x的元素
void push(int x)
{
tt ++; // 开辟一个新的空间
stk[tt] = x; // 将x放入空间
}
// 弹出栈顶
void pop()
{
if(tt >= 0) // 如果栈不空
tt --;
}
// 返回栈的大小
int size()
{
return tt;
}
// 返回栈是否为空
bool empty()
{
if(tt >= 1) // 栈不空
return false;
else
return true;
// 可以用"return tt < 1;"代替
}
// 求栈顶元素
int top()
{
return stk[tt];
}
**`栈从下标1开始存储元素`**
**`栈指针tt的值可表示栈的实际长度`**
队列模拟
const int N = 100005;
int q[N], hh = 0, tt = -1;
// q为队列,hh为队头,tt为队尾
// 在队尾插入值为x的元素
void push_back(int x)
{
tt ++; // 开辟出新的空间
q[tt] = x; // 将x放入空间
}
// 弹出队尾
void pop_front()
{
if(hh <= tt) // 如果队列不空
hh ++;
}
// 返回队列的大小
int size()
{
return tt - hh + 1;
}
// 返回队列的大小
bool empty()
{
if(hh <= tt) // 如果队列不空
return false;
else
return true;
// 可以用"return hh > tt"代替
}
单调栈
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
`**时间复杂度由O(n^2)变为O(n)**`
单调队列
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;
}
`**时间复杂度由O(nk)O(nk)降为O(n+k)**`
KMP
// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度(s,p都从1开始)
// 求模式串的Next数组:
for(int i=2,j=0;i<=m;i++)
{
while(j&&p[i]!=p[j+1])j=ne[j];//找到能和p[i]匹配的p[j + 1]
if(p[i]==p[j+1])j++;// 如果匹配到了,j向后走一位
ne[j]=j;
}
// 匹配
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=p[j+1])j=ne[j];// 找到能和s[i]匹配的p[j + 1]
if(s[i]==s[j+1])j++; // 如果匹配到了
if(j==m)
{
j=ne[j]; // 匹配成功后的逻辑
......
}
}
`**使用KMP算法时,起始下标为1**`
`**字符串可用char数组保存,读入时用cin >> p + 1读取,表示从下标1开始写入字符串**`
`**求next数组时,由于ne[1]初始化已经为0,故从2开始计算**`
`**j == 0表示从头开始匹配模式串,匹配时用p[j + 1]比较**`
Trie 树
const int N = 100005;
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[i][j]存储树中i节点的子节点j
// cnt[i]存储以i节点结尾的单词数量
// 注意:str[i]在这里都是小写字母!!!
// 插入一个字符串
void insert(char str[]){
int p = 0; // p表示现在走到哪个点了
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a'; // 算出str[i]对应的u
if(!son[p][u]) // 如果p没有子节点u
son[p][u] = ++ idx; // 就加上儿子节点u
p = son[p][u]; // p走到下一个位置
}
cnt[p] ++; // 以p结尾的单词数目+1
}
// 查询字符串出现的次数
int query(char str[]){
int p = 0; // p表示现在走到哪个点了
for(int i = 0; str[i]; i ++){
int u = str[i] - 'a'; // 算出str[i]对应的u
if(!son[p][u]) // 如果p没有子节点u
return 0; // 没有这个单词
p = son[p][u]; // p走到下一个位置
}
return cnt[p]; // 返回以p结尾的单词个数
}
**Trie树是多重集合**
**son数组的第1维表示结点地址,要大于所有存储的字符串长度的和(不是字符串长度的最大值);**
**第2维表示每个结点的最大分支数,一般取字符种类数(如小写字母有26个)**
**cnt[i]表示以son[i]结点为末尾的字符串的个数**
并查集
1.朴素版
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]); // 路径压缩
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
// 判断两个结点是否属于同一集合
if (find(a) == find(b)) {...}
**查找函数中使用了路径压缩优化并查集结构,使得每个非根结点直接连到根节点上,每棵树的深度不超过`2`**
**判断两个数是否属于同一个集合等价于判断两个数的祖宗结点是否相同,即`find(a) == find(b)`**
**合并操作本质是把其中一个祖宗结点连接到另一个祖宗结点上**
维护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~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1; // 变动部分
}
// 合并a和b所在的两个集合:
int x = find(a), y = find(b);
if (x != y) {
p[x] = y;
size[y] += size[x];
}
// 判断两个结点是否属于同一集合
if (find(a) == find(b)) {...}
**size[x]存储的是以该结点为根的树的结点树**
**在合并操作中,可以不必把find(a)和find(b)存入两个变量。**
**因为第一次调用find()时会进行路径压缩,下一次调用就是O(1)复杂度了。**
**但要注意先修改size再合并结点,二者顺序不可颠倒,因为结点含义会改变**
**改变size时,要先判断两个集合是否为同一个**
**在两个彼此不连通的连通图加上一条边连通二者,等价于把两个集合合并**
**为了避免合并步骤中出现顺序问题,可以用两个变量表示,同时也减少了代码量**
维护到祖宗节点距离的并查集
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[p[x]]
d[x] += d[p[x]]; // 再更新d[x]
p[x] = u; // 最后更新p[x]
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0; // 自身到自身的距离是0
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
`**注意find函数语句的先后次序,次序不对可能会导致含义错误**`
堆
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
int h[N], size;
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)
{
swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(u, u / 2);
u >>= 1;
}
}
// --------------------------------基本操作--------------------------------
// 0. 建堆
void init() {
for (int i = n / 2; i; i -- ) down(i);
}
// 1. 插入一个数
void insert(int x) {
h[++size] = x;
up[size];
}
// 2. 求最小值
int top() {
return h[1];
}
// 3. 删除最小值
void remove() {
h[1] = h[size];
size--;
down(1);
}
// 4. 删除任意位置的元素(STL没有)
void remove(int k) {
h[k] = h[size];
size--;
down(k);
up(k);
}
// 5. 修改任意位置的元素(STL没有)
void update(int k, int x) {
h[k] = x;
down(k);
up(k);
}
**所有基本操作都可由up()和down()组合而成**
**建堆的时间可以看做是O(n),因为只有n2个结点参与建堆,**
**这些结点向下调整的次数至多为**
**2h−1×1+2h−2×2+21×(d−2)+20×(d−1),**
**由错位相减法可知结果<n**
**实现down时,注意t的含义是当前最小结点的下标,是变化的,而u是不变的,不要与u的含义弄混**
**STL没有基本操作4和基本操作5,尽管它们实现时同时调用了down()和up(),但实际上只会执行其中一个**
**建堆是从n/2逆着遍历到1**
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size, m;
// 加强swap
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); // 加强swap
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2); // 加强swap
u >>= 1;
}
}
// --------------------------------基本操作--------------------------------
// 0. 建堆
void init() {
for (int i = n / 2; i; i -- ) down(i);
}
// 1. 插入一个数
void insert(int x) {
h[++size] = x;
ph[++m] = size; // m为当前插入的序号
hp[size] = m;
up[size];
}
// 2. 求最小值
int top() {
return h[1];
}
// 3. 删除最小值
void remove() {
heap_swap(1, siz); // 加强swap
size--;
down(1);
}
// 4. 删除第k次插入的元素(STL没有)
void remove(int k) {
k = ph[k];
heap_swap(k, size); // 加强swap
size--;
down(k);
up(k);
}
// 5. 修改第k次插入的元素(STL没有)
void update(int k, int x) {
k = ph[k];
h[k] = x;
down(k);
up(k);
}
**加强模板额外存储了插入记录ph,映射插入序号和元素在堆中的位置,**
**同时构建了ph的逆映射hp,可根据堆中的下标反推插入序号**
**所有swap改成加强版的heap_swap,因为要维护ph和hp**
**在heap_swap中,由于参数是下标,但ph数组需要提供插入序号k,因此可用数组hp的值来作为ph的下标**
哈希表
// (1) 拉链法
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) 开放寻址法
const int null = 0x3f3f3f3f;
int h[N];
memset(h, 0x3f, sizeof h); // 给h的每个字节初始化成0x3f,使得每个元素的值都是null
// 如果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;
}
**(x % N + N) % N首先把x缩放到满足abs(x) < N,由于第一次求余的结果可能是负数,因此还要再进行一次求余
用单链表实现拉链法
用质数作为长度可以使得冲突最少(数学能证明)
可以事先实现一个求质数的函数,算出比N大的最小质数,作为N的值
离散化是哈希的特例,因为离散化要求相对顺序不变,而哈希没有要求
哈希表的删除是通过标记实现的
开放寻址法手动设定null的值,其值可根据题目给出的元素数值范围设计。
例如元素值的绝对值≤109,又知0x3F>109,但memset只能按字节赋值,
故可考虑0x3F3F3F3F,经检验它>109,故可使用memset(h, 0x3f, sizeof h);
为数组元素“赋”初值null**
字符串哈希
`O(1)代价计算子串的哈希值`
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
const int P = 131; // 或13331
// 初始化
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];
}
**核心思想:将字符串看成P进制数,P的经验值是131或13331,取这两个值的冲突概率低**
**小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果**
**质数p可取经验值131或13331**
STL模板
// vector, 变长数组,倍增的思想
size() // 返回元素个数
empty() // 返回是否为空
clear() // 清空
front() / back()
push_back() / pop_back()
begin() / end()
[]
// 支持比较运算,按字典序
// pair<int, int>
first, 第一个元素
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<int, vector<int>, greater<int>> 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/multiset
insert() // 插入一个数
find() // 查找一个数
count() // 返回某一个数的个数
erase()
// (1) 输入是一个数x,删除所有x O(k + logn)
// (2) 输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) // 返回大于等于x的最小的数的迭代器
upper_bound(x) // 返回大于x的最小的数的迭代器
// map/multimap
insert() // 插入的数是一个pair
erase() // 输入的参数是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() // 返回有多少个1
any() // 判断是否至少有一个1
none() // 判断是否全为0
set() // 把所有位置成1
set(k, v) // 将第k位变成v
reset() // 把所有位变成0
flip() // 等价于~
flip(k) // 把第k位取反
**系统为某程序分配空间所需要的时间与空间大小无关,而与申请次数有关**
**priority-queue默认是大根堆,可通过插入-x变成小根堆**