头像

CodeWater




离线:4小时前



CodeWater
23小时前

题目描述

原题

维护一个字符串集合,支持两种操作:

“I x”向集合中插入一个字符串x;
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

输入格式
第一行包含整数N,表示操作数。

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

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

每个结果占一行。

数据范围
1≤N≤2∗104
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:
1
0
1


算法 Trie树

图解:
acwing835trie字符串统计.png

参考文献

y总讲解视频

C++ 代码

/*
Trie树  高效存储和查找字符串集合的数据结构
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
/*本题告诉我们只包含26个小写字母,所以每个子节点的个数是26
son 定义子节点的数组
cnt 存储的是以当前字母结尾的单词有多少个
idx 存的是当前用到的哪个下标。下标0的点既是根节点又是空节点(当一个点没有子节点
    的时候,我们让它也指向0)
*/
int son[N][26] , cnt[N] , idx ;
//要插入的字符串
char str[N];

//插入操作
void insert(char str[]){
    //从根节点开始
    int p = 0 ;
    /*这里是晚上找的资料:      a = "aad";
    string 并不是以‘\0'作为字符串结尾的标志,但是经试验,字符串可以越界
    访问a[3],并且字符串的结尾确实是'\0';*/
    //从前往后遍历,C++字符串结尾是\0 ,所以这里str[i]判断是不是走到结尾
    for(int i = 0 ; str[i] ; i++){
        //把a-z的字母映射成0-25的数字
        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';
        //这里是查询,如果不存在这个结点就直接返回0
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    //返回这个结点位置的单词数
    return cnt[p];
}

int main(){
    int n ; 
    scanf("%d" , &n);
    while(n--){
        //op一个单独的操作
        char op[2] ;
        //输入操作符  和字符串
        scanf("%s%s" , &op , &str);
        //如果操作符是插入就插入到str中
        if(op[0] == 'I') insert(str);
        //否则直接查询输出
        else printf("%d\n" , query(str));

    }
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

CodeWater
23小时前
/*
Trie树  高效存储和查找字符串集合的数据结构
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
/*本题告诉我们只包含26个小写字母,所以每个子节点的个数是26
son 定义子节点的数组
cnt 存储的是以当前字母结尾的单词有多少个
idx 存的是当前用到的哪个下标。下标0的点既是根节点又是空节点(当一个点没有子节点
    的时候,我们让它也指向0)
*/
int son[N][26] , cnt[N] , idx ;
//要插入的字符串
char str[N];

//插入操作
void insert(char str[]){
    //从根节点开始
    int p = 0 ;
    /*这里是晚上找的资料:      a = "aad";
    string 并不是以‘\0'作为字符串结尾的标志,但是经试验,字符串可以越界
    访问a[3],并且字符串的结尾确实是'\0';*/
    //从前往后遍历,C++字符串结尾是\0 ,所以这里str[i]判断是不是走到结尾                                                                                    
    for(int i = 0 ; str[i] ; i++){
        //把a-z的字母映射成0-25的数字
        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';
        //这里是查询,如果不存在这个结点就直接返回0
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    //返回这个结点位置的单词数
    return cnt[p];
}

int main(){
    int n ; 
    scanf("%d" , &n);
    while(n--){
        //op一个单独的操作
        char op[2] ;
        //输入操作符  和字符串
        scanf("%s%s" , &op , &str);
        //如果操作符是插入就插入到str中
        if(op[0] == 'I') insert(str);
        //否则直接查询输出
        else printf("%d\n" , query(str));

    }
    return 0;
}



题目描述

原题

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

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

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

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

第二行输入字符串P。

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

第四行输入字符串S。

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

数据范围
1≤N≤105
1≤M≤106
输入样例:
3
aba
5
ababa

输出样例:
0 2


算法 KMP

辅助图解,结合代码看。
acwing831kmp字符串.png
不懂的再多看几遍视频。

时间复杂度

O(n)

参考文献

y总视频讲解

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010 , M = 1000010;
//模板串p   模式串s
char p[N] , s[M];
//在有些编译器里面next会报错,这里直接定义为ne
int ne[N] ;
int n , m;

int main(){
    //输入p+1是因为让他从下标1开始
    cin>>n >> p + 1 >> m >> s + 1;

    //求ne过程
    //i从2开始,如果第一个字母失败了,那就只能从0开始了
    for(int i = 2 , j =0 ; i <= n ; i++){
        //跟下面的kmp过程一样
        while(j != 0 && p[i] != p[j + 1]) j = ne[j];
        //如果匹配成功, j继续往下走
        if(p[i] == p[j + 1]) j++;
        //记录
        ne[i] =  j;

    }



    /*kmp匹配过程
    和s[i]匹配的是p[j + 1]这个字符,所以j总是往前错一位
    */
    for(int i = 1 , j = 0 ; i <= m ; i++){
/*每一次匹配过程中, j没有退回起点。j如果退回起点,那就说明要重新进行匹配.
 并且当前s[i]不能和下一个j的位置去匹配:也就是说要把模板串p往后最少移动多少,才
 可以进行重新匹配。(看上面的图解)
*/
        while(j != 0 && s[i] != p[j + 1]) j = ne[j];
/*
while循环结束之后有两种条件:
                            1. j已经退无可退
                            2. s[i] 和 p[j + 1] 已经达成匹配
        这里就直接看达成匹配的情况。
*/
        //达成匹配,j移动到下一个位置
        if(s[i] == p[j + 1]) j++;
        if(j == n){//j= n说明匹配成功
            //输出起始位置
//printf("%d " , i - n + 1);题目总下标是从0开始的,我们是从1开始的,所以我们不用+1
            printf("%d " , i - n );
            //匹配成功,再往后退一步。继续下一轮的匹配
            j = ne[j];
        }

    }
    return 0;
}



活动打卡代码 AcWing 831. KMP字符串

算法 KMP

acwing831kmp字符串.png

#include <iostream>

using namespace std;

const int N = 100010 , M = 1000010;
//模板串p   模式串s
char p[N] , s[M];
//在有些编译器里面next会报错,这里直接定义为ne
int ne[N] ;
int n , m;

int main(){
    //输入p+1是因为让他从下标1开始
    cin>>n >> p + 1 >> m >> s + 1;

    //求ne过程
    //i从2开始,如果第一个字母失败了,那就只能从0开始了
    for(int i = 2 , j =0 ; i <= n ; i++){
        //跟下面的kmp过程一样
        while(j != 0 && p[i] != p[j + 1]) j = ne[j];
        //如果匹配成功, j继续往下走
        if(p[i] == p[j + 1]) j++;
        //记录
        ne[i] =  j;

    }



    /*kmp匹配过程
    和s[i]匹配的是p[j + 1]这个字符,所以j总是往前错一位
    */
    for(int i = 1 , j = 0 ; i <= m ; i++){
/*每一次匹配过程中, j没有退回起点。j如果退回起点,那就说明要重新进行匹配.
 并且当前s[i]不能和下一个j的位置去匹配:也就是说要把模板串p往后最少移动多少,才
 可以进行重新匹配。(看上面的图解)
*/
        while(j != 0 && s[i] != p[j + 1]) j = ne[j];
/*
while循环结束之后有两种条件:
                            1. j已经退无可退
                            2. s[i] 和 p[j + 1] 已经达成匹配
        这里就直接看达成匹配的情况。
*/
        //达成匹配,j移动到下一个位置
        if(s[i] == p[j + 1]) j++;
        if(j == n){//j= n说明匹配成功
            //输出起始位置
//printf("%d " , i - n + 1);题目总下标是从0开始的,我们是从1开始的,所以我们不用+1
            printf("%d " , i - n );
            //匹配成功,再往后退一步
            j = ne[j];
        }

    }
    return 0;
}




题目描述

原题

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7],k 为 3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式
输入包含两行。

第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式
输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:
8 3
1 3 -1 -3 5 3 6 7

输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7


算法

朴素算法
如果是用普通队列的话,那就是每次把元素从队尾加入到队列中,从队头弹出元素,然后
暴力循环一遍,检索出最小值输出。
一共扫描n次 , 每次检索k个元素,所以时间复杂度是nk。

单调队列
如果当前队尾数比当前要加入进来这个数大,那就把它从队列中删除,这样使得这个队列保持
一个单调增的性质,那每次要求最小的数只要输出队头即可。(最大值同理)

参考文献

y总讲解视频

C++ 代码

/*单调队列
这里有个小注意点,单调队列里面存储的a数组里面值得下标,队列得下标是数组里面对应的值

*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;
//a原数组  q模拟单调队列
int a[N] , q[N] ;
int n , k;

int main(){
    scanf("%d%d" , &n  , &k);
    for(int i = 0 ; i < n; i++)scanf("%d" , &a[i]);

    //hh队头 tt队尾
    int hh = 0 , tt = -1;
    //从前往后扫描一遍(这是单调递增的)
    for(int i = 0 ; i < n ; i++ ){
        /*首先判断当前队头元素还是不是在窗口的内部,如果不在的话就要删掉
        i此时是窗口右侧的端点,i - k + 1得到的是窗口左侧的端点,这样就可以判断
        此时队列的头部时候还在窗口内
        */
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        //当队列不空,并且队尾元素比当前要加入进来的元素大,那就把他删掉
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        //删除完队头的元素之后,要把当前数加入进队列中
        q[++tt] = i;

        //当窗口满足k个数时,才输出最小值
        if(i >= k - 1) printf("%d " , a[q[hh]]);

    }
    puts("");

    //求最大值也是同理,对称来写(这是单调递减的)
    hh = 0 , tt = -1;
    for(int i = 0 ; i < n ; i++){
        //首先判断当前队头元素还是不是在窗口的内部,如果不在的话就要删掉
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        //当队列不空,并且队尾元素比当前要加入进来的元素小,那就把他删掉
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;

        //删除完队头的元素之后,要把当前数加入进队列中
        q[++tt] = i;
        //当窗口满足k个数时,才输出最大值
        if(i >= k - 1) printf("%d " , a[q[hh]]);
    }
     puts("");
    return 0;
}





活动打卡代码 AcWing 154. 滑动窗口

算法分析

朴素算法
如果是用普通队列的话,那就是每次把元素从队尾加入到队列中,从队头弹出元素,然后
暴力循环一遍,检索出最小值输出。
一共扫描n次 , 每次检索k个元素,所以时间复杂度是nk。

单调队列
如果当前队尾数比当前要加入进来这个数大,那就把它从队列中删除,这样使得这个队列保持
一个单调增的性质,那每次要求最小的数只要输出队头即可。(最大值同理)

/*单调队列
这里有个小注意点,单调队列里面存储的a数组里面值得下标,队列得下标是数组里面对应的值

*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;
//a原数组  q模拟单调队列
int a[N] , q[N] ;
int n , k;

int main(){
    scanf("%d%d" , &n  , &k);
    for(int i = 0 ; i < n; i++)scanf("%d" , &a[i]);

    //hh队头 tt队尾
    int hh = 0 , tt = -1;
    //从前往后扫描一遍(这是单调递增的)
    for(int i = 0 ; i < n ; i++ ){
        //首先判断当前队头元素还是不是在窗口的内部,如果不在的话就要删掉
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        //当队列不空,并且队尾元素比当前要加入进来的元素大,那就把他删掉
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        //删除完队头的元素之后,要把当前数加入进队列中
        q[++tt] = i;

        //当窗口满足k个数时,才输出最小值
        if(i >= k - 1) printf("%d " , a[q[hh]]);

    }
    puts("");

    //求最大值也是同理,对称来写(这是单调递减的)
    hh = 0 , tt = -1;
    for(int i = 0 ; i < n ; i++){
        //首先判断当前队头元素还是不是在窗口的内部,如果不在的话就要删掉
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        //当队列不空,并且队尾元素比当前要加入进来的元素小,那就把他删掉
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;

        //删除完队头的元素之后,要把当前数加入进队列中
        q[++tt] = i;
        //当窗口满足k个数时,才输出最大值
        if(i >= k - 1) printf("%d " , a[q[hh]]);
    }
     puts("");
    return 0;
}




题目描述

原题

给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。

输入格式
第一行包含整数N,表示数列长度。

第二行包含N个整数,表示整数数列。

输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。

数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5

输出样例:
-1 3 -1 2 2


算法

单调栈
详情看代码注释,边看代码边看注释,方便理解。

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//stk模拟的单调栈  tt栈顶
int stk[N] , tt;
//n个数据
int n ;

int main(){
    cin>>n;
    //输入n个数据
    for(int i = 0 ; i < n ; i++){
        //x具体的数据
        int x;
        cin>>x;
        //当栈不为空并且栈顶元素大于等于当前值的时候,弹出
        /*
        因为我们要找的是当前值左边第一个比它小的数,而这个单调栈就是符合这
        样一种性质:从栈底到栈顶都是单调增加的。如果说当前栈顶元素比当前值
        都打,那说明此时的这个值必然是在后面输入进来的数中,比栈顶元素更加
        靠近那个后来值。并且这个x比后来值小的概率也会比栈顶元素大。因为它
        本来就比栈顶元素小,还在栈顶元素的右边。
        综上,当此时栈顶元素大于等于此时输入的x值,那么栈顶元素弹出,x进栈
        替换掉它。直到x找到适合它的位置,并再次构成单调栈。注意是while循环
        */
        while(tt != 0 && stk[tt] >= x )tt--;
        //如果栈不为空,那就说明此时的栈顶元素就是当前值左边离他最近的一个
            if(tt != 0) cout<<stk[tt]<<' ';
            //否则输出-1
            else cout<<-1<<' ';
            //把此时大于等于栈顶元素的x加入进栈中,形成单调栈
            stk[++tt] = x;

    }
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//stk模拟的单调栈  tt栈顶
int stk[N] , tt;
//n个数据
int n ;

int main(){
    cin>>n;
    //输入n个数据
    for(int i = 0 ; i < n ; i++){
        //x具体的数据
        int x;
        cin>>x;
        //当栈不为空并且栈顶元素大于等于当前值的时候,弹出
        /*
        因为我们要找的是当前值左边第一个比它小的数,而这个单调栈就是符合这
        样一种性质:从栈底到栈顶都是单调增加的。如果说当前栈顶元素比当前值
        都打,那说明此时的这个值必然是在后面输入进来的数中,比栈顶元素更加
        靠近那个后来值。并且这个x比后来值小的概率也会比栈顶元素大。因为它
        本来就比栈顶元素小,还在栈顶元素的右边。
        综上,当此时栈顶元素大于等于此时输入的x值,那么栈顶元素弹出,x进栈
        替换掉它。直到x找到适合它的位置,并再次构成单调栈。注意是while循环
        */
        while(tt != 0 && stk[tt] >= x )tt--;
        //如果栈不为空,那就说明此时的栈顶元素就是当前值左边离他最近的一个
            if(tt != 0) cout<<stk[tt]<<' ';
            //否则输出-1
            else cout<<-1<<' ';
            //把此时大于等于栈顶元素的x加入进栈中,形成单调栈
            stk[++tt] = x;

    }
    return 0;
}



题目描述

原题

实现一个队列,队列初始为空,支持四种操作:

(1) “push x” – 向队尾插入一个数x;

(2) “pop” – 从队头弹出一个数;

(3) “empty” – 判断队列是否为空;

(4) “query” – 查询队头元素。

现在要对队列进行M个操作,其中的每个操作3和操作4都要输出相应的结果。

输入格式
第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。

输出格式
对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。

其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示队头元素的值。

数据范围
1≤M≤100000,
1≤x≤109,
所有操作保证合法。

输入样例:
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例:
NO
6
YES
4


算法

数组模拟队列
示意图:
acwing829模拟队列.png
(PS:这个队列的队头是在左边,队尾是在右边。我一般理解的队列队头好像是在右边?不管,跟着y总学的话,思路就按着他的来。)

参考文献

y总讲解视频

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;
//q数组表示的模拟队列  hh表示队头  tt队尾
int q[N] , hh , tt = -1;
//在对头弹出元素, 在队尾插入元素

int m;

int main(){
//m个操作
    cin>>m;
    while(m --){
    //x要插入的元素
        int x ; 
        //op要执行的操作
        string op ;
        cin>>op;
        if(op == "push"){
            cin>>x;
            //插入
            q[++tt] = x;
        }else if(op == "pop"){
//弹出元素 , 对头指针往后移动一位就是弹出。
//这里的对头是在数组的左边,所以hh++,即指针前移,弹出一位
            hh++;
        }else if(op == "empty"){
           //不空判断
            if(hh <= tt) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }else{
            //取出队头元素
            cout<<q[hh]<<endl;
          /*  不难可看出,数组模拟队列,还可以取出队尾即:
            q[tt];
            */
        }
    }
    return 0;
}




活动打卡代码 AcWing 829. 模拟队列

#include <iostream>

using namespace std;

const int N = 100010;
//q数组表示的模拟队列  hh表示队头  tt队尾
int q[N] , hh , tt = -1;
//在对头弹出元素, 在队尾插入元素

int m;

int main(){
    cin>>m;
    while(m --){
        int x ; 
        string op ;
        cin>>op;
        if(op == "push"){
            cin>>x;
            //插入
            q[++tt] = x;
        }else if(op == "pop"){
//弹出元素 , 对头指针往后移动一位就是弹出。
//这里的对头是在数组的左边,所以hh++,即指针前移,弹出一位
            hh++;
        }else if(op == "empty"){
           //不空判断
            if(hh <= tt) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }else{
            //取出队头元素
            cout<<q[hh]<<endl;
          /*  不难可看出,数组模拟队列,还可以取出队尾即:
            q[tt];
            */
        }
    }
    return 0;
}