【基础算法】双指针----字符串删减
🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在!学会自己和解,与过去和解,努力爱自己。==希望春天来之前,我们一起面朝大海,春暖花开!==🤟
👏专栏:C++👏 👏专栏:Java语言👏👏专栏:Linux学习👏
👏专栏:C语言初阶👏👏专栏:数据结构👏👏专栏:备战蓝桥杯👏
文章目录
- 前言
-
- 字符串删减:
- 题目:
- 输入格式
- 输出格式
- 数据范围
- 输入样例1:
- 输出样例1:
- 输入样例2:
- 输出样例2:
- 输入样例3:
- 输出样例3:
- 做题思路:
- 代码:
- 代码解析:
-
- 最后
-
-
前言
今天这篇文章我们学习双指针,这次要讲解双指针的经典问题:字符串删减。码字不易,请多多支持!
——————————————————————————————
首先先写上几句话:献给坚持创作的我和点开这篇文章希望进步的你
1.也许你要早上七点起床,晚上十二点睡觉,日复一日,踽踽独行。但只要笃定而努力地活着,即使生不逢时,你人生最坏的结果,也只是大器晚成。
2.你可以讨厌某种东西,但你必须允许它的存在和别人喜欢它。
3.爱你的人会让你变成更好的人。
4.这一生的温柔记得给父母留一份。
5.我们都各自发光,不必去吹灭别人的灯。
字符串删减:
题目:
给定一个由 n 个小写字母构成的字符串。
现在,需要删掉其中的一些字母,使得字符串中不存在连续三个或三个以上的 x。
请问,最少需要删掉多少个字母?
如果字符串本来就不存在连续的三个或三个以上 x,则无需删掉任何字母。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤100
输入样例1:
6
xxxiii
输出样例1:
1
输入样例2:
5
xxoxx
输出样例2:
0
输入样例3:
10
xxxxxxxxxx
输出样例3:
8
做题思路:
从题意中我们可以知道我们一定不会删除之外的字符

从下图可以知道如果存在多段子串,那它们必是独立的

这样我们就可以分别考虑它们了,分别计算出它们要删减的字符个数,最终计算即可:

对于某一段进行讨论:

K<3,不需要删减;
K>=3,删减K-2个字符。
计算每一段的长度,那就需要用到双指针了
首先从第一个数字开始,不是X则下一个,是X则从它开始计数,直到第一个不是X的数即可。
代码:
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n;int main()
{int n;string str;cin >> n >> str;int res = 0;for (int i = 0; i < n; i ++ )//从开始枚举,if (str[i] == 'x')//当遇到第一个为x的时候,计数{int j = i + 1;while (j < n && str[j] == 'x') j ++ ;res += max(j - i - 2, 0);//j-i-2是要删减字符的个数i = j - 1;}cout << res << endl;return 0;
}
代码解析:
for (int i = 0; i < n; i ++ )//从开始枚举,if (str[i] == 'x')//当遇到第一个为x的时候,计数{int j = i + 1;while (j < n && str[j] == 'x') j ++ ;res += max(j - i - 2, 0);//j-i-2是要删减字符的个数i = j - 1;}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里,送几句话,对你,也对我:
1.应该是从喜欢里得到力量和快乐,而不是花光了力量和快乐去喜欢。
2.一定要狠下心来努力变成一个很厉害的人,厉害到有一天,你可以随时离开那些令你不舒服的圈子和人,让他们通通羡慕不已。你在四五月做的事情,在八九月自然会有答案。
3.你一定要努力,当你接触优秀的人时,你会发现别人不仅有钱,还穿的好看,打扮时尚,阳光且温柔,自律且上进,各方面都很优秀。
难熬的日子总会过去的,不信你回头看看,你都已经在不知不觉中熬过了很多苦难,所以真的不必慌张。
4.该翻脸的时候就翻脸,你好说话他还以为你好说话,过分的善良只会让人觉得你没有价值,他会得寸进尺的欺负你,你还要对他低声下气,难道他就天生富贵高人一等吗?
你不敢翻脸,是你自卑懦弱无能,对于不尊重你,不理解你的人,别客气。
5.你讨厌父亲的平庸,却不知道,他也曾是个怀揣梦想的少年。
你嫌弃母亲的唠叨,却不记得,她也曾是个对镜贴花黄的姑娘。
你是第一次当孩子,他们也是第一次当父母。世界上没有那么多极端可恶或者完美无缺的父母,他们也只是有着各种缺点的普通人而已。
不必总是想原生家庭欠了我什么,恰恰是原生家庭帮助我们看清自己修补自己,而非用来怨恨。毕竟,我们终其一生都要为自己负责。
最后如果觉得我写的还不错,请不要忘记点赞✌,收藏✌,加关注✌哦(。・ω・。)
愿我们一起加油,奔向更美好的未来,愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油,为自己点赞!
相关文章:
【基础算法】双指针----字符串删减
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
Billu靶场黑盒盲打——思路和详解
一、信息收集 1、探测内网主机IP可以使用各种扫描工具比如nmap,我这里用的是自己编写的。 nmap -n 192.168.12.0/24 #扫描IP,发现目标主机 2、先不着急,先收集一波它的端口(无果) nmap -n 192.168.12.136 -p 1-10000…...
【2363. 合并相似的物品】
来源:力扣(LeetCode) 描述: 给你两个二维整数数组 items1 和 items2 ,表示两个物品集合。每个数组 items 有以下特质: items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ,we…...
【C++提高编程】C++全栈体系(二十四)
C提高编程 第三章 STL - 常用容器 九、map/ multimap容器 1. map基本概念 简介: map中所有元素都是pairpair中第一个元素为key(键值),起到索引作用,第二个元素为value(实值)所有元素都会根…...
c++11 标准模板(STL)(std::unordered_set)(十一)
定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...
AI/CV大厂笔试LeetCode高频考题之基础核心知识点
AI/CV互联网大厂笔试LeetCode高频考题之基础核心知识点算法复习1、二叉树的遍历2、回溯算法3、二分搜索4、滑动窗口算法题5、经典动态规划6、动态规划答疑篇6.1、总结一下如何找到动态规划的状态转移关系7、编辑距离8、戳气球问题9、最长公共子序列 Longest Common Subsequence…...
华为OD机试题,用 Java 解【静态扫描最优成本】问题
最近更新的博客 华为OD机试题,用 Java 解【停车场车辆统计】问题华为OD机试题,用 Java 解【字符串变换最小字符串】问题华为OD机试题,用 Java 解【计算最大乘积】问题华为OD机试题,用 Java 解【DNA 序列】问题华为OD机试 - 组成最大数(Java) | 机试题算法思路 【2023】使…...
常见无线技术方案介绍
无线技术 无线网络大体有两种:WAN(广域网)、PAN(个人区域网)。 对于LoRa,NB-IoT,2G / 3G / 4G等无线技术,通常传输距离超过1 km,因此它们主要用于广域网(WA…...
收获满满的2022年
收到csdn官方的证书,感谢官方的认可!...
react的生命周期
目录 一、初始化阶段 constructor() static getDerivedStateFromProps() componentWillMount() / UNSAFE_componentWillMount() render(): componentDidMount() 二、运行阶段 componentWillUpdate() / UNSAFE_componentWillUpdate() render() getSnapsh…...
scanpy 单细胞分析API接口使用案例
参考:https://zhuanlan.zhihu.com/p/537206999 https://scanpy.readthedocs.io/en/stable/api.html scanpy python包主要分四个模块: 1)read 读写模块、 https://scanpy.readthedocs.io/en/stable/api.html#reading 2)pp Prepr…...
【Vue3 第二十一章】Teleport组件传送
一、基本使用场景 有时我们可能会遇到这样的场景:一个组件模板的一部分在逻辑上从属于该组件,但从整个应用视图的角度来看,它在 DOM 中应该被渲染在整个 Vue 应用外部的其他地方。 这类场景最常见的例子就是全屏的模态框。理想情况下&#…...
在 Windows Subsystem for Linux (WSL2) 的 Ubuntu 系统上配置 Vulkan 开发环境
在 Windows Subsystem for Linux (WSL2) 的 Ubuntu 系统上配置 Vulkan 开发环境Vulkan Tutorial https://vulkan-tutorial.com/ Development environment - Linux https://vulkan-tutorial.com/Development_environment 1. Vulkan - Cross platform 3D Graphics https://www…...
放苹果HJ61
入门题目 把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?注意:如果有7个苹果和3个盘子,(5,1,1)和(1,5&#…...
Windows下,OPC UA移植,open62541移植
OPC通信标准的核心是互通性 (Interoperability) 和标准化 (Standardization) 问题。传统的OPC技术在控制级别很好地解决了硬件设备间的互通性问题,在企业层面的通信标准化是同样需要的。OPC UA之前的访问规范都是基于微软的COM/DCOM技术, 这会给新增层面的通信带来不可根除的…...
【Tomcat与Servlet篇1】认识Tomcat与Maven
目录 一、什么是Tomcat 二、Tomcat的几个重要目录 conf文件编辑 Server.xml logs文件 Webapps目录 三、如何使用Tomcat 但是,如果出现了点击之后进行闪退的情况,那又是怎么回事呢? 原因1:环境变量没有配置 原因2&#…...
C++类和对象:拷贝构造函数和运算符重载
目录 一. 拷贝构造函数 1.1 什么是拷贝构造函数 1.2 编译器默认生成的拷贝构造函数 1.3 拷贝构造函数特性总结 二. 运算符重载 2.1 运算符重载概述 2.2 比较运算符重载(> > < <) 2.2.1 >运算符的重载 2.2.2 运算符的重载 2.…...
【IntelliJ IDEA】idea plugins搜索不出来,如何找到插件的解决方案
一、背景描述安装好IDEA后,想下载一些插件来使用,因为IDEA非常方便的一点就是插件使用非常的方便,但是经常会发现进入到插件市场无法搜索到插件的情况,这个时候就有点烦人了。那么怎么解决这个问题呢?以下会把我能想到…...
移动端自动化测试(一)appium环境搭建
自动化测试有主要有两个分类,接口自动化和ui自动化,ui自动化呢又分移动端的和web端的,当然还有c/s架构的,这种桌面程序应用的自动化,使用QTP,只不过现在没人做了。 web自动化呢,现在基本上都是…...
5 逻辑回归及Python实现
1 主要思想 分类就是分割数据: 两个条件属性:直线;三个条件属性:平面;更多条件属性:超平面。 使用数据: 5.1,3.5,0 4.9,3,0 4.7,3.2,0 4.6,3.1,0 5,3.6,0 5.4,3.9,0 . . . 6.2,2.9,1 5.1,2.5…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
大数据治理的常见方式
大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法,以下是几种常见的治理方式: 1. 数据质量管理 核心方法: 数据校验:建立数据校验规则(格式、范围、一致性等)数据清洗&…...
