当前位置: 首页 > news >正文

【蓝桥杯集训·每日一题】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中的mapset等容器就是基于哈希表。
  • 关于代码中涉及的一些操作:
    unordered_set 是无序的set,而且对容器中元素去重。
    count() 用于查找某个数(或字符或字符串)出现的次数。
    insert() 向哈希表中插入一个元素。

相关文章:

【蓝桥杯集训·每日一题】AcWing 1460. 我在哪?

文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴二分查找哈希表一、题目 1、原题链接 1460. 我在哪&#xff1f; 2、题目描述 农夫约翰出门沿着马路散步&#xff0c;但是他现在发现自己可能迷路了&#xff01; 沿路有一…...

一个不可忽视的重要能力

阅读本文大概需要 2.16 分钟。1、自我们开工后&#xff0c;年后第一场直播&#xff0c;场观二十万出头&#xff0c;以为是不是巧合还是卡 bug 了&#xff0c;就最近又测了下&#xff0c;发现连续几场直播下来&#xff0c;场观数据依旧很吓人&#xff0c;都是十几二十万&#xf…...

2023.2.6-2.12 AI行业周刊(第136期):住院

周末把父亲送到医院&#xff0c;安顿下来&#xff0c;这周还是决定做膝关节的手术了。 一辈子长期的劳累&#xff0c;加上前两年搬家时的辛苦&#xff0c;最终导致膝关节受损严重。 这两年来&#xff0c;走路每一步都很疼&#xff0c;纠结了很久&#xff0c;去了上海&#xf…...

听说2年以上的自动化测试都有16k+,4年10k的你还要等待奇迹吗?

个人简介学渣一枚&#xff0c;2017年6月某xx学校毕业。从事自动化测试已经4年&#xff0c;。2018年的时候&#xff0c;由于项目的原因&#xff0c;开始使用Robot Framework测试框架&#xff0c;正因为有Python的基础所以很快就理解了Robot Framework框架的工作原理&#xff0c;…...

git 命令实战

大家好&#xff0c;我是 17。 今天和大家一起用前面学过的命令做过实践。 git 命令实战 你在分支 A,一个同事在分支 B fix 了一个bug。你不方便 merge 分支B,只想更新这个 fix bug 的提交。 最先想到的是 cherry-pick&#xff0c;但还有两个办法&#xff0c;git restore&am…...

基于机器学习LSTM的古代汉语切分标注算法及语料库研究 完整代码+数据+论文

完整代码&#xff1a;https://download.csdn.net/download/qq_38735017/87382302摘 要近年来&#xff0c;深度学习的浪潮渗透在科研和生活领域的方方面面&#xff0c;本文主要研究深度学习在自然语言处理&#xff0c;尤其是古汉语自然语言处理方面的应用。本文旨在利用计算机帮…...

魔百和M401A刷入Armbian系统EMMC开启wifi

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

超实用的小红书内容营销策略分享!纯干货

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

高压放大器在介电泳效应的细胞分选研究中的应用

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

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 总线的工件台运动控制系统研究与开发-以光刻运动台为例(一)

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

回溯算法理论基础

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

【STM32笔记】低功耗模式下GPIO省电配置避坑实验(闲置引脚配置为模拟输入其实更耗电)

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

AI算法创新赛-人车目标检测竞赛总结02

源码目录--AI0000026/ --models/ #存放原始模型文件 --scripts/ #存放模型编译、量化所用到的命令脚本&#xff0c;标签格式转换的脚本。 --data/ #存放B榜数据集102张图片 --bmodel/ #存放编译或量化生成的xxx.bmodel --test/ #存放执行推理的代码&#xff0c;会调用bmodel/中…...

Python 编程必备:盘点nginx和gunicorn的几大用法,建议收藏

程序员是新兴技术工种中比较高薪的一个&#xff0c;在互联网公司&#xff0c;程序员往往与秃头&#xff0c;压力大&#xff0c;找不到女朋友等等挂钩。 最近&#xff0c;最新技能类榜单出炉&#xff0c;这是一个关于程序员自己给自己贴的几个标签。 其中&#xff0c;不难看出…...

USB3.0移动硬盘启动Win7的方法(AHCI/AMD USB3.0/Win7)

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

Python学习-----函数3.0(嵌套函数、闭包、装饰器)

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

最新版EasyRecovery数据恢复软件使用测评介绍

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

关于知识图谱TransR

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

始于日志,不止于日志,Elastic Stack全面介绍

1、Elastic Stack是什么&#xff1f; 说Elastic Stack之前&#xff0c;先说一下ELK Stack。这个词相信很多人都是耳熟能详的&#xff0c;作为一个著名的日志系统解决方案&#xff0c;应用非常广泛。 “ELK”是三个开源项目的首字母缩写词&#xff1a;Elasticsearch、Logstash…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...