广东建设局网站,室内设计作品集,百度商桥的代码放到网站里,沈阳做网站多少钱AcWing《蓝桥杯集训每日一题》—— 1460. 我在哪#xff1f; 文章目录AcWing《蓝桥杯集训每日一题》—— 1460. 我在哪#xff1f;一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的#xff0c;转md文件可能不太美观#xff0c;大家可以去我的博客中查看 文章目录AcWing《蓝桥杯集训·每日一题》—— 1460. 我在哪一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、题目 农夫约翰出门沿着马路散步但是他现在发现自己可能迷路了 沿路有一排共 NNN 个农场。
不幸的是农场并没有编号这使得约翰难以分辨他在这条路上所处的位置。
然而每个农场都沿路设有一个彩色的邮箱所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..ZA..ZA..Z 之间的一个字母来指定所以沿着道路的 NNN 个邮箱的序列可以用一个长为 NNN 的由字母 A..ZA..ZA..Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 A..ZA..ZA..Z 的值使得他查看任意连续 KKK 个邮箱序列他都可以唯一确定这一序列在道路上的位置。
例如假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K3K 3K3因为如果他看到了 ABC则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K4K 4K4因为如果他查看任意连续 4 个邮箱那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 NNN第二行包含一个由 NNN 个字符组成的字符串每个字符均在 A..ZA..ZA..Z 之内。
输出格式
输出一行包含一个整数为可以解决农夫约翰的问题的最小 KKK 值。
数据范围
1≤N≤1001≤ N ≤1001≤N≤100
输入样例
7
ABCDABC输出样例
4二、解题思路 当我们看到这道题目的时候我们需要思考如何根据颜色的连续性来确定当前位置从而找到最小的连续颜色长度K。最简单的想法就是从1到N依次枚举K的长度然后在每个长度下枚举所有的子串并判断这个子串是否在后面的部分出现过如果出现过则表示当前长度K不行需要继续增加K的长度进行判断。这里我介绍两种方法。 1、暴力枚举法
对于暴力枚举法我们可以使用两重循环外层循环枚举K的长度内层循环枚举所有的子串并在后面的部分中查找该子串是否出现过。如果没有找到则表示当前长度K可行输出K并结束程序。如果内层循环结束后仍未找到合适的K则需要继续外层循环进行下一轮枚举。
2、二分法
对于二分法我们可以将判断一个长度K是否可行转化为判断以每个位置为起点的长度为K的子串是否互不相同。具体地我们可以将所有以长度K的子串存入一个集合中然后判断集合中的元素个数是否等于N-K1。如果等于则表示当前长度K可行否则不可行。因为如果有重复的子串那么集合中的元素个数会小于N-K1如果没有重复的子串则集合中的元素个数会等于N-K1。根据这个判断结果来缩小二分法的搜索范围直到找到最小可行的K。
三、代码实现
暴力枚举解法 n int(input()) # 输入农场数
s input().strip() # 输入邮筒序列res n # 初始化最小连续颜色长度res为nfor k in range(1, n1): # 外层循环枚举连续颜色长度k从1到nseen set() # 定义一个集合seen用于存储当前长度为k的所有子串unique True # 初始化unique为True# 内层循环枚举字符串s中长度为k的所有子串for i in range(n-k1):sub s[i:ik] # 取出从i开始长度为k的子串subif sub in seen: # 如果sub已经在seen中出现过了说明有重复子串此时unique为Falseunique Falsebreakelse:seen.add(sub) # 否则将sub加入seen集合中if unique: # 如果unique为True说明当前枚举的k值可以唯一确定任意连续k个邮箱序列在道路上的位置res k # 更新最小连续颜色长度resbreakprint(res) # 输出最小的k值即可以解决农夫约翰的问题的最小K值该段代码的时间复杂度为 O(n2)O(n^2)O(n2)因为外层循环枚举了 kkk 个长度内层循环每次需要枚举 n−k1n-k1n−k1 个长度为 kkk 的子串并且使用了 set 进行查重。set 的查找时间复杂度为 O(1)O(1)O(1)所以内层循环的时间复杂度为 O((n−k1)×1)O(n−k1)O((n-k1) \times 1) O(n-k1)O((n−k1)×1)O(n−k1)。因此总的时间复杂度为∑k1n(n−k1)O(n2)\sum_{k1}^{n} (n-k1) O(n^2)∑k1n(n−k1)O(n2)
其中∑k1n(n−k1)\sum_{k1}^{n} (n-k1)∑k1n(n−k1) 是等差数列求和公式的展开形式。
二分解法
n int(input()) # 输入农场数
s input().strip() # 输入邮筒序列def check(k): # 定义check函数用来检查k的取值是否满足条件substrings set() # 用set存储s中所有长度为k的不同的子串for i in range(n-k1):substrings.add(s[i:ik])return len(substrings) n-k1 # 如果set中的元素个数为n-k1则说明所有长度为k的子串均不相同left, right 1, n # 初始时left1,rightn
while left right: # 当left right时循环继续mid (leftright)//2 # 计算中间值midif check(mid): # 如果check(mid)返回True则说明kmid满足条件应该继续往左找right midelse: # 如果check(mid)返回False则说明kmid不满足条件应该往右找left mid1print(left) # 最终left就是满足条件的最小的k该二分法代码的时间复杂度为O(nlogn)O(nlogn)O(nlogn)**其中nnn为字符串的长度。主要耗时的是check函数时间复杂度为O(nk)O(nk)O(nk)kkk是检查的子串长度当knknkn时时间复杂度最大为O(n2)O(n^2)O(n2)。而二分法中循环的次数最多为O(logn)O(logn)O(logn)因此总时间复杂度为O(n∗logn)O(n*logn)O(n∗logn)。
