支付网站建设费账务处理,广州网站开发 英诺科技,如何快速网络推广产品的方法,网站新闻列表页面代码作者#xff1a;指针不指南吗 专栏#xff1a;Acwing 蓝桥集训每日一题 #x1f43e;或许会很慢#xff0c;但是不可以停下#x1f43e; 文章目录1.字符串删减2.最长连续不重复子序列3.数组元素的目标和1.字符串删减 给定一个由 n 个小写字母构成的字符串。 现在#xff… 作者指针不指南吗 专栏Acwing 蓝桥集训每日一题 或许会很慢但是不可以停下 文章目录1.字符串删减2.最长连续不重复子序列3.数组元素的目标和1.字符串删减 给定一个由 n 个小写字母构成的字符串。 现在需要删掉其中的一些字母使得字符串中不存在连续三个或三个以上的 x。 请问最少需要删掉多少个字母 如果字符串本来就不存在连续的三个或三个以上 x则无需删掉任何字母。 输入格式 第一行包含整数 n。 第二行包含一个长度为 n 的由小写字母构成的字符串。 输出格式 输出最少需要删掉的字母个数。 数据范围 3≤n≤100 输入样例1: 6
xxxiii输出样例1 1输入样例2 5
xxoxx输出样例2 0输入样例3 10
xxxxxxxxxx输出样例3 8方法一 思路 枚举 i 遇到 x,进入循环计x的个数超过 2 个答案ans 代码实现 #includebits/stdc.h
using namespace std;int main()
{int n;string s;cinns; //读入数据int cnt0,ans0;for(int i0;in;i){while(s[i]x){ //如果是 x 进入循环cnt; // x 在该循环中出现的个数if(cnt2) ans; //ans累加i; //循环控制变量}cnt0; //进入下次循环之前进行置零操作}coutans;return 0;} 方法二——双指针算法 思路 输出单词那道题很像 枚举 i 表示全是x区间的开头j 表示x区间的最后即 j 的下一个不是x, 满足条件的答案 ans 累加 代码实践 #includebits/stdc.h
using namespace std;int main()
{int n;string s;cinns;int i0,j0,ans0;for(int i0;in;i){if(s[i]x) { // i 表示 x 区间的最左端开头ji;while(jns[j]x) j; // j 表示 x 区间的最右端结尾ansmax(0,j-i-2); //j-i-2拆分j-i1(区间长度)-1(跳出循环之前多加了1)-2(题中条件从第三个开始数)ij; // 令i 跳过这段已经计算过的区间寻找下一个}}coutans;return 0;
}2.最长连续不重复子序列 给定一个长度为 n 的整数序列请找出最长的不包含重复的数的连续区间输出它的长度。 输入格式 第一行包含整数 n。 第二行包含 n 个整数均在 0∼105 范围内表示整数序列。 输出格式 共一行包含一个整数表示最长的不包含重复的数的连续区间的长度。 数据范围 1≤n≤105 输入样例 5
1 2 2 3 5输出样例 3思路 枚举 i 表示区间右端点的指针 , j 表示区间左端点的指针 利用区间内数字出现的个数来判断是否满足条件 i 向前走一步a [ i ] 所表示的数出现的次数多一次用 s 数组把数字出现的次数存起来 j 从 0 开始走如果在 i 走的过程中 s [ a [ i ] ] 1则说明 i 现在表示的数与之前的重复了 让 j 往前走区间挤出去一个数先 s [ a [ j ] ] --再 j , 直到把重复的数挤出去即 s [ a [ i ] ] 1; i 每走一步判断一下区间大小是否做出最大值 res 更新 代码实现 #includebits/stdc.h
using namespace std;const int N100010;
int n;
int a[N],s[N]; //a表示原整数序列s 表示区间内数字出现的次数int main()
{cinn;for(int i0;in;i) cina[i]; //读入数据int res0,i0,j0; //res 表示最大的区间大小for(i0;in;i){s[a[i]]; //i前进区间内a[i]的出现次数增加while(s[a[i]]1){ //若出现重复元素则进入循环s[a[j]]--; //j前进a[j]出现次数减少一次j;}resmax(res,i-j1); //更新最大值}coutres;return 0;
}3.数组元素的目标和 给定两个升序排序的有序数组 A 和 B以及一个目标值 x。 数组下标从 0 开始。 请你求出满足 A[i]B[j]x 的数对 (i,j)。 数据保证有唯一解。 输入格式 第一行包含三个整数 n,m,x分别表示 A 的长度B 的长度以及目标值 x。 第二行包含 n 个整数表示数组 A。 第三行包含 m 个整数表示数组 B。 输出格式 共一行包含两个整数 i 和 j。 数据范围 数组长度不超过 105。 同一数组内元素各不相同。 1≤数组元素≤109 输入样例 4 5 6
1 2 4 7
3 4 6 8 9输出样例 1 1思路 先想暴力做法 for(int i0;in;i)for(int jm-1;j0;j--)if(a[i]b[j]k) couti jendl; 利用单调性优化后 枚举 i 从小到大j 从大到小找到 j 满足条件 a[i]b[j]k,说明符合题意的一定在 此时i的右边j的左边 代码实现 #includebits/stdc.h
using namespace std;const int N100010;
int a[N],b[N];
int n,m,k;int main()
{cinnmk;for(int i0;in;i) cina[i];for(int j0;jm;j) cinb[j];for(int i0,jm-1;in;i){ //i从小到大枚举while(j0a[i]b[j]k) j--; //j 从大到小 答案在i的右边在j的左边if(a[i]b[j]k){couti jendl;}} return 0;
}
