做进口产品的网站,徐州网站开发哪个好薇,网站开发费用清单,企业加盟网站建设1 问题 给定一个字符串“S”#xff0c;找出其中不含有重复字符的最长子串的长度。例如#xff1a;S‘ABCABCBB’#xff0c;则不含重复字符的最长字串长度为3.。S‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能#xff1f; 2 方法 按照一… 1 问题 给定一个字符串“S”找出其中不含有重复字符的最长子串的长度。例如S‘ABCABCBB’则不含重复字符的最长字串长度为3.。S‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能 2 方法 按照一般方法可以采取暴力求解即把所有不重复的字串全部找出来再在其中找出最长的字串。可是该方法的时间复杂度和空间复杂度都十分大面对较长的字符串则会浪费过多时间。 对于该现象即可使用“滑动窗口”算法。滑动窗口算法也是一种思想是双指针的拓展和延伸。滑动指这个窗口是移动的也就是移动是按照一定方向来的。窗口窗口大小并不是固定的可以不断扩容直到满足一定的条件也可以不断缩小直到找到一个满足条件的最小窗口当然也可以是固定大小。 面对前面所提出的问题使用“滑动窗口”算法大致思路为 设置两个指针和一个空列表固定左指针不断右移右指针同时更新最长不重复字符串长度如果出现重复字符再右移左指针如此重复直到遍历完字符串的所有字符。最后输出最长不重复字符串长度即可。 这样就降低了问题的复杂度也降低了循环的嵌套深度。 代码清单 1 通过固定左端元素再右端元素不断右移算出左端和右端间的总数然后左端再不断右移不断计算之间的总数。最后算出最长长度s input() # 输入字符串max_length float(-inf) # 定义一个初指为负无穷start 0 # 定义左指针为0l list() # 定义一个空列表用于是否重复的判断for end in range(len(s)): # 右指针通过for循环逐步向右移动 while s[end] in l: # 当右指针移到某个值时且该值已经在前面出现过 l.remove(s[start]) # 移除左指针对应的重复值 start 1 # 并且将左指针向右移动一个单位 max_length max(max_length, end-start1) # 每次右指针移动后统计不重复的字符串的最长长度 l.append(s[end]) # 将右指针每次遍历过的值加入列表中用于重复判断if max_length float(-inf): # 如果最大值对于负无穷则代表无最长不重复字符串 print(0)else: print(max_length) # 打印最大不重复字符串长度测试结果abcabcbb 输出3aaaaaaaa 输出1 3 结语 通过测试发现“滑动窗口”算法可以很好的解决该问题与此同时相对于暴力求解其时间复杂度和空间复杂度也得到了优化。总结发现一般给出的数据结构是数组或者字符串且求取某个子串或者子序列最长最短等最值问题或者求某个目标值时。都可以使用“滑动窗口”算法。
