AcWing算法基础课笔记与常用算法模板 (2) ——数据结构
常用算法代码模板 (1) :基础算法
常用算法代码模板 (2) :数据结构
常用算法代码模板 (3) :搜索与图论
常用算法代码模板 (4) :数学知识
算法基础课 模板题笔记:动态规划
算法基础课 模板题笔记:贪心
算法选择——由数据范围反推算法时间复杂度
文章目录
- 1 链表
- 1.1 单链表
- 1.2 双链表
- 2 栈
- 3 队列
- 3.1 非循环队列
- 3.2 循环队列
- 4 单调队列
- 4.1 单调栈
- 4.2 单调队列
- 5 模式匹配
- 5.1 暴力匹配
- 5.2 KMP
- 6 Trie树
- 7 并查集
- 7.1 朴素并查集
- 7.2 维护集合大小的并查集
- 7.3 维护到祖宗结点距离的并查集
- 8 堆
- 8.1 优先队列
- 8.2 数组堆
- 9 哈希
- 9.1 一般哈希
- 9.1.1 拉链法
- 9.1.2 开放寻址法
- 9.2 字符串哈希
1 链表
用链式前向星(静态链表)实现链表的定义、遍历与增删改查。
1.1 单链表
无头单链表。元素结点地址idx从0开始分配,表尾空指针记为-1。
int head, e[N], ne[N], idx; // head为无头单链表的头指针 // e[i]存储结点i的值 // ne[i]指向结点i的后继 // idx为分配给结点的"地址" /* 初始化 */ head = -1; // 头指针初始为-1 idx = 0; // 这里设定第1个插入的结点在0号下标 /* 头插一个数x */ void insert_head(int x) { e[idx] = x, ne[idx] = head, head = idx++; // 后继为开始结点 } /* 在结点k之后插入一个数x */ void insert(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx++; // 后继为k的后继 } /* 删除头结点(需保证链表非空) */ void remove_head() { head = ne[head]; } /* 删除结点k之后的结点 */ void remove(int k) { ne[k] = ne[ne[k]] } /* 遍历整条链表 */ for (int i = head; ~i; i = ne[i]) { int u = e[i]; ... }
1.2 双链表
带头循环双链表。规定0是头结点/左端点,只有后继;1是尾结点/右端点,只有前驱。元素结点地址idx从2开始分配,每个元素结点都不含空指针。
对于删除操作,为避免繁杂通常不直接将结点移出链表,而是通过开bool数组st[]标记结点来实现,st[i]记录结点i是否被删除。
int e[N], l[N], r[N], idx; // l[i]、r[i]分别指向结点i的前驱、后继 // 特殊规定:0是头结点/左端点,只有后继;1是尾结点/右端点,只有前驱 /* 初始化 */ r[0] = 1, l[1] = 0; // 左右端点分别指向对方 idx = 2; // 第1个结点从下标2开始存储 /* 在结点k的右边插入一个数x */ void insert_r(int k, int x) { e[idx] = x; l[idx] = k, r[idx] = r[k]; // 前驱为k,后继为k的后继 l[r[k]] = idx, r[k] = idx++; // k后继的前驱、k的后继(须最后修改)即为该结点 } /* 在结点k的左边插入一个数x */ void insert_l(int k, int x) { insert_r(l[k], x); // 等价于在结点k的前驱(l[k])的右边插入 } /* 删除结点k */ void remove(int k) { l[r[k]] = l[k]; r[l[k]] = r[k]; } /* 遍历整条链表 */ for (int i = r[0]; i != 1; i = r[i]) { int u = e[i]; ... }
2 栈
FILO。手工数组建栈可以实现对栈内元素的随机存取。
int stk[N], tt = -1; // stk[0 ... N-1] // 栈顶指针tt初始化为-1 /* 栈顶入栈一个数 */ stk[++tt] = x; /* 栈顶出栈一个数 */ tt--; /* 获取栈顶的值 */ stk[tt]; /* 判断栈是否为空 */ if (tt != -1) ...
3 队列
FIFO
3.1 非循环队列
手工建立的非循环队列队中元素不会被覆盖,由此可以实现对队内历史元素的遍历与随机存取,或根据指针判断某些性质(如拓扑序列)。
int q[N], hh = 0, tt = -1; // q[0 ... N-1] // 队头初始为0, 队尾初始和栈顶一样为-1 /* 队尾入队一个数 */ q[++tt] = x; /* 队头出队一个数 */ hh++; /* 队头、队尾的值 */ q[hh]; q[tt]; /* 判断队列是否为空 */ if (hh <= tt) ...
3.2 循环队列
int q[N], hh = 0, tt = 0; // q[0 ... N-1] // 队头和队尾指针初始均为0 /* 队尾入队一个数 */ q[tt++] = x; if (tt == N) tt = 0; /* 队头出队一个数 */ hh++; if (hh == N) hh = 0; /* 队头、队尾的值 */ q[hh]; q[tt]; /* 判断队列是否为空 */ if (hh != tt) ...
4 单调队列
核心思想:及时弹出必不会作为答案的数,使得容器内各所指元素始终单调
4.1 单调栈
常见模型:找出数列中每个数左边离它最近的比它大/小的数
/* 示例:输出数组a[n]中每个数左边离它最近的比它小的数,不存在则输出-1 */ int n, a[N]; // a[1 ... n] int stk[N], tt = -1; // 栈中存储数组元素下标 // 思想:若a[x] >= a[y] (x < y),则a[x]必不会是任何一数的答案,可直接剔除 for (int i = 0; i < n; i++) {// 双指针算法,i是子区间右端点 while (tt != -1 && a[stk[tt]] >= a[i]) tt--; // 弹出既大又"远"的数 if (tt != -1) printf("%d ", a[stk[tt]]); else printf("-1 "); stk[++tt] = i; }
4.2 单调队列
常见模型:找出滑动窗口中的最大值/最小值
/* 示例:输出滑动窗口每次前移时窗口内的最小值 */ int n, a[N]; // a[1 ... n] int k; // 滑动窗口的长度 int q[N], hh = 0, tt = -1; // 队列(双端队列)中存储数组元素下标 // 思想:同单调栈,且应输出的最值在队头(单调) for (int i = 0; i < n; i++) {// 双指针算法,i是子区间右端点 while (hh <= tt && i - k + 1 > q[hh]) hh++; // 判断队头是否滑出窗口 while (hh <= tt && a[q[tt]] >= a[i]) tt--; // 同单调栈,队尾弹出既大又"远"的数 q[++tt] = i; // 先将i从队尾入队 if (i + 1 >= k) printf("%d ", a[q[hh]]); // 当窗口长度达到要求时才输出 }
5 模式匹配
5.1 暴力匹配
时间复杂度: O ( n ⋅ m ) O(n\cdot m) O(n⋅m)
string s, p; if (s.find(p) != -1) ... // 匹配成功的操作
5.2 KMP
next数组: next [ i ] = \text{next}[i]= next[i]= 以 i i i 为终点的最大公共前后缀(此处规定包含 i i i )的长度
时间复杂度: O ( n + m ) O(n+m) O(n+m)
char s[N], p[N]; // 主串s[1 ... n]与模式串p[1 ... m](必须从下标1开始存储字符) int n, m; // 主串长度为n,模式串长度为m int ne[N]; // next数组 /* 初始化 */ scanf("%s%s", s + 1, p + 1); // 从下标1读取串至字符数组 n = strlen(s + 1), m = strlen(p + 1); // 获取有效存储长度 /* 求模式串p的next数组:p对p自己作KMP匹配 */ for (int i = 2, j = 0; i <= m; i++) {// ne[1]=0,故i从2开始遍历 while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j++; ne[i] = j; // 匹配成功则表明得到了以当前i为终点的最大公共前后缀的长度 } /* KMP匹配 */ for (int i = 1, j = 0; i <= n; i++) {// 始终与j的下一位(j+1)作匹配 while (j && s[i] != p[j + 1]) j = ne[j]; // 若j未退回起点且i与j的下一位不匹配,则j回溯 if (s[i] == p[j + 1]) j++; // 若i与j的下一位匹配,则j走至下一位 if (j == m) { // 匹配成功的操作 ... j = ne[j]; // 若要求找到所有匹配点,则j继续回溯、匹配 } }
6 Trie树
字典树(Retrieval Tree, Trie Tree)用于高效存储和查找字符串集合。
AC自动机为追加了fail指针的Trie树,算法思想参考KMP。
int son[N][26], cnt[N], idx; // son[p][u]记录结点p的第u个子结点(26表示26个字母) // cnt[p]存储以结点p结尾的单词数量 // idx初始为0(0号点既是根结点,又是空结点,故创建结点时为++idx) /* 插入一个字符串 */ void insert(char str[]) { int p = 0; // 从根结点0开始遍历Trie的指针 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]++; // p最终指向字符串末尾字母,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; // 不存在则直接返回0 p = son[p][u]; } return cnt[p]; // p最终指向字符串末尾字母,返回数量 }
7 并查集
使用树的双亲表示法顺序存储,p[x]存储结点x的父结点(经过路径更新后变为该结点所属集合的根结点/祖宗结点)。若p[x] == x(或find(x) == x),则x为该集合的根结点。
判断结点a和b是否在同一集合:find(a) == find(b)
7.1 朴素并查集
int n; // [1 ... n] int p[N]; // p[i]存储结点i的祖先结点(路径压缩后则为根结点),集合根结点的父结点为其自身 /* 初始化 */ for (int i = 1; i <= n; i++) p[i] = i; /* 并查集核心操作:返回结点x所属集合的根结点,并进行路径压缩 */ int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } /* 合并结点a和b所在集合:将a并至b */ p[find(a)] = find(b); // 将a的根接在b的根之后
7.2 维护集合大小的并查集
结点a所属集合的大小:cnt[find(a)]
int n; int p[N], cnt[N]; // cnt[i]存储根结点i的集合中结点数(仅根结点的cnt有意义) /* 初始化 */ for (int i = 1; i <= n; i++) { p[i] = i; cnt[i] = 1; // 初始化各结点为根,其所属集合大小为1 } /* 并查集核心操作 */ int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } /* 合并结点a和b所在集合:将a并至b */ if (find(a) == find(b)) continue; // 若已在同一集合内则跳过 cnt[find(b)] += cnt[find(a)]; // 需将a所属集合的大小加至b p[find(a)] = find(b);
7.3 维护到祖宗结点距离的并查集
int n; int p[N], d[N]; // d[i]存储结点i到其根结点p[i]的距离 /* 初始化 */ for (int i = 1; i <= n; i++) { p[i] = i; d[i] = 0; // 初始化全为0 } /* 并查集核心操作 */ int find(int x) { if (p[x] != x) { int u = find(p[x]); // u临时记录根结点 d[x] += d[p[x]]; // 更新x到根p[x]的路径长度 p[x] = u; } return p[x]; } /* 根据具体问题,初始化根find(a)的偏移量 */ d[find(a)] = distance; /* 合并结点a和b所在集合:将a并至b */ p[find(a)] = find(b);
8 堆
8.1 优先队列
priority_queue
max_heap; // 默认为大根堆 priority_queue , greater > min_heap; // 小根堆 8.2 数组堆
可实现堆中任意元素的插入删除操作,并建立与插入序列之间的映射关系。
int h[N], cnt; int ph[N], hp[N], idx; // h[1 ... cnt]为小根堆,h[1]为堆顶/最小值,结点u的左右儿子(若存在)分别为2u、2u+1 // ph[k]映射插入序列中第k个点到堆中的下标u (Position-Heap) // hp[u]映射堆中结点u到插入序列中的序号k (Heap-Position) /* 堆swap函数:交换堆中两个结点a和b的所有信息(若不建立映射则用std::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]); } /* 向下调整:一路向下交换结点u与其较小的儿子 */ void down(int u) { int t = u; // 记录u、2u、2u+1三个结点中的最小值结点编号 if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u; if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1; if (t != u) { heap_swap(u, t); down(t); } } /* 向上调整:一路向上交换结点u与其父结点 */ void up(int u) { while (u / 2 && h[u / 2] > h[u]) { heap_swap(u / 2, u); u >>= 1; } } /* 插入一个数x */ void insert(int x) { cnt++, idx++; ph[idx] = cnt, hp[cnt] = idx; h[cnt] = x; up(cnt); } /* 删除最小值/堆顶元素 */ void remove_top() { heap_swap(1, cnt); cnt--; down(1); } /* 删除第k个插入的元素 */ void remove(int k) { int u = ph[k]; heap_swap(u, cnt); cnt--; up(u), down(u); // 只会执行其中一个 } /* 修改第k个插入的元素为x */ void change(int k, int x) { int u= ph[k]; h[u] = x; up(u), down(u); // 只会执行其中一个 }
9 哈希
9.1 一般哈希
N最好取质数,使得冲突概率尽可能低
若要删除,则可额外开bool数组标记各地址元素状态来表示是否被删
9.1.1 拉链法
int h[N], e[N], ne[N], idx; /* 链表初始化 */ memset(h, -1, sizeof h); /* 向哈希表中插入一个数 */ void insert(int x) { int t = (x % N + N) % N; // C++的负数取余运算:(-n) mod k = -(n mod k) e[idx] = x, ne[idx] = h[t], h[t] = idx++; // 将x头插在链表h[t] } /* 在哈希表中查询某个数是否存在 */ bool find(int x) { int t = (x % N + N) % N; for (int i = h[t]; ~i; i = ne[i]) // 遍历整条链表h[t] if (e[i] == x) return true; return false; }
9.1.2 开放寻址法
数组长度应开到最大数据量的2~3倍
const int INF = 0x3f3f3f3f; // 表示该哈希值的元素不在哈希表内 int h[N]; /* 哈希表初始化 */ memset(h, 0x3f, sizeof h); // 初始化为无穷 /* 若x在哈希表中,返回x的下标;否则返回x应该插入的位置*/ int find(int x) { int t = (x % N + N) % N; while (h[t] != INF && h[t] != x) {// 若已存在该哈希值的元素且该元素不等于x t++; if (t == N) t = 0; } return t; }
9.2 字符串哈希
字符串前缀哈希法:快速判断两段字符串是否相等(不考虑冲突)
- 核心思想:将字符串看成 P P P 进制数, P P P 的经验值是 131 131 131 或 13331 13331 13331 ,取这两个值的冲突概率极低
- 小技巧:取模的数用
2
64
2^{64}
264,这样直接用unsigned long long存储,溢出的结果就是取模的结果
typedef unsigned long long ULL; const int P = 131; char str[N]; // 待哈希字符串str[1 ... n] int n; // 字符串的长度 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; // unsigned long long溢出相当于对2^64取模 } /* 计算子串str[l...r]的哈希值 */ ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }