【蓝桥集训】第四天——双指针
作者:指针不指南吗
专栏: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++ -
代码实现
#include<bits/stdc++.h> using namespace std;int main() {int n;string s;cin>>n>>s; //读入数据int cnt=0,ans=0;for(int i=0;i<n;i++){while(s[i]=='x'){ //如果是 x 进入循环cnt++; // x 在该循环中出现的个数if(cnt>2) ans++; //ans累加i++; //循环控制变量}cnt=0; //进入下次循环之前,进行置零操作}cout<<ans;return 0;}
方法二——双指针算法
-
思路
输出单词那道题很像
枚举 i 表示全是
x区间的开头,j 表示x区间的最后,即 j 的下一个不是x,满足条件的答案 ans 累加
-
代码实践
#include<bits/stdc++.h> using namespace std;int main() {int n;string s;cin>>n>>s;int i=0,j=0,ans=0;for(int i=0;i<n;i++){if(s[i]=='x') { // i 表示 x 区间的最左端开头j=i;while(j<n&&s[j]=='x') j++; // j 表示 x 区间的最右端结尾ans+=max(0,j-i-2); //j-i-2拆分:j-i+1(区间长度)-1(跳出循环之前多加了1)-2(题中条件从第三个开始数)i=j; // 令i 跳过这段已经计算过的区间,寻找下一个}}cout<<ans;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 更新;
-
代码实现
#include<bits/stdc++.h> using namespace std;const int N=100010; int n; int a[N],s[N]; //a表示原整数序列,s 表示区间内数字出现的次数int main() {cin>>n;for(int i=0;i<n;i++) cin>>a[i]; //读入数据int res=0,i=0,j=0; //res 表示最大的区间大小for(i=0;i<n;i++){s[a[i]]++; //i前进,区间内a[i]的出现次数增加while(s[a[i]]>1){ //若出现重复元素则进入循环s[a[j]]--; //j前进,a[j]出现次数减少一次j++;}res=max(res,i-j+1); //更新最大值}cout<<res;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 i=0;i<n;i++)for(int j=m-1;j>=0;j--)if(a[i]+b[j]==k) cout<<i<<' '<<j<<endl;利用单调性优化后
枚举 i 从小到大,j 从大到小,找到 j 满足条件 a[i]+b[j]>k,说明符合题意的一定在 此时i的右边,j的左边
-
代码实现
#include<bits/stdc++.h> using namespace std;const int N=100010; int a[N],b[N]; int n,m,k;int main() {cin>>n>>m>>k;for(int i=0;i<n;i++) cin>>a[i];for(int j=0;j<m;j++) cin>>b[j];for(int i=0,j=m-1;i<n;i++){ //i从小到大枚举while(j>=0&&a[i]+b[j]>k) j--; //j 从大到小 ,答案在i的右边,在j的左边if(a[i]+b[j]==k){cout<<i<<' '<<j<<endl;}} return 0; }
相关文章:
【蓝桥集训】第四天——双指针
作者:指针不指南吗 专栏:Acwing 蓝桥集训每日一题 🐾或许会很慢,但是不可以停下🐾 文章目录1.字符串删减2.最长连续不重复子序列3.数组元素的目标和1.字符串删减 给定一个由 n 个小写字母构成的字符串。 现在ÿ…...
List<Map<String, Object>>的数据结构的添加和删除实例
对List<Map<String, Object>>的数据结构的添加和删除实例添加//初始化List<Map<String, Object>> products new ArrayList<Map<String,Object>>();//也可以这样初始化List<Map<String, Object>> products null//初始Map<…...
5.2 线程实际案例练习
文章目录1.概述2.实现方案一:继承Thread2.1 代码实现2.2 代码分析3.实现方案二:实现Runnable接口3.1 代码实现3.2 代码分析4.实现方案三:构建线程池4.1 代码实现4.2 代码分析1.概述 接下来我们通过一个售票案例的实际操作来深入理解线程的相…...
stm32f407探索者开发板(十七)——串口寄存器库函数配置方法
文章目录一、STM32串口常用寄存器和库函数1.1 常用的串口寄存器1.2 串口相关的库函数1.3 状态寄存器(USART_ SR)1.4 数据寄存器(USART_ DR)1.5 波特率寄存器(USART_BRR)二、串口配置一般步骤一、STM32串口常…...
山西省2023年软考报名3月14日开始
根据2023年上半年计算机技术与软件专业技术资格(水平)考试工作计划,可以得知,全国考务管理服务平台将于2023年3月13日开放,各地开始组织报名,如山西已发布2023上半年报名简章,从3月14号开始报名。 软考报名官网 大部…...
进程章节总结性实验
进程实验课笔记 本节需要有linux基础,懂基本的linux命令操作即可。 Ubuntu镜像下载 https://note.youdao.com/s/VxvU3eVC ubuntu安装 https://www.bilibili.com/video/BV1j44y1S7c2/?spm_id_from333.999.0.0 实验环境ubuntu22版本,那个linux环境都可以…...
【MyBatis】MyBatis的缓存
10、MyBatis的缓存 10.1、MyBatis的一级缓存 一级缓存是SqlSession级别的,通过同一个SqlSession查询的数据会被缓存,下次查询相同的数据,就会从缓存中直接获取,不会从数据库重新访问 使一级缓存失效的四种情况: 不…...
MyBatis基本使用
一、简介 MyBatis 中文文档 https://mybatis.org/mybatis-3/zh/index.html 1.什么是 MyBatis 概述:MyBatis 是一款优秀的持久层框架,它支持自定义 SQL、存储过程以及高级映射。MyBatis 免除了几乎所有的 JDBC 代码以及设置参数和获取结果集的工作。MyBa…...
如何运行YOLOv6的代码实现目标识别?
YOLOv6是由美团视觉团队开发的1.环境配置我们先把YOLOv6的代码clone下来git clone https://github.com/meituan/YOLOv6.git安装一些必要的包pip install pycocotools2.0作者要求pytorch的版本是1.8.0,我的环境是1.7.0,也是可以正常运行的pip install -r requirement…...
新品BCM6755A1KFEBG/MT7921LE/MT7921AU WiFi芯片
博通在WiFi市场具有相当的实力。在WiFi6上有下面这几个解决方案:型号:BCM6755 BCM6755A1KFEBG类型:四核1.5GHz CPU封装:BGA批次:新BCM6755和BCM6750还是A7架构,更多的用在中低端型号上。BCM6755和BCM6750 C…...
析构函数、拷贝构造
1、析构函数析构函数的定义方式函数名和类名相同,在类名前加~,没有返回值类型,没有函数形参(不能重载)当对象生命周期结束的时候,系统会自动调用析构函数先调用析构函数,再释放对象的空间析构函…...
光学镜头是制作过程阶段理解
光学镜头是由多组镜片组合而成,它是摄影机投影一及显微镜上必不可少的部件。那么光学镜头是如何制造的呢?光学镜头的制作分为以下四个阶段:第一、首先将一大块光学玻璃用钻石锯片进行切片,然后用钻头在每一块玻璃切片上钻出多块冰…...
实验室设计|实验室设计要点SICOLAB
一、实验室设计规划要素1、实验室布局:实验室的布局要符合实验室工作流程,可以将实验室划分为干净区和污染区,以确保实验室的卫生和实验的准确性。2、设备选购:根据实验需要选择适当的设备,并确保设备的质量和性能符合…...
I.MX6ULL_Linux_系统篇(16) uboot分析-启动流程
原文链接:I.MX6ULL_系统篇(16) uboot分析-启动流程 – WSY Personal Blog (cpolar.cn) 前面我们详细的分析了 uboot 的顶层 Makefile,了解了 uboot 的编译流程。本章我们来详细的分析一下 uboot 的启动流程,理清 uboot 是如何启动的。通过对 …...
【C#】async关键字修饰后有无await的影响
文章目录测试总结拓展:js的async await问题参考测试 来自微软官网的说法: 异步方法通常包含 await 运算符的一个或多个匹配项,但缺少 await 表达式不会导致编译器错误。 如果异步方法未使用 await 运算符标记悬挂点,则该方法将作…...
Interspeech2022 | 一种基于元辅助学习的低资源口语语义理解方法
中国移动研究院首席科学家冯俊兰博士带领人工智能与智慧运营中心语音团队共同撰写的文章《Meta Auxiliary Learning for Low-resource Spoken Language Understanding》被语音国际顶会Interspeech2022接收。 关于Interspeech Interspeech 是国际最大且最全面关于言语科学与技…...
File类的用法和InputStream,OutputStream的用法
这里写自定义目录标题一、File类1.构造方法2.普通方法二、InputStream1.方法2.FileInputStream3.Scanner类的应用三、OutputStream1.方法2.FileOutputStream3.PrintWriter类的应用一、File类 1.构造方法 签名说明File(File parent, Stringchild)根据父目录 孩子文件路径&…...
Java多线程——Thread类的基本用法
一.线程的创建继承Thread类//继承Thread类class MyThread extends Thread{Overridepublic void run() {System.out.println("线程运行的代码");} } public class Demo1 {public static void main(String[] args) {MyThread t new MyThread();t.start();//启动线程&a…...
【C++】类和对象练习——日期类的实现
文章目录前言1. 日期的合法性判断2. 日期天数(/)2.1 和的重载2.2 对于两者复用的讨论3. 前置和后置重载4. 日期-天数(-/-)5. 前置- -和后置- -的重载6. 日期-日期7. 流插入<<重载8. 流提取>>重载9. 总结10. 源码展示前…...
[LeetCode周赛复盘] 第 333 场周赛20230219
[LeetCode周赛复盘] 第 333 场周赛20230219 一、本周周赛总结二、 [Easy] 6362. 合并两个二维数组 - 求和法1. 题目描述2. 思路分析3. 代码实现三、[Medium] 6365. 将整数减少到零需要的最少操作数1. 题目描述2. 思路分析3. 代码实现四、[Medium] 6364. 无平方子集计数1. 题目描…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
