达内培训网站开发,莱芜网红小莱芜,郴州网站建设维护,徐州最大的广告公司1.链表与邻接表#xff1a;树与图的存储
我们将结构体和指针结合来实现链表 struct Node
{int val;Node * next;
};
new Node;//这样创建结点是相当慢的 我们算法主要是用数组来模拟链表#xff0c;这样效率会高一些。
数组模拟单链表
邻接表#xff1a;存储图和树
实…
1.链表与邻接表树与图的存储
我们将结构体和指针结合来实现链表 struct Node
{int val;Node * next;
};
new Node;//这样创建结点是相当慢的 我们算法主要是用数组来模拟链表这样效率会高一些。
数组模拟单链表
邻接表存储图和树
实现一个单链表链表初始为空支持三种操作 向链表头插入一个数 删除第k个插入的数后面的数 在第k个前面插入一个数
#includeiostream
using namespace std;
const int N 100010;
//head为头结点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的节点next指针
//idx存储当前已经使用到的点的位置
int head, idx, e[N], ne[N];
void init()
{head -1;idx 0;
}
//将x插入到头结点
void add_to_head(int x)
{e[idx] x;ne[idx] head;head idx;idx;
}
//将x插入到k的节点位置
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]];
}
int main()
{int m;cin m;init();while(m--){int k, x;char op;cin op;if(op H){cin x;add_to_head(x);}else if(op D){cin k;if(k 0) head ne[head];remove(k-1);}else{cin k x;add(k-1, x);}}for(int i head;i ! -1;i ne[i]){cout e[i] ;}return 0;
}
数组模拟双链表的模板
#includeiostream
using namespace std;
const int N 100010;
int m;
int e[N], l[N], r[N], idx;
void init()
{//0表示左端点1表示右端点r[0] 1, l[1] 0;idx 2;
}
//在下标的k的右边插入x
void add(int k, int x)
{e[idx] x;r[idx] r[k];l[idx] k;l[r[k]] idx;r[k] idx;
}
//删除第k个点
void remove(int k)
{r[l[k]] r[k];l[r[k]] l[k];
}
2.栈与队列单调队列、单调栈
栈是先进后出队列是先进先出。
数组实现栈 #includeiostream
using namespace std;
const int N 100010;
int stk[N], tt;
//插入stk[tt] x;
//弹出tt--;
//判断栈是否为空 if(tt0) 不为空否则为空
//栈顶 stk[tt]; 数组实现队列 #includeiostream
using namespace std;
//在队尾插入元素在队头弹出元素
int q[N], hh, tt -1;
//判断队列是否为空
if(hh tt) not empty;
else empty;
//取出队头、队尾元素
q[hh];
q[tt]; 单调栈例题
给定一个长度为 N 的整数数列输出每个数左边第一个比它小的数如果不存在则输出 -1。 int tt;
for(int i 1;i n; i)
{while(tt check(q[tt], i)) t--;stk[tt] i;
} 题目代码
#includeiostream
using namespace std;
const int N 1e5 10;
int n;
int q[N], tt;
int main()
{scanf(%d, n);for(int i 0;i n; i){int x;scanf(%d,x);while(tt stk[tt] x) tt--;if(tt) printf(%d ,stk[tt]);else printf(-1 );stk[tt] x;}return 0;
}
只有出栈和入栈两次操作所以它的时间复杂度为O(n)
单调队列例题
移动窗口的例题k为窗口大小且k3打印出三个数中最小数如果窗口下数不足则输出-1
1 3 -1 -3 5 3 6 7
由上面的例子我们可以知道在3 -1 -3这个序列中3绝对不可能为最小值-3的生命周期要比3长。我们要优化该形式可以用单调队列的形式将不满足的点删掉。
我们的队列里存的不是值而是下标。 int hh 0, tt 1;
for(int i 0;i n; i)
{if(hh tt check_out(q[hh])) hh;while(hh tt check(q[tt],i)) tt--;q[tt] i;
} 本题代码
#includeiostream
using namespace std;
const int N 1e6 10;
int n,k;
int a[N], q[N];
int main()
{scanf(%d%d, n, k);for(int i 0;i n; i){scanf(%d, a[i]);}int hh 0, tt -1;for(int i 0;i n; i){//判断队头是否已经超出滑出窗口if(hh tt i - k 1 q[hh]) hh;while(hh tt a[q[tt]] a[i]) tt--;q[tt] i;if(i k - 1)printf(%d , a[q[hh]]);}printf();return 0;
}
3.kmp算法
KMP算法是一种字符串匹配算法用于在一个字符串中查找另一个字符串出现的位置。它的全名是Knuth-Morris-Pratt算法是由Donald Knuth、James H. Morris和Victor S. Pratt三人共同发明的。
S[N]p[M]我们如果用暴力算法朴素做法来做的话代码如下 for(int i 1;i n; i)
{bool flag true;for(int j 1;j m; j){if(s[i] ! p[j]){flag false;break;}}
} KMP算法的思想是在匹配过程中尽量利用已经匹配过的信息来快速跳过不匹配的位置从而达到减少匹配次数和提高匹配效率的目的。具体来说它通过预处理出一个next数组来记录匹配模式串中每个位置上最长的相同前缀和后缀的长度。在匹配过程中如果发现当前字符不匹配就可以利用next数组中记录的信息快速地将模式串向右移动一定的距离而无需重新从头开始匹配。
KMP算法的时间复杂度为O(mn)其中m和n分别为匹配串和模式串的长度。相比于暴力匹配算法KMP算法可以在很大程度上减少匹配的次数从而提高匹配的效率。但是KMP算法的实现比较复杂需要对next数组进行正确的计算和处理因此在实际应用中需要仔细考虑其实现方式和适用场景。
next[i] j p[1, j] p[i - j 1, i]
acwing的KMP算法例题
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串P在模式串S中多次作为子串出现。求出模板串P在模式串S中所有出现的位置的起始下标。
输入样例3 aba 5 ababa 输出0 2
代码
#includeiostream
using namespace std;
const int N 1e4 10, M 1e5 10;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{cin n p 1 m s 1;//求next的过程for(int i 2, j 0;i n; i){while(j p[i] ! p[j 1]) j ne[j];if(p[i] p[j 1]) j;ne[i] j;}//kmp的匹配过程for(int i 1, j 0;i m; i){while(j s[i] ! p[j 1]) j ne[j];if(s[i] p[j 1]) j;if(j n){//匹配成功printf(%d ,i - n);j ne[j];}}return 0;
}
4.Trie树
Trie又称前缀树或字典树是一种基于树结构的数据结构用于快速地检索和插入字符串。Trie的每个节点代表一个字符串的前缀从根节点到叶子节点的路径上表示一个完整的字符串。
Trie的特点是它的每个节点都有多个子节点每个子节点代表一个字符。根节点没有父节点每个非叶子节点的子节点数等于它的编号从0开始减去1。
在Trie中插入一个字符串的操作是从根节点开始按照字符串的字符顺序依次遍历每个字符如果当前节点的子节点中没有对应字符就新建一个子节点并将当前节点移动到该子节点。如果已经遍历到字符串的末尾则说明该字符串已经成功插入到Trie中。
Trie的另一个常见操作是查找一个字符串是否存在于Trie中。从根节点开始按照字符串的字符顺序依次遍历每个字符如果当前节点的子节点中没有对应字符则说明该字符串不存在于Trie中。如果已经遍历到字符串的末尾且当前节点是一个叶子节点则说明该字符串存在于Trie中。
Trie的主要优势是它可以快速地检索和插入字符串时间复杂度为O(m)其中m为字符串的长度。但是由于Trie的每个节点都需要存储多个子节点因此它的空间复杂度比较高适用于数据规模较小的情况。在大数据处理和文本处理等领域Trie通常被用来实现词典和关键字过滤等功能。
trie字符串统计
维护一个字符串集合支持两种操作 ‘lx’向集合中插入一个字符串x ‘Qx’询问一个字符串在集合中出现了多少次
一共有N次操作输入的字符串总长度不超过105字符串仅包含小写英文字母。
#includeiostream
using namespace std;
const int N 1e5 10;
int son[N][26], cnt[N], idx;//下标是0的点既是根节点有是空节点
int str[N];
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];
}
int main()
{int n;scanf(%d, n);while(n--){char op[2];scanf(%s%s, op, str);if(op I) insert(str);else printf(%d\n, query(str));}return 0;
}
最大异或对
5.并查集
并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题。 将两个集合合并 询问两个元素是否在一个集合当中。
基本原理每隔几何用一棵树来表示树根的编号就是一整个集合的编号。每个节点存储它的父节点p[x]表示x的父节点。
问题1如何判断树根if(p[x] x);
问题2如何求x的集合编号while(p[x] ! x) x p[x];
问题3如何合并两个集合px是x的集合编号py是y的集合编号。p[x] y
基本上来说是O(1)的时间复杂度
合并集合
一共有n个数编号是1~n最开始每个数各自在一个集合中。
现在要进行m个操作操作一共有两种 将编号为ab的两个数所在集合进行合并如果两个数已经在集合中即忽略这个操作 询问编号为ab的两个数是否在同一个集合中
#includeiostream
using namespace std;
const int N 1e5 10;
int n, m;
int p[N];
int find(int x)//返回x的祖宗结点路径压缩
{if(p[x] ! x) p[x] find(p[x]);return p[x];
}
void merge(int a, int b)
{p[find(a)] find(b);
}
int main()
{scanf(%d%d, n, m);for(int i 1;i n; i)p[i] i;while(m--){char op[2];int a, b;scanf(%s%d%d, op, a, b);if(op[0] M)merge(a, b);else{if(find(a) find(b))printf(Yes\n);elseprintf(No\n);}}return 0;
}
近乎O(1)的时间
连通块中点的数量
给定一个包含n个点编号为1~n的无向图初始时图中没有边。
现在要进行m个操作操作一共有三个 “Cab”在点a和点b之间连一条边a和b可能相等 “Q1ab”询问点a和点b是否在同一连通块内a和b可能相等 “Q2ab”询问点a所在的联通快中点的个数。
#includeiostream
using namespace std;
const int N 1e5 10;
int n, m;
int p[N], size[N];
int find(int x)
{if(p[x] ! x) p[x] find(p[x]);return p[x];
}
void merge(int a, int b)
{p[find(a)] find(b);
}
int main()
{scanf(%d%d, n, m);for(int i 1;i n; i){p[i] i;size[i] 1;}while(m--){char op[5];int a, b;scanf(%s, op);if(op[0] C){scanf(%d%d, a, b);if(find(a) find(b)) continue;size[find(b)] size[find(a)];merge(a, b);}else if(op[1] 1){scanf(%d%d, a, b);if(find(a) find(b))printf(Yes\n);elseprintf(No\n);}else{scanf(%d, a);printf(%d\n, size[find(a)]);}}return 0;
}
食物链
动物王国中有三类动物A,B,C这三类动物的食物链构成了有趣的环形。
A吃B B吃CC吃A。
现有N个动物以1N编号。
每个动物都是A,B,C中的一种但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述
第一种说法是”1 X Y”表示X和Y是同类。
第二种说法是”2 X Y”表示X吃Y。
此人对N个动物用上述两种说法一句接一句地说出K句话这K句话有的是真的有的是假的。
当一句话满足下列三条之一时这句话就是假话否则就是真话。
1 当前的话与前面的某些真的话冲突就是假话 2 当前的话中X或Y比N大就是假话 3 当前的话表示X吃X就是假话。
你的任务是根据给定的N和K句话输出假话的总数。
#includeiostream
using namespace std;
int main()
{return 0;
} 6.堆
如何手写一个堆
堆是维护数与集合。
堆是一种数据结构它满足以下两个条件 完全二叉树堆的总是一棵完全二叉树即除了最后一层外其他层都是满的并且最后一层的节点都集中在左侧。 堆性质对于每个节点X其父节点的值小于等于或大于等于称为最小堆其子节点的值。
堆通常用于实现优先队列其中每个节点代表一个事件或任务节点的值表示任务的优先级。通过将任务按照优先级从上到下放置在堆中可以保证优先级最高的任务总是最先被执行。
在实现上堆可以使用数组来表示。对于一个节点X其父节点和子节点的位置可以通过简单的数学计算来确定。例如对于一个最小堆节点X的父节点和左子节点的位置可以通过以下公式计算 父节点位置parent(X) (X-1)/2 左子节点位置left_child(X) 2*X 1
堆也可以用来实现优先级调度、任务调度等应用。 插入一个数 heap[size] x; up(size); 求集合当中的最小值 heap[1]; 删除最小值 用最后一个元素覆盖根节点 heap[1] heap[size];size--;down(1); 删除任意元素 heap[k] heap[size];size--; 修改任意元素 heap[k] x; down(k); up(k);
838.堆排序
输入一个长度为n的整数数列从小到大输出前m小的数。
输入格式第一行包含整数n和m第二行包含n个整数表示整数数列。
输出格式共一行包含m个整数表示整数数列中前m小的数。
5 3 \n 4 5 1 3 2
1 2 3
代码
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
int n, m;
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(h[u], h[t]);down(t);}
}
int main()
{scanf(%d%d, n, m);for(int i 1;i n; i)scanf(%d, h[i]);size n;for(int i n / 2; i; i--)down(i);while(m--){printf(%d , h[1]);h[1] h[size];size--;down(1);}return 0;
}
839.模拟堆
维护一个集合初始时集合为空支持如下几种操作 lx插入一个数x “PM”输出当前集合中的最小值 “DM”删除当前集合的最小值当最小值不唯一时删除最早插入的最小值 “Dk”删除第k个插入的数 “Ckx”修改第k个插入的数将其变为x
现在要进行N次操作。对于所有第2个操作输出当前集合的是小值。
#includeiostream
#includealgorithm
#includestring.h
using namespace std;
const int N 1e5 10;
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 / 2] h[u]){heap_swap(u / 2, u);u / 2;}
}
int main()
{int n, m 0;scanf(%d, n);while(n--){char op[10];int k, x;scanf(%s, op);if(!strcmp(op, I)){scanf(%d, x);size;m;ph[m] size, hp[size] m;h[size] x;up(size);}else if(!strcmp(op, PM)) printf(%d\n, h[1]);else if(!strcmp(op, DM)){heap_swap(1, size);size--;down(1);}else if(!strcmp(op, D)){scanf(%d, k);k ph[k];heap_swap(k, size);size--;down(k), up(k);}else{scanf(%d%d, k, x);k ph[k];h[k] x;down(k), up(k);}}return 0;
}
7.Hash表
哈希表是一种使用哈希函数组织数据以支持快速插入和搜索的数据结构。
哈希表可以用来实现动态集合。它支持以下操作 插入将一个元素插入到哈希表中。 删除将一个元素从哈希表中删除。 搜索在哈希表中查找一个元素。
哈希表的实现基于哈希函数它将键映射到存储桶bucket中。每个存储桶是一个链表链表中的每个节点都包含一个键值对。当插入一个元素时哈希函数将键映射到一个存储桶然后将元素添加到该存储桶的链表中。当搜索一个元素时哈希函数将键映射到相应的存储桶然后在该存储桶的链表中查找元素。
哈希表有多种实现方式其中最常用的是开放地址法和相联数组法。开放地址法在哈希表中使用一个数组来存储存储桶当发生哈希冲突时它使用线性探测、二次探测、双重散列等方法来找到空槽位。相联数组法在哈希表中直接使用一个数组来存储键值对当发生哈希冲突时它将新元素添加到数组的末尾。
哈希表在计算机科学中广泛应用例如在数据库、操作系统、网络通信等领域。它能够提供常数级别的查找效率比其他数据结构更高效。
7.1哈希表的存储结构
1.开放寻址法 2.拉链法
840.模拟散列表
维护一个集合支持如下几种操作 “lx”插入一个数 “Qx”询问数x是否在集合中出现过
现在要进行N次操作对于每个询问操作输出对应的结果
一般情况下对哈希函数进行取模但是由于取模的原因可能会有冲突若干不同的数可能会映射在同一个位置。
开放寻址法
#includeiostream
#includecstring
using namespace std;
cosnt int N 200003, null 0x3f3f3f3f;
int h[N];
int find(int n)
{int t (x % N N) % N;while(h[t] ! null h[t] ! x){t;if(t N)t 0;}return t;
}
int main()
{int n;scanf(%d, n);merset(h, 0x3f, sizeof(h));while(n--){char op[2];int x;scanf(%s%d, op, x);int k find(x);if (op I){h[k] x;}else{if (h[k] ! null) puts(Yes);elseputs(No);}}return 0;
}
拉链法
#includeiostream
#includecstring
using namespace std;
const int N 100003;
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;elsereturn false;
}
int main()
{int n;scanf(%d, n);memset(h, -1, sizeof(h));while(n--){char op[2];int x;scanf(%s%d, op, x);if(op I) insert(x);else{if(find(x)) puts(Yes);else puts(No);}}return 0;
}
7.2.字符串前缀哈希方法
str ABCDEFADCYUGHJJDFDGKHJK
预处理特殊h[0] 0
h[1] A的对应的哈希值后面的一样 h[2] AB h[3] ABC..... 不能映射为0 Rp足够好不产生冲突
841.字符串哈希
给定个长度为的字符串再给定m个询问每个询问包含四个整数l1r1l2r2请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
#includeiostream
using namespace std;
typedef unsigned long long ULL;
const int N 100010;
int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l 1];
}
int main()
{scanf(%d%d%s, n, m, str 1);p[0] 1;for(int i 1;i n; i){p[i] p[i-1] * p;h[i] h[i-1] * p str[i];}while(m--){int l1, r1, l2, r2;scanf(%d%d%d%d,l1, r1, l2, r2);if(get(l1, r1) get(l2, r2))puts(Yes);elseputs(No);}return 0;
}
8.CSTL使用技巧
vector变长数组倍增的思想
string字符串substr()c_str()
queue队列push(), front(), pop()
priority_queue优先队列push() top()pop()
stack栈push(), top(), pop()
deque双增队列
set, map, multiset和multimap基于平衡二叉树动态维护有序序列
unorder_set、unorder_map、unorder_multiset、unorder_multimap基于哈希表
bitset压位
list
#includeiostream
#includealgorithm
#includevector
#includecstring
#includecstdio
using namespace std;
int main()
{vectorint a(10, 3);//vectorint a[10];a.size();//返回元素个数a.empty();//返回是否为空a.clear();//清空a.front();//返回第一个数a.back();//返回最后一个数a.push_back();//尾插a.pop_back();//尾部释放a.begin()/a.end();//vector的迭代器for(int i 0;i 10; i)a.push_back();for(int i 0;i a.size(); i)cout a[i] ;cout endl;for(vectorint::iterator i a.begin();i ! a.end(); i)cout a[i] ;cout endl;//支持比较运算vectorint a(4, 3), b(3, 4);if(a b) cout a b endl;return 0;
}
系统内某一程序分配空间时所需时间与空间大小无关与中间次数有关
pairint, int存储一个二元组
#includeiostream
#includecstring
#includealgorithm
#includecstdio
#includevector
using namespace std;
int main()
{pairint, stringp;p.first;p.second;//支持比较运算//以first为第一关键词以second为第二关键词p make_pair(10, yxc);p {20, abc};pairint, pairintw;return 0;
}
string
#includeiostream
#includecstring
#includealgorithm
using namespace std;
int main()
{string a yxc;a def;a c;cout a endl;cout a.substr(2, 3) endl;return 0;
}
queue队列
#includeiostream
#includequeue
#includealgorithm
#includevector
using namespace std;
int main()
{queueint q;q queueint;//优先队列priority_queueint heap;heap.clear();priority_queueint, vectorint, greaterint heap;//定义一个小根堆return 0;
}
stack栈
deque双端队列
size() empty() clear() front() back() push_front() pop_front() push_back pop_back() begin() end()
缺点就是deque比较慢
set
#includeiostream
#includevector
#includeset
#includealgorithm
using namespace std;
int main()
{setint S;multisetint S1;//可以有重复元素set不允许S.insert(1);//插入一个数S.find();//查找一个数S.count();//返回某一个数的个数S.erase();//1.输入的是一个数就删除该数的所有存储 2.输入一个迭代器就删除这个迭代器S.lower_bound(x);//返回大于等于x的最小的数的迭代器S.upper_bound(x);//返回大于x的最小数的迭代器return 0;
}
map/multimap
insert()插入的数是一个pair erase()输入的参数是pair或者是迭代器 find()
[] 时间复杂度是O(nlogn) lower_bound() upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap
哈希表 和上面的类似增删查改的时间复杂度是O(1)
不支持lower_bound()和upper_bound()迭代器的、--
bitset压位
bitset10000S;~, , |, ^, , , , !,
count()返回有多少个1
any()判断是否至少有一个1
none()判断是否为0
set()把所有位置都换成1
reset()把所有位都变成0
flip()等价~ flip(k)把第k位反转。
