建设网站需要设备,全媒体门户网站建设方案,泰安搭建公司,一建延期最新消息2022AcWing《蓝桥杯集训每日一题》—— 3768. 字符串删减 文章目录AcWing《蓝桥杯集训每日一题》—— 3768. 字符串删减一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的#xff0c;转md文件可能不太美观#xff0c;大家可以去我的博客中查看#xff1a;北天的 …AcWing《蓝桥杯集训·每日一题》—— 3768. 字符串删减 文章目录AcWing《蓝桥杯集训·每日一题》—— 3768. 字符串删减一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、题目 给定一个由 $n$ 个小写字母构成的字符串。 现在需要删掉其中的一些字母使得字符串中不存在连续三个或三个以上的 x。
请问最少需要删掉多少个字母
如果字符串本来就不存在连续的三个或三个以上 x则无需删掉任何字母。
输入格式
第一行包含整数 nnn。
第二行包含一个长度为 nnn 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤1003≤n≤1003≤n≤100
输入样例1
6
xxxiii
输出样例1
1
输入样例2
5
xxoxx
输出样例2
0
输入样例3
10
xxxxxxxxxx
输出样例3
8二、解题思路 这道题要解决的问题是找到最少需要删除的字符数量使得字符串中不存在连续三个或三个以上的 x。我们可以想到暴力枚举法和双指针法其中这里更推荐使用暴力枚举法因为很快也不会超时。下面我大致说一下两种方法的解题思路。 暴力枚举法 我们可以通过枚举所有长度为3的子串判断是否为 ‘xxx’从而找到需要删除的字符数量。具体实现方法是从下标2开始每次取出以该下标为结尾的长度为3的子串判断是否为 ‘xxx’如果是就需要删除中间那个字符即下标为i-1的字符。最后统计需要删除的字符数量即可。暴力枚举法的时间复杂度为 O(n)O(n)O(n)空间复杂度为 O(1)O(1)O(1)。 双指针法 我们可以通过维护两个指针 i 和 j其中 i 指向当前处理的字符j 指向最近一个不需要删除的字符。具体实现方法是遍历整个字符串如果当前字符为 ‘x’就将 cnt 加 1如果 cnt 等于 3说明需要删除当前字符即将 res 加 1如果 cnt 大于 3说明当前字符需要删除但是删除后会导致字符串中存在连续三个 ‘x’因此需要将 j 后移一位即将 j 赋值为 i-1同时将 cnt 减 1这样可以保证删除当前字符后字符串中不存在连续三个 ‘x’。如果当前字符不为 ‘x’则将 cnt 置为 0j 赋值为 i。最后统计需要删除的字符数量即可。时间复杂度为 O(n)O(n)O(n)空间复杂度为 O(1)O(1)O(1)。
总体而言双指针法的效率更高因为其只需要遍历一遍字符串而暴力枚举法需要枚举所有长度为 3 的子串效率相对较低。
三、代码实现
暴力枚举法代码实现 n int(input())
st input()
c 0
# 枚举所有长度为 3 的子串
for i in range(2, n):# 判断是否为 xxxif st[i - 2:i 1] xxx:# 如果是则需要删除中间那个字符即下标为 i-1 的字符c 1
# 输出需要删除的字符数量
print(c)双指针法代码实现
n int(input())
s input()res, cnt 0, 0
j -1
# 遍历整个字符串
for i in range(n):# 如果当前字符为 xif s[i] x:# 将 cnt 加 1cnt 1# 如果 cnt 等于 3说明需要删除当前字符if cnt 3:# 将 res 加 1res 1# 如果 cnt 大于 3说明当前字符需要删除# 但是删除后会导致字符串中存在连续三个 x# 因此需要将 j 后移一位即将 j 赋值为 i-1# 同时将 cnt 减 1这样可以保证删除当前字符后# 字符串中不存在连续三个 xelif cnt 3:res 1cnt - 1j 1else:# 如果当前字符不为 x将 cnt 置为 0j 赋值为 icnt 0j i# 输出需要删除的字符数量
print(res)
