【蓝桥杯集训·每日一题】AcWing 3768. 字符串删减
文章目录
- 一、题目
- 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(){cin>>n;cin>>s;for(int i=0;i<s.size()-2;i++){ //从前到后依次枚举长度为3的子串的起点if(s.substr(i,3)=="xxx"){ //每出现连续3个x说明需要删一个,ans++ans++;}}cout<<ans;return 0;
}
y总思路代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n,ans;
string s;
int main(){cin>>n;cin>>s;for(int i=0;i<s.size();i++){ //从前往后枚举字符串s的每个位置if(s[i]=='x'){ //如果当前位置为xint j=i+1; //j指向当前位置的下一位 while(j<n&&s[j]=='x') j++; //如果j也是x,j++,最终j指向该段连续的x的下一个位置ans+=max(j-i-2,0); //j-i为该段连续x中x的数量,j-i-2是需要删除x的数量,有可能连续x的个数小于3,所以需要与0取maxi=j-1; //i指向当前连续一段x的最后一位的x的位置,下次循环前i++,就指向了该段连续x之后的第一个不是x的位置}}cout<<ans;return 0;
}
三、知识风暴
双指针
如果在暴力求解过程中出现需要用双层循环来遍历,而且两层循环的变量走向具有
单调性,则可以进行双指针优化,可以将时间复杂度降低至O(n)。
相关文章:
【蓝桥杯集训·每日一题】AcWing 3768. 字符串删减
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴双指针一、题目 1、原题链接 3768. 字符串删减 2、题目描述 给定一个由 n 个小写字母构成的字符串。 现在,需要删掉其中的一些字母,使得字符串中不…...
Python|每日一练|树|深度优先搜索|数组|二分查找|链表|双指针|单选记录:填充每个节点的下一个右侧节点指针|搜索插入位置|旋转链表
1、填充每个节点的下一个右侧节点指针(树,深度优先搜索) 给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *rig…...
降雨量实时监测系统压电式雨量计
压电式雨量传感器由上盖、外壳和下盖组成,壳体内部有压电片和电路板,可以固定在外径50mm立柱上和气象站横杆上。传感器采用冲击测量原理对单个雨滴重量进行测算,进而计算降雨量。雨滴在降落过程中受到雨滴重量和空气阻力的作用,到…...
滑动相关的原理以及用滤波器实现滑动相关(匹配滤波器捕获DMF)
目录滑动相关匹配滤波器捕获(DMF)滑动相关 滑动相关属于一种时域捕获方法,其具体原理是是通过本地序列与接收信号在固定窗长内滑动累加得到相关结果。 一般滑动相关算法可以用于对自相关性非常好的伪码进行同步判决。 我们首先生成一组自相关…...
计算机网络笔记(三)—— 数据链路层
数据链路层概述 数据链路层以帧为单位传输数据。 封装成帧:给网络层提供的协议数据单元添加帧头帧尾 差错检测:检错码封装在帧尾 可靠传输:尽管误码不能避免,但如果可以实现发送什么就接受什么,就叫可靠传输 封装成…...
【日常】矩阵正态分布参数检验问题
最近给凯爹做的一个苦力活,统计检验这个东西说实话也挺有趣,跟算法设计一样,好的检验真的是挺难设计的,就有近似算法的那种感觉,检验很难保证size和power都很理想,所以就要做tradeoff,感觉这个假…...
QML矩形(Rectangle)
Rectangle 用于绘制矩形 常见的属性: 填充颜色:纯色:color 渐变 :Gradient类 渐变的优先级大于纯色Gradient(渐变色): 渐变由多种颜色定义,这些颜色将无缝混合,…...
CSS自定义鼠标样式
CSS自定义鼠标样式 属性值 属性描述url需使用的自定义光标的 URLdefault默认光标(通常是一个箭头)auto默认。浏览器设置的光标crosshair光标呈现为十字线pointer光标呈现为指示链接的指针(一只手)move此光标指示某对象可被移动e…...
春招Leetcode刷题日记-D4-双指针算法-滑动窗口快慢指针
D4-双指针算法-滑动窗口&&快慢指针快慢指针算力扣141. 环形链表思路代码力扣142. 环形链表 II思路代码滑动窗口力扣76. 最小覆盖子串思路代码力扣424. 替换后的最长重复字符思路代码快慢指针算 快慢指针算法,多用于链表当中,常见的如࿱…...
【go】结合一个go开源项目分析谷歌浏览器cookie为什么不安全 附go项目导包失败怎么解决教程
本文创作背景 源于谷歌浏览器提示密码被泄露 并且某站很快收到了异地企图登录的提醒。 当即怀疑是不是谷歌浏览器保存的密码不安全,最后查阅诸多资料 并找到一个go语言编写的开源项目进行研究,虽然最终不能确定密码是如何泄露的 但研究结论还是让人不由感…...
Windows瘦身方法
一、快速删除系统盘临时文件方法, 1、winr打开运行对话框,输入%temp%命令,如图1 图1 2、打开temp文件夹,如图2,选择所有文件,鼠标右键删除或按Del键删除。 图2 二、磁盘清理 1、winr,输入cleanmgr&#x…...
19. 删除链表的倒数第 N 个结点
题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/进阶:你能尝试使用一趟扫描实现吗?解题思路:最简单的方法是先遍历一次链表,得到链表的长度len,然后再一次遍历链表,遍…...
【Linux】网络编程 - 基础概念
目录 一.OSI七层模型vsTCP/IP五层模型 1.一些周边概念 2.OSI七层模型 3.TCP/IP五层模型 4.网络传输流程图 二.什么是MAC地址 三.什么是IP/IP地址 1.什么是IP 2.什么是IP地址 四.什么是端口号 一.OSI七层模型vsTCP/IP五层模型 1.一些周边概念 局域网vs广域网 网络互…...
Unity 多语言 轻量高效的多语言工具集 LanguageManager
效果展示 支持excel导入自动化 组件化 更方便 也提供直接获取多语言的接口 没有挂 LanguageText的对象也可以获取多语言文本内容 支持 Format接口 可以传递N个参数进来组装多语言 支持首次系统语言自测 支持语言切换后本地自动保存配置 支持实时切换 同步刷新所有UI 容错处…...
在Linux和Windows上安装zookeeper-3.5.9
记录:378场景:在CentOS 7.9操作系统上,安装zookeeper-3.5.9。在Windows上操作系统上,安装zookeeper-3.5.9。版本:JDK 1.8 CentOS 7.9 zookeeper-3.5.9官网地址:https://zookeeper.apache.org/源码地址&…...
【ESP32+freeRTOS学习笔记-(八)资源管理】
目录1、 资源使用概况2、互斥方法之一:基本临界区2.1、taskENTER_CRITICAL_FROM_ISR() 和taskEXIT_CRITICAL_FROM_ISR()3、互斥方法之二:挂起或锁定调度程序3.1 vTaskSuspendAll()3.2 xTaskResumeAll()4 互斥方法三:互斥信号量(和…...
P1427 小鱼的数字游戏(赋值运算符和String)
小鱼的数字游戏 题目描述 小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字 aia_iai(长度不一定,以 000 结束),记住了然后反着念出来(表示结束的数字 000 就不要念出来了)。这对小鱼…...
Java学的好,工作不愁找
俗话说的好:“Java学的好,工作不愁找”,不管我们学习哪一门语言,我们都要掌握从抽象化中提取出来的方法,这样你才能提高我们的学习能力,并且在学习新事物的时候可以提取我们自己的想法。学习java࿰…...
表情包可视化编辑、生成配置信息数据工具
合成GIF图片 - 表情包 后续,用于快速、便捷生成 img_config.js 中 要生成的GIF每一帧数据(写入头像图片信息参数); 1、先上传 写入GIF中头像 标准图,同时获取图片信息,更新 写入GIF中头像 初始值࿰…...
java简单循环结构
while循环结构 Java提供的while条件循环。它的基本用法是: while (条件表达式) {循环语句 } // 继续执行后续代码while循环在每次循环开始前,首先判断条件是否成立。如果计算结果为true,就把循环体内的语句执行一遍,如果计算结果…...
java+uniapp集成unipush2实现消息推送
一、开通uniPush2.0 1.实名认证 登录DCloud开发者中心,通过实名认证 2.进入UniPush控制台 HBuilderX中打开项目的manifest.json文件 导航在“App模块配置” → 项的“Push(消息推送)” → “UniPush”下点击配置 或者申请开通。 3.配置应用信息 在UniPush开通界面…...
从服务器到手机:手把手教你修改游戏客户端IP,让私服在手机上跑起来
移动游戏私服客户端IP修改实战指南 当你在服务器上成功部署了游戏私服后,最令人沮丧的莫过于发现手机上的官方客户端无法连接到你的私人服务器。这个看似简单的"最后一公里"问题,往往成为许多私服搭建者的拦路虎。本文将彻底解决这个痛点&…...
逆向实战:从异或表到明文存储,我是如何让Eternium的游戏数据‘裸奔’的
逆向工程实战:解密游戏数据存储的核心逻辑 在数字娱乐时代,游戏安全机制与逆向分析技术之间的博弈从未停止。对于技术爱好者而言,理解游戏如何保护其核心数据不仅是一次智力挑战,更是深入了解计算机系统底层运作的绝佳机会。本文将…...
深度解析:HS2-HF Patch如何通过模块化架构彻底重塑游戏体验
深度解析:HS2-HF Patch如何通过模块化架构彻底重塑游戏体验 【免费下载链接】HS2-HF_Patch Automatically translate, uncensor and update HoneySelect2! 项目地址: https://gitcode.com/gh_mirrors/hs/HS2-HF_Patch HS2-HF Patch作为《Honey Select 2》最全…...
别再死记硬背了!用一张图+代码片段,彻底搞懂Element UI Menu组件的嵌套关系
可视化拆解Element UI菜单组件:从零构建多级导航系统 每次看到Element UI文档里那些层层嵌套的菜单代码,是不是感觉像在解一道复杂的数学题?作为Vue生态中最受欢迎的UI框架之一,Element UI的菜单组件确实功能强大,但初…...
一站式解决方案:3步实现Mac微信聊天记录的永久备份与专业管理
一站式解决方案:3步实现Mac微信聊天记录的永久备份与专业管理 【免费下载链接】WeChatExporter 一个可以快速导出、查看你的微信聊天记录的工具 项目地址: https://gitcode.com/gh_mirrors/wec/WeChatExporter 在数字时代,微信聊天记录承载着珍贵…...
重温DIRE:走向通用人工智能生成的图像检测
1.摘要生成模型的快速发展提高了图像质量,并使图像合成广泛可用,引起了对内容可信度的关注。为了解决这个问题,我们提出了一种称为通用重建残差分析(UR2EA)的方法来检测合成图像。我们的研究表明,当通过预训练的扩散模型重建GAN和…...
我开会用了之后从怀疑到真香!2026华为手机语音转文字真后悔没早用
我上周差点因为漏记项目评审会的核心需求背锅,前前后后踩了N多会议记录的坑,用过不下10款语音转文字工具,掏心窝子说一句:听脑AI是同类工具中最值得职场人用的,没有之一。之前我真的不信什么语音转文字能解决所有问题&…...
从波形到Mel谱图:机器学习音频特征提取的完整实践指南
1. 音频信号处理基础:从物理世界到数字信号 第一次接触音频信号处理时,我被那一串串看似随机的波形数据弄得一头雾水。直到后来才明白,这些数字背后其实对应着我们熟悉的物理现象——声音。声音的本质是空气压力的变化,就像水面泛…...
BlueArchive-Cursors:开源鼠标主题的技术实现与扩展应用指南
BlueArchive-Cursors:开源鼠标主题的技术实现与扩展应用指南 【免费下载链接】BlueArchive-Cursors Custom mouse cursor theme based on the school RPG Blue Archive. 项目地址: https://gitcode.com/gh_mirrors/bl/BlueArchive-Cursors BlueArchive-Curso…...
