acwing刷题指南7

//数据结构篇

 

好像单链表和双链表没写到上面来，不过没事，后面图论再写

题目列表：

828. 模拟栈

829. 模拟队列

830. 单调栈（找在右边比自己小的数，构成单调递增区间（反之））

154. 滑动窗口（类似于单调栈不过又像极了双端队列）

P1614 爱与愁的心痛

都可以画图解释

836. 合并集合（并查集）

837. 连通块中点的数量

学习笔记：

for(int i = 0; i < 8; i ++) p[i] = i;//初始化

得到下图

 很容易理解，就是将当前数据的父节点指向自己

查找 + 路径压缩

find(1) p[1] = 2  p[1] = find(2)
find(2) p[2] = 3  p[2] = find(3)
find(3) p[3] = 4  p[3] = find(4)
find(4) p[4] = 4  将p[4]返回

退到上一层
find(3) p[3] = 4  p[3] = 4 将p[3]返回
退到上一层
find(2) p[2] = 3  p[2] = 4 将p[2]返回
退到上一层
find(1) p[1] = 2  p[1] = 4 将p[1]返回

至此，我们发现所有的1，2，3的父节点全部置为了4，实现路径压缩；同时也实现了1的父节点的返回

合并操作
if(op[0] == ‘M’) fa[find(a)] = find(b); //将a的祖先点的父节点置为b的祖先节点

其他路径压缩方法

1.路径分裂：使路径上的每个节点都指向其祖父节点（parent的parent）(这是我们这题836. 合并集合所选择用的)

2 路径减半：使路径上每隔一个节点就指向其祖父节点（parent的parent）

 int find(int x){

    while(x != fa[x]){

        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

总结
并查集
1.将两个集合合并
2.询问两个元素是否在一个集合中

基本原理：每个集合用一棵树来表示。树的编号就是整个集合的编号。每个节点存储它的父节点，fa[x]表示x的父节点

1.判断树根 if(fa[x] = x)
2.求x的集合编号 while(fa[x] != x) x = fa[x]
3.合并两个集合，这两将x的根节点嫁接到y的根节点, px为x的根节点， py为y的根节点，嫁接p[px] = py

字符串算法：

831. KMP字符串(KMP主要分两步：求next数组、匹配字符串)

835. Trie字符串统计

Trie树(是一种能够高效存储和查找字符串集合的数据结构)

Trie树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。

Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2;如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

堆：

838. 堆排序

hash:

840. 模拟散列表

828. 模拟栈

模板题

有手就行

#include<iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;
int m;
void push(int x)
{

    tt++;
    stk[tt] = x;
}
void pop()
{

    tt–;
}
void empty()
{

    if(tt)cout<<“NO”<<endl;
    else cout<<“YES”<<endl;
}
int query()
{

    return stk[tt];
}

int main()
{

    cin>>m;
    while(m–)
    {

        string op;
        cin>>op;
        if(op == “push”)
        {

            int x;
            cin>>x;
            push(x);
        }
        else if(op == “pop”)pop();
        else if(op == “empty”)empty();
        else cout<<query()<<endl;
    }
    return 0;
}

829. 模拟队列（有手就行）

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int hh,tt=-1,q[N],n;
int main()
{

    cin>>n;
    while(n–)
    {

        int x;
        string op;
        cin>>op;
        if(op == “push”)
        {

            cin>>x;
            q[++tt] = x;
        }
        else if(op == “pop”) hh++;
           
        else if(op == “empty”)cout<<(hh <= tt ? “NO”:”YES”)<<endl;
        
        else cout<<q[hh]<<endl;
    }
    return 0;
}

830. 单调栈

#include<iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;
int n;
int main()
{

    cin>>n;
    while(n–)
    {

        int x;
        cin>>x;
        while(tt && stk[tt] >= x)tt–;
        if(!tt)cout<<“-1″<<” “;
        else cout<<stk[tt]<<” “;
        stk[++tt] = x;
    }
    return 0;
}

154. 滑动窗口(求最大最小可以镜像求解即可)

#include<iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];//a[N]表示原数组，q[N]表示单调队列
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

//86ms的速度快吧

    cin>>n>>k;
    for(int i = 0;i < n;i++)cin>>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) cout<<a[q[hh]]<<” “;
    }
    cout<<endl;
    
     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)cout<<a[q[hh]]<<” “;
        
    }
   cout<<endl;
    return 0;
}

P1614 爱与愁的心痛

(滑动窗口和前缀和都可以做这题)

（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第一章。

《我为歌狂》当中伍思凯神曲《舞月光》居然没赢给萨顶顶，爱与愁大神心痛啊~~~而且最近还有一些令人伤心的事情，都让人心痛（最近真的很烦哈)……

题目描述

最近有 n 个不爽的事，每句话都有一个正整数刺痛值（心理承受力极差）。爱与愁大神想知道连续 m 个刺痛值的和的最小值是多少，但是由于业务繁忙，爱与愁大神只好请你编个程序告诉他。

输入格式

第一行有两个用空格隔开的整数，分别代表 n 和 m。

第 2 到第 (n + 1)行，每行一个整数，第 (i + 1) 行的整数 ai​ 代表第 i 件事的刺痛值 ai​。

输出格式

输出一行一个整数，表示连续 mm 个刺痛值的和的最小值是多少。

输入输出样例

输入 #1复制

8 3
1
4
7
3
1
2
4
3

输出 #1复制

6

#include<iostream>
using namespace std;
const int N = 3e4 + 10;
int MIN = 100000;
int a[N];
int n,m;
int sum = 0;
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        cin>>a[i];
    }
    
    for(int i = 1;i <= n-m+1;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            sum += a[i+j-1];
        }
        if(sum < MIN) MIN = sum;
        sum = 0;
    }
    cout<<MIN<<endl;
    return 0;
}

836. 合并集合

#include<iostream>
using namespace std;
const int N = 100010;
int fa[N],n,m;
int find(int x)//路径压缩
{

    if(fa[x] != x)fa[x] = find(fa[x]);
    return fa[x];
}
int main()
{

    cin>>n>>m;
    for(int i = 1;i <= n;i++)fa[i] = i;
    while(m–)
    {

        int a,b;
        char op[2];//两个操作
        scanf(“%s%d%d”,op,&a,&b);
        if(op[0] == ‘M’)fa[find(a)] = find(b);
        else 
        {

            if(find(a) == find(b)) puts(“Yes”);
            else puts(“No”);
        }
    }
    return 0;
}

837. 连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

维护连通块size的并查集

PS:因为与合并题目中唯一不同的是，多了记录合并集合中连通块的个数
通过cnt数组记录以当前点x为祖先节点的集合中的连通块个数

#include<iostream>
using namespace std;
const int N = 100010;
int fa[N],cnt[N],n,m;
int find(int x)//路径压缩
{

    if(fa[x] != x)fa[x] = find(fa[x]);
    return fa[x];
}
int main()
{

    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {

        fa[i] = i;
        cnt[i] = 1;
    }
    while(m–)
    {

        string op;
        int a,b;
        cin>>op;
        if(op == “C”)
        {

            cin>>a>>b;
            a = find(a),b = find(b);
            if(a != b)
            {

                fa[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if(op == “Q1”)
        {

            cin>>a>>b;
            if(find(a) == find(b)) puts(“Yes”);
            else puts(“No”);
        }
        else
        {

            cin>>a;
            cout<<cnt[find(a)]<<endl;
            
        }
        
    }
    return 0;
}

831. KMP字符串

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 MM，表示字符串 S 的长度。

第四行输入字符串 SS。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤N≤10^5  
1≤M≤10^6

输入样例：

3
aba
5
ababa

输出样例：

0 2

Ps:

核心思想：在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。

next[ ]是“部分匹配值表”，即next数组，它存储的是每一个下标对应的“部分匹配值”，是KMP算法的核心。​ 然后来说明一下next数组的含义：对next[ j ] ，是p[ 1, j ]串中前缀和后缀相同的最大长度（部分匹配值），即 p[ 1, next[ j ] ] = p[ j – next[ j ] + 1, j ]。

手动模拟求next数组：

对 p = “abcab”

p            a    b    c    a    b
下标       1    2    3    4    5
next[ ]     0    0    0    1    2

对next[ 1 ] ：前缀 = 空集—————后缀 = 空集 所以：next[ 1 ] = 0;

对next[ 2 ] ：前缀 = { a }—————后缀 = { b } 所以：next[ 2 ] = 0;

对next[ 3 ] ：前缀 = { a , ab }—————后缀 = { c , bc} 所以：next[ 3 ] = 0;

对next[ 4 ] ：前缀 = { a , ab , abc }—————后缀 = { a ，ca , bca }所以：next[ 4 ] = 1;

对next[ 5 ] ：前缀 = { a , ab , abc , abca }————后缀 = { b , ab , cab , bcab} 所以：next[ 5 ] = 2;

 实现看代码：（ s串和p串都是从1开始的。i 从1开始，j 从0开始，每次s[ i ] 和p[ j + 1 ]比较）

#include<iostream>
using namespace std;
const int N = 100010,M = 1000010;
char s[M],p[N];
int ne[N];
int n,m;
int main()
{

    cin>>n>>p+1>>m>>s+1;
    //求next[]数组
    for(int i = 2,j = 0;i <= n;i++)//ne[1] = 0,所以我们这里i从2开始
    {

        while(j && p[i] != p[j+1]) j = ne[j];//while循环在这里的作用是一次一次寻找符合条件的（j = ne[j]是跳到前边去找）
        if(p[i] == p[j+1]) j++;//满足条件可以寻找下一个了
        ne[i] = j;
    }
    //求匹配过程
    for(int i = 1,j = 0;i <= m;i++)//此处我们这里的j总是会比i小1
    {

        while(j && s[i] != p[j+1]) j = ne[j];//与上述求next[]数组一样
        if(s[i] == p[j+1]) j++;
        if(j == n)
        {

            //匹配成功
            cout<<i-n<<” “;//本题俺下标从1开始，而题目让我们从0开始
            j = ne[j];
            
        }
    }
    return 0;
}

835. Trie字符串统计

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗10^4

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

#include<iostream>
using namespace std;
const int N = 100010;
char str[N];
int son[N][26],idx,cnt[N];

//son[ ] [ ]存储子节点的位置，分支最多26条；
//cnt[ ] 存储以某节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
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];//走到p的子结点
    }
    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;
    cin>>n;
    while(n–)
    {

        char op[5];//用char数组可以防止读入出现一些奇奇怪怪的问题。
        scanf(“%s%s”,op,str);
        if(op[0] == ‘I’)insert(str);
        else printf(“%d\n”,query(str));
    }
    return 0;
}

838. 堆排序

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n和 m。

第二行包含 n个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤10^5，
1≤数列中元素≤10^9

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

插入一个数 heap[ ++ size] = x; up(size);
求集合中的最小值   heap[1]
删除最小值   heap[1] = heap[size]; size — ;down(1);
删除任意一个元素   heap[k] = heap[size]; size — ;up(k); down(k);
修改任意一个元素   heap[k] = x; up(k); down(k);

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int h[N],cnt;
int n,m;
void down(int u)
{

    int t = u;//t是这里面最小的数
    if(u*2 <= cnt && h[u*2] < h[t])t = u*2;
    if(u*2+1 <= cnt && h[u*2+1] < h[t]) t = u*2+1;
    if(u != t)
    {

        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{

    cin>>n>>m;
    for(int i = 1;i <= n;i++)cin>>h[i];
    cnt = n;//统计元素的数量
    
    for(int i = n/2;i;i–)down(i);//插入操作，可以一个一个插入，但是一个一个插入时间复杂度有些高，这里的时间复杂度为O(n)

解决您的疑惑：

i为什么从n/2开始down？

首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。

开始创建堆的时候，元素是随机插入的，所以不能从根节点开始down，而是要找到满足下面三个性质的结点：

1.左右儿子满足堆的性质。

2.下标最大（因为要往上遍历）

3.不是叶结点（叶节点一定满足堆的性质）

        while(m–)
        {

            cout<<h[1]<<” “;
            h[1] = h[cnt–];//已经包含了cnt–操作，把那个元素删掉,最大的数赋值给堆顶
            down(1);
        }

//从头结点重新排列一遍，确保下标是1的值，是最小的，然后输出出来，然后删除，依次输出当前堆里面最小的值
    return 0;
}

840. 模拟散列表

维护一个集合，支持如下几种操作：

1. I x，插入一个数 xx；
2. Q x，询问数 xx 是否在集合中出现过；

现在要进行 NN 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤10^5
−10^9≤x≤10^9

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

此题咱们用拉链法来做，拉链拉链，顾名思义就是拉出一条链，避免映射到同一个点去

//拉链法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int ne[N],val[N],idx,h[N];//开一个槽 h
void insert(int x)
{
    int k = (x % N + N) % N;  // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    val[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(val[i] == x)
        return true;
        
        return false;
}

 //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h); //将槽先清空 空指针一般用 -1 来表示
    
    while(n--)
    {
        int x;
        char op[2];
        scanf("%s%d",op,&x);
        if(*op == 'I')insert(x);
        else 
        {
            if(find(x))puts("Yes");
            else puts("No");
        }
    }
    
    
    return 0;
    
}

今天的文章acwing刷题指南7分享到此就结束了，感谢您的阅读。