【Leetcode刷题Python】子数组查找

简介: 一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。

深信服公司的算法笔试题

1 题目

一个重复字符串是由两个相同的字符串首尾拼接而成,例如abcabc便是长度为6的一个重复字符串,而abcba则不存在重复字符串。
给定任意字符串,请帮小强找出其中的最长重复子串。
示例

输入
“ababc”
输出
4
说明
abab为最长的重复字符子串,长度为4

2 解析

子串问题一般都是用滑动窗口解决,这里就是一个典型的例子,

  • 我们先将字符串从中间分开,看成两个连续的窗口,最大窗口的长度是字符串长度的一半,函数比较窗口中的内容是否相等,如果相等,返回true,此时的最长重复子串长度等于一个窗口的长度的两倍,即2*i;否则继续移动窗口,移动步数的边界是字符串长度减去此时的两个窗口长度;
  • 在这一层窗口长度中找不到重复子串则缩小窗口长度,重复步骤2,直到窗口长度缩小至0,循环结束

3 Python 实现

def solve(s):
    if s=='':
         return 0
    mid=int(len(s)/2)
    # 记录窗口长度
    res=0
    # 窗口长度最长为一半,且不断减小
    for i in range(mid,-1,-1):
        # j不仅控制着窗口内容的比较,而且控制着窗口的移动,窗口移动的边界条件是字符串长度减去当前的一个窗口长度
        for j in range(len(s)-i):
            # 比较两个窗口中的字符                                    
            if s[j]==s[j+i]:
                res+=1
            # 一旦出现一个字符不相等时,窗口长度置0,从下一个字符开始遍历
            else:
                res=0;
            # 当结果等于当前一个窗口的长度时,返回窗口长度的两倍
            if res==i:
                return 2*i
    return 0
print(solve(str(input())))
AI 代码解读
目录
打赏
0
1
1
0
150
分享
相关文章
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
43 3
|
4月前
|
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
39 0
|
4月前
|
Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)
本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。
34 0
|
4月前
|
Leecode 101刷题笔记之第二章:和你一起你轻松刷题(Python)
本文是关于LeetCode 101刷题笔记的第二章,主要介绍了使用Python解决贪心算法题目的方法和实例。
33 0
|
6月前
|
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
40 1
5个适合新手练习的Python刷题网站
5个适合新手练习的Python刷题网站
609 0

热门文章

最新文章