【蓝桥杯集训·每日一题】AcWing 1460. 我在哪?
文章目录
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、知识风暴
- 二分查找
- 哈希表
一、题目
1、原题链接
1460. 我在哪?
2、题目描述
农夫约翰出门沿着马路散步,但是他现在发现自己可能迷路了!
沿路有一排共 N 个农场。
不幸的是农场并没有编号,这使得约翰难以分辨他在这条路上所处的位置。
然而,每个农场都沿路设有一个彩色的邮箱,所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A…Z 之间的一个字母来指定,所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A…Z
组成的字符串来表示。某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值,使得他查看任意连续 K 个邮箱序列,他都可以唯一确定这一序列在道路上的位置。
例如,假设沿路的邮箱序列为
ABCDABC
。约翰不能令 K=3,因为如果他看到了 ABC,则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4,因为如果他查看任意连续 4 个邮箱,那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N,第二行包含一个由 N 个字符组成的字符串,每个字符均在 A…Z 之内。
输出格式
输出一行,包含一个整数,为可以解决农夫约翰的问题的最小 >K 值。
数据范围
1≤N≤100
输入样例:
7 ABCDABC
输出样例:
4
二、解题报告
1、思路分析
思路来源:AcWing 1460. 我在哪?(蓝桥杯集训·每日一题)
y总yyds
数据量为100,时间复杂度控制在 O(n3) 左右。
暴力解法:
(1)题目要求的是长度最小的子串,且满足该子串与任意一个子串都不相同,求此最小长度k
。
(2)暴力枚举,第一层枚举所有k的可能取值,第二层枚举长度为k
的所有子串,第三层判断以当前长度k
作为答案是否满足条件(即判断是否存在长度为k
的子串与当前子串相同,如果都不相同,则k满足条件直接输出,否则继续查找),直到找到答案为止。
二分+哈希优化:
(1)在暴力基础上,利用二分来查找满足条件的k(因为k是满足条件的最小长度,所以小于k的的数一定不满足条件,而大于等于k的一定满足条件,具有二段性,可以二分),取代第一层循环。
(2)利用哈希表来查找是否存在长度为k,与当前子串长度相同的子串,取代字符串相等的比较。
2、时间复杂度
暴力解法时间复杂度最坏情况O(n4)
优化解法时间复杂度O(n2logn)
3、代码详解
暴力解法代码
#include <iostream>
#include <string>
using namespace std;
int n;
string s;
int main(){cin>>n;cin>>s;for(int k=1;k<=n;k++){ //枚举k的所有可能取值bool flag=true; //记录当前k是否满足条件for(int i=0;i<n-k+1;i++){ //枚举长度为k的子串for(int j=i+1;j<n-k+1;j++){ //枚举剩余字符串的子串中长度为k的子串if(s.substr(i,k)==s.substr(j,k)){ //如果存在与当前长度为k的子串相同的子串,则当前k满足条件,直接跳出循环 flag=false; break;}}if(!flag) break; //当前k不满足条件,直接跳出循环}if(flag){ //当前k满足条件,输出k,跳出循环,程序结束cout<<k;break;}}return 0;
}
优化代码
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int n;
string s;
unordered_set<string> st; //哈希表存储每个子串
//判断长度为x作为答案是否满足条件
bool check(int x){//枚举所有长度为x的子串for(int i=0;i<n-x+1;i++){string tmp=s.substr(i,x);if(!st.count(tmp)) st.insert(tmp); //如果不存在与该子串相同的子串,则将该子串放入哈希表中else return false; //如果存在与该子串相同的子串,则说明不满足条件,直接返回false}return true; //如果遍历完所有长度为x的子串且这些子串互不相等,则x满足题目要求,返回true
}
int main(){cin>>n;cin>>s;int l=1,r=n; //答案k范围在区间[1,n]//二分查找答案while(l<r){int mid=l+r>>1;if(check(mid)) r=mid; //如果mid满足条件,则说明mid比答案k大,将搜索区间缩小为[l,mid]else l=mid+1; //如果mid不满足条件,则说明mid比答案k小,将搜索区间缩小为[mid+1,r]}cout<<l;return 0;
}
三、知识风暴
二分查找
- 二分查找可以快速地进行查找,每次将区间缩小一半,只要符合某个数只有两种情况:满足条件或者不满足条件,就可以用二分来查找满足条件或者不满足条件的分界点。
哈希表
- 哈希表存储一种映射关系,可以快速地进行查找,STL中的
map
、set
等容器就是基于哈希表。- 关于代码中涉及的一些操作:
unordered_set
是无序的set,而且对容器中元素去重。
count()
用于查找某个数(或字符或字符串)出现的次数。
insert()
向哈希表中插入一个元素。
相关文章:
【蓝桥杯集训·每日一题】AcWing 1460. 我在哪?
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴二分查找哈希表一、题目 1、原题链接 1460. 我在哪? 2、题目描述 农夫约翰出门沿着马路散步,但是他现在发现自己可能迷路了! 沿路有一…...
一个不可忽视的重要能力
阅读本文大概需要 2.16 分钟。1、自我们开工后,年后第一场直播,场观二十万出头,以为是不是巧合还是卡 bug 了,就最近又测了下,发现连续几场直播下来,场观数据依旧很吓人,都是十几二十万…...

2023.2.6-2.12 AI行业周刊(第136期):住院
周末把父亲送到医院,安顿下来,这周还是决定做膝关节的手术了。 一辈子长期的劳累,加上前两年搬家时的辛苦,最终导致膝关节受损严重。 这两年来,走路每一步都很疼,纠结了很久,去了上海…...

听说2年以上的自动化测试都有16k+,4年10k的你还要等待奇迹吗?
个人简介学渣一枚,2017年6月某xx学校毕业。从事自动化测试已经4年,。2018年的时候,由于项目的原因,开始使用Robot Framework测试框架,正因为有Python的基础所以很快就理解了Robot Framework框架的工作原理,…...
git 命令实战
大家好,我是 17。 今天和大家一起用前面学过的命令做过实践。 git 命令实战 你在分支 A,一个同事在分支 B fix 了一个bug。你不方便 merge 分支B,只想更新这个 fix bug 的提交。 最先想到的是 cherry-pick,但还有两个办法,git restore&am…...

基于机器学习LSTM的古代汉语切分标注算法及语料库研究 完整代码+数据+论文
完整代码:https://download.csdn.net/download/qq_38735017/87382302摘 要近年来,深度学习的浪潮渗透在科研和生活领域的方方面面,本文主要研究深度学习在自然语言处理,尤其是古汉语自然语言处理方面的应用。本文旨在利用计算机帮…...

魔百和M401A刷入Armbian系统EMMC开启wifi
文章目录一、Armbian系统写入U盘二、U盘内uEnv.txt文件修改三、盒子从U盘进行启动四、设置用户名和密码五、Armbian系统写入EMMC六、 重启系统reboot(不可以拔U盘)七、盒子关机拔出U盘八、插入USB无线网卡,连接wifi上次盒子刷了5.15版本的armbian系统,可…...

超实用的小红书内容营销策略分享!纯干货
抓住小红书内容流量密码就是掌握了财富,越来越多的品牌方和商家都在小红书上收获了相当可观的用户流量,如果你的小红书营销没有什么起色,那绝对是没有走对方向。 小红书是一个内容为王的平台,如果你还不懂下面这些小红书内容营销…...

高压放大器在介电泳效应的细胞分选研究中的应用
实验名称:高压放大器在介电泳效应的细胞分选研究中的应用研究方向:生物医学测试目的:细胞分选在分析化学和生物医药领域有着非常重要的应用。在众多的分选方法中,微流控分选方法以其响应速度快、样品需求少等优点成为研究热门。微…...

Redis三 高级篇-3. 最佳实践
《Redis三 高级篇-3. 最佳实践》 提示: 本材料只做个人学习参考,不作为系统的学习流程,请注意识别!!! 《Redis三 高级篇-3. 最佳实践》《Redis三 高级篇-3. 最佳实践》1、Redis键值设计1.1、优雅的key结构1.2、拒绝BigKey1.2.1、BigKey的危害1.2.2、如何发现BigKey①redis-cli…...

基于 VPX 总线的工件台运动控制系统研究与开发-以光刻运动台为例(一)
工件台系统是光刻机的关键子系统之一,工件台运动控制系统对实现光刻机性能指标具有至关重要的作用,因此研发工件台运动控制系统具有极其重要的工程应用价值。论文根据工件台控制系统必须具备的并行性、同步性和实时性等技术需求,建立了基于 V…...

回溯算法理论基础
目录什么是回溯法回溯法的效率回溯法解决的问题如何理解回溯法回溯法模板什么是回溯法 回溯法也可以叫做回溯搜索法,它是一种搜索的方式。 回溯是递归的副产品,只要有递归就会有回溯。 所以以下讲解中,回溯函数也就是递归函数,指…...

【STM32笔记】低功耗模式下GPIO省电配置避坑实验(闲置引脚配置为模拟输入其实更耗电)
【STM32笔记】低功耗模式下GPIO省电配置避坑实验(闲置引脚配置为模拟输入其实更耗电) 前文: blog.csdn.net/weixin_53403301/article/details/128216064 【STM32笔记】HAL库低功耗模式配置(ADC唤醒无法使用、低功耗模式无法烧录解…...

AI算法创新赛-人车目标检测竞赛总结02
源码目录--AI0000026/ --models/ #存放原始模型文件 --scripts/ #存放模型编译、量化所用到的命令脚本,标签格式转换的脚本。 --data/ #存放B榜数据集102张图片 --bmodel/ #存放编译或量化生成的xxx.bmodel --test/ #存放执行推理的代码,会调用bmodel/中…...

Python 编程必备:盘点nginx和gunicorn的几大用法,建议收藏
程序员是新兴技术工种中比较高薪的一个,在互联网公司,程序员往往与秃头,压力大,找不到女朋友等等挂钩。 最近,最新技能类榜单出炉,这是一个关于程序员自己给自己贴的几个标签。 其中,不难看出…...

USB3.0移动硬盘启动Win7的方法(AHCI/AMD USB3.0/Win7)
古董电脑(intel处理器,无USB3.0接口)突然坏了,已经没有维修价值了,硬盘还是完好的。欲把硬盘拆下来,装到USB3.0硬盘盒上,然后在新电脑(AMD R5-4650G/A520)上从USB3.0硬盘盒上启动。 一、需要工具 SATA数据线PS/2鼠标…...

Python学习-----函数3.0(嵌套函数、闭包、装饰器)
目录 1.函数嵌套 2.闭包 3.装饰器 这一节,我会详细Python中讲解函数的进阶内容,包括嵌套函数、闭包和装饰器。一起来学习吧!!! 1.函数嵌套 概念:函数里面再定义一个函数 作用:当我们在一个多…...

最新版EasyRecovery数据恢复软件使用测评介绍
我们在逐渐适应信息电子化的同时,也有一些潜在的麻烦接踵而来,其中较为常见的就是文件和数据的保存问题。显然,设备的存储空间是有限的,这就不可避免地会出现数据被删除、覆盖或丢失的现象,如果丢失的是重要数据&#…...

关于知识图谱TransR
论文题目 Learning Entity and Relation Embeddings for Knowledge Graph Completion 论文链接 TransR 文中指出,不管是TransE还是TransH都是将实体和关系映射同一空间,但是,一个实体可能具有多个层面的信息,不同的关系可能关注…...

始于日志,不止于日志,Elastic Stack全面介绍
1、Elastic Stack是什么? 说Elastic Stack之前,先说一下ELK Stack。这个词相信很多人都是耳熟能详的,作为一个著名的日志系统解决方案,应用非常广泛。 “ELK”是三个开源项目的首字母缩写词:Elasticsearch、Logstash…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...