1.链表与邻接表:树与图的存储

我们将结构体和指针结合来实现链表
struct Node {    int val;    Node * next; }; ​ new Node;//这样创建结点是相当慢的
我们算法主要是用数组来模拟链表,这样效率会高一些。

数组模拟单链表

邻接表:存储图和树

实现一个单链表,链表初始为空,支持三种操作:

*
向链表头插入一个数

*
删除第k个插入的数后面的数

*
在第k个前面插入一个数
#include<iostream> 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; }
数组模拟双链表的模板:
#include<iostream> 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.栈与队列:单调队列、单调栈

栈是先进后出,队列是先进先出。

数组实现栈:
#include<iostream> using namespace std; ​ const int N = 100010; ​ int stk[N],
tt; ​ //插入stk[++tt] = x; ​ //弹出tt--; ​ //判断栈是否为空 if(tt>0) 不为空,否则为空 ​ //栈顶
stk[tt];
数组实现队列
#include<iostream> 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; }
题目代码:
#include<iostream> 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为窗口大小且k=3,打印出三个数中最小数,如果窗口下数不足,则输出-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; }
本题代码
#include<iostream> 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(m+n),其中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

代码:
#include<iostream> 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,字符串仅包含小写英文字母。
#include<iostream> 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个操作,操作一共有两种

*
将编号为a,b的两个数所在集合进行合并,如果两个数已经在集合中,即忽略这个操作

*
询问编号为a,b的两个数是否在同一个集合中
#include<iostream> 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");            else                printf("No\n");       }   }
       return 0; }
近乎O(1)的时间

连通块中点的数量:

给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。

现在要进行m个操作,操作一共有三个:

*
“Cab”,在点a和点b之间连一条边,a和b可能相等

*
“Q1ab”,询问点a和点b是否在同一连通块内,a和b可能相等

*
“Q2ab”,询问点a所在的联通快中点的个数。
#include<iostream> 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");            else
               printf("No\n");       }        else       {          
 scanf("%d", &a);            printf("%d\n", size[find(a)]);       }           }
   return 0; }
食物链

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。

A吃B, B吃C,C吃A。

现有N个动物,以1-N编号。

每个动物都是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句话,输出假话的总数。
#include<iostream> 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

代码:
#include<iostream> #include<algorithm> ​ 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个操作,输出当前集合的是小值。
#include<iostream> #include<algorithm> #include<string.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次操作,对于每个询问操作输出对应的结果

一般情况下,对哈希函数进行取模,但是由于取模的原因,可能会有冲突,若干不同的数可能会映射在同一个位置。

开放寻址法:
#include<iostream> #include<cstring> ​ 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");          
 else                puts("No");       }   }    return 0; }
拉链法:
#include<iostream> #include<cstring> ​ 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;   else            return 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个询问,每个询问包含四个整数l1,r1,l2,r2,请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。
#include<iostream> 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");        else            puts("No");   }    return 0; }
8.C++STL使用技巧

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
#include<iostream> #include<algorithm> #include<vector> #include<cstring>
#include<cstdio> ​ using namespace std; ​ int main() {    vector<int> a(10, 3);
   //vector<int> 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(vector<int>::iterator i = a.begin();i != a.end(); i++)        cout << a[i]
<< ' ';    cout << endl;       //支持比较运算    vector<int> a(4, 3), b(3, 4);  
 if(a > b) cout << "a > b" << endl;        return 0; }
系统内某一程序分配空间时,所需时间,与空间大小无关,与中间次数有关

pair<int, int>:存储一个二元组
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio>
#include<vector> ​ using namespace std; ​ int main() {    pair<int, string>p;  
     p.first;    p.second;    //支持比较运算    //以first为第一关键词,以second为第二关键词        p
= make_pair(10, "yxc");    p = {20, "abc"};        pair<int, pair<int>>w;  
 return 0; }
string
#include<iostream> #include<cstring> #include<algorithm> ​ using namespace
std; ​ int main() {    string a = "yxc";        a += "def";    a += "c";      
 cout << a << endl;    cout << a.substr(2, 3) << endl;        return 0; }
queue队列
#include<iostream> #include<queue> #include<algorithm> #include<vector> ​
using namespace std; ​ int main() {    queue<int> q;        q = queue<int>;    
   //优先队列    priority_queue<int> heap;    heap.clear();      
 priority_queue<int, vector<int>, greater<int>> heap;//定义一个小根堆    return 0; }
stack栈

deque双端队列

size() empty() clear() front() back() push_front() pop_front() push_back
pop_back() begin() end()

缺点就是deque比较慢

set
#include<iostream> #include<vector> #include<set> #include<algorithm> ​ using
namespace std; ​ int main() {    set<int> S;    multiset<int>
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,压位

bitset<10000>S;~, &, |, ^, >>, <<, ==, !=,

count()返回有多少个1

any()判断是否至少有一个1

none()判断是否为0

set()把所有位置都换成1

reset()把所有位都变成0

flip()等价~ flip(k)把第k位反转。

 

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信