崇义做网站,网站建设 合肥,网站流量合作,文学投稿网站平台建设文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴双指针一、题目
1、原题链接 3768. 字符串删减 2、题目描述 给定一个由 n 个小写字母构成的字符串。 现在#xff0c;需要删掉其中的一些字母#xff0c;使得字符串中不…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴双指针一、题目
1、原题链接 3768. 字符串删减 2、题目描述 给定一个由 n 个小写字母构成的字符串。 现在需要删掉其中的一些字母使得字符串中不存在连续三个或三个以上的 x。 请问最少需要删掉多少个字母 如果字符串本来就不存在连续的三个或三个以上 x则无需删掉任何字母。 输入格式 第一行包含整数 n。 第二行包含一个长度为 n 的由小写字母构成的字符串。 输出格式 输出最少需要删掉的字母个数。 数据范围 3≤n≤100 输入样例1 6
xxxiii输出样例1 1输入样例2 5
xxoxx输出样例2 0输入样例3 10
xxxxxxxxxx输出样例3 8二、解题报告
1、思路分析
我的思路 1遍历一遍字符串求出从每个位置开始长度为3的子串如果该子串中包含三个x则需要删去一个。 2统计所有位置的需要删除的个数输出即可。 思路来源y总蓝桥杯每日一题b站视频链接 y总yyds y总思路 1利用双指针算法找出每段连续x的个数如连续的x的个数小于3则不需要删除否则如果连续x的个数大于等于3个则需要删除x并使得该段x的个数等于2个。 2统计所有需要删除的x的个数输出即可。
2、时间复杂度
我的思路时间复杂度O(n) y总思路时间复杂度O(n)
3、代码详解
我的思路代码
#include iostream
#include string
using namespace std;
int n,ans;
string s;
int main(){cinn;cins;for(int i0;is.size()-2;i){ //从前到后依次枚举长度为3的子串的起点if(s.substr(i,3)xxx){ //每出现连续3个x说明需要删一个ansans;}}coutans;return 0;
}y总思路代码
#include iostream
#include string
#include algorithm
using namespace std;
int n,ans;
string s;
int main(){cinn;cins;for(int i0;is.size();i){ //从前往后枚举字符串s的每个位置if(s[i]x){ //如果当前位置为xint ji1; //j指向当前位置的下一位 while(jns[j]x) j; //如果j也是xj最终j指向该段连续的x的下一个位置ansmax(j-i-2,0); //j-i为该段连续x中x的数量j-i-2是需要删除x的数量有可能连续x的个数小于3所以需要与0取maxij-1; //i指向当前连续一段x的最后一位的x的位置下次循环前i就指向了该段连续x之后的第一个不是x的位置}}coutans;return 0;
}三、知识风暴 双指针 如果在暴力求解过程中出现需要用双层循环来遍历而且两层循环的变量走向具有单调性则可以进行双指针优化可以将时间复杂度降低至O(n)。
