内蒙古城乡建设网站,网站标签名词,游戏程序开发,企业应该做几个网站文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴二分查找哈希表一、题目
1、原题链接 1460. 我在哪#xff1f; 2、题目描述 农夫约翰出门沿着马路散步#xff0c;但是他现在发现自己可能迷路了#xff01; 沿路有一…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴二分查找哈希表一、题目
1、原题链接 1460. 我在哪 2、题目描述 农夫约翰出门沿着马路散步但是他现在发现自己可能迷路了 沿路有一排共 N 个农场。 不幸的是农场并没有编号这使得约翰难以分辨他在这条路上所处的位置。 然而每个农场都沿路设有一个彩色的邮箱所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。 每个邮箱的颜色用 A…Z 之间的一个字母来指定所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A…Z 组成的字符串来表示。 某些邮箱可能会有相同的颜色。 约翰想要知道最小的 K 的值使得他查看任意连续 K 个邮箱序列他都可以唯一确定这一序列在道路上的位置。 例如假设沿路的邮箱序列为 ABCDABC 。 约翰不能令 K3因为如果他看到了 ABC则沿路有两个这一连续颜色序列可能所在的位置。 最小可行的 K 的值为 K4因为如果他查看任意连续 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(){cinn;cins;for(int k1;kn;k){ //枚举k的所有可能取值bool flagtrue; //记录当前k是否满足条件for(int i0;in-k1;i){ //枚举长度为k的子串for(int ji1;jn-k1;j){ //枚举剩余字符串的子串中长度为k的子串if(s.substr(i,k)s.substr(j,k)){ //如果存在与当前长度为k的子串相同的子串则当前k满足条件直接跳出循环 flagfalse; break;}}if(!flag) break; //当前k不满足条件直接跳出循环}if(flag){ //当前k满足条件输出k跳出循环程序结束coutk;break;}}return 0;
}优化代码
#include iostream
#include string
#include unordered_set
using namespace std;
int n;
string s;
unordered_setstring st; //哈希表存储每个子串
//判断长度为x作为答案是否满足条件
bool check(int x){//枚举所有长度为x的子串for(int i0;in-x1;i){string tmps.substr(i,x);if(!st.count(tmp)) st.insert(tmp); //如果不存在与该子串相同的子串则将该子串放入哈希表中else return false; //如果存在与该子串相同的子串则说明不满足条件直接返回false}return true; //如果遍历完所有长度为x的子串且这些子串互不相等则x满足题目要求返回true
}
int main(){cinn;cins;int l1,rn; //答案k范围在区间[1,n]//二分查找答案while(lr){int midlr1;if(check(mid)) rmid; //如果mid满足条件则说明mid比答案k大将搜索区间缩小为[l,mid]else lmid1; //如果mid不满足条件则说明mid比答案k小,将搜索区间缩小为[mid1,r]}coutl;return 0;
}三、知识风暴 二分查找 二分查找可以快速地进行查找每次将区间缩小一半只要符合某个数只有两种情况满足条件或者不满足条件就可以用二分来查找满足条件或者不满足条件的分界点。 哈希表 哈希表存储一种映射关系可以快速地进行查找STL中的map、set等容器就是基于哈希表。关于代码中涉及的一些操作 unordered_set 是无序的set而且对容器中元素去重。 count() 用于查找某个数或字符或字符串出现的次数。 insert() 向哈希表中插入一个元素。
