算法刷题Day28:BM66 最长公共子串
题目链接,点击跳转
题目描述:

解题思路:
方法一:暴力枚举
- 遍历
str1的每个字符x,并在str2中寻找以相同元素x为起始的最长字符串。 - 记录最长的公共子串及其长度。
代码实现:
def LCS(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
max_start = 0
max_end = 0
max_length = 0
for i in range(len1):
for j in range(len2):
if str2[j] == str1[i]:
pos1 = i
pos2 = j
length = 0
while pos1 < len1 and pos2 < len2 and str1[pos1] == str2[pos2]:
length += 1
pos1 += 1
pos2 += 1
if length > max_length:
max_length = length
max_start = j
max_end = pos2
return str2[max_start:max_end]
分析:
时间复杂度:O(n \* m \* min(n, m)),其中 n 和 m 分别是两个字符串的长度。
空间复杂度:O(1)。
缺点:时间复杂度过高,在字符串较长时会超时。
方法二:动态规划
- 使用一个二维数组来记录子串长度
- 状态转移方程
如果str1[i-1] == str2[j-1],则dp[i][j] = dp[i-1][j-1] +1
如果str1[i-1] != str2[j-1],则dp[i][j] = 0
代码实现:
def LCS(self, str1: str, str2: str) -> str:
len1 = len(str1)
len2 = len(str2)
max_end = 0
max_length = 0
dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_end = j
max_length = dp[i][j]
else:
dp[i][j] = 0
return str2[max_end - max_length:max_end]
时间复杂度:O(n \* m),其中 n 和 m 分别是两个字符串的长度。
空间复杂度:O(n \* m)。
缺点:python版本会超时
方法三:滑动窗口
1.遍历较长的字符串,判断窗口内的字符,是否存在于在另一个字符串中。
代码实现
def LCS(self, str1: str, str2: str) -> str:
if len(str1) < len(str2):
str1, str2 = str2, str1
res = ""
max_len = 0
for i in range(len(str1)):
if str1[i - max_len:i + 1] in str2:
res = str1[i - max_len:i + 1]
max_len += 1
return res
时间复杂度:O(n\*k\*m)。其中 n 是较长字符串的长度。k 是切片长度,最多为 n。使用 in 判断是否存在于 str2 中,其时间复杂度为 O(m),其中 m 是 str2 的长度。
相关文章:
算法刷题Day28:BM66 最长公共子串
题目链接,点击跳转 题目描述: 解题思路: 方法一:暴力枚举 遍历str1的每个字符x,并在str2中寻找以相同元素x为起始的最长字符串。记录最长的公共子串及其长度。 代码实现: def LCS(self, str1: str, st…...
论文阅读笔记:MambaOut: Do We Really Need Mamba for Vision?
论文阅读笔记:MambaOut: Do We Really Need Mamba for Vision? 1 背景2 创新点3 方法4 模块4.1 Mamba适合什么任务4.2 视觉识别任务是否有很长的序列4.3 视觉任务是否需要因果token混合模式4.4 关于Mamba对于视觉的必要性假设 5 效果 论文:https://arxi…...
HarmonyOS:ForEach:循环渲染
一、前言 ForEach接口基于数组类型数据来进行循环渲染,需要与容器组件配合使用,且接口返回的组件应当是允许包含在ForEach父容器组件中的子组件。例如,ListItem组件要求ForEach的父容器组件必须为List组件。 API参数说明见:ForEa…...
Python3 【函数】项目实战:5 个新颖的学习案例
Python3 【函数】项目实战:5 个新颖的学习案例 本文包含5编程学习案例,具体项目如下: 简易聊天机器人待办事项提醒器密码生成器简易文本分析工具简易文件加密解密工具 项目 1:简易聊天机器人 功能描述: 实现一个简易…...
XSS 漏洞全面解析:原理、危害与防范
目录 前言编辑 漏洞原理 XSS 漏洞的危害 检测 XSS 漏洞的方法 防范 XSS 漏洞的措施 前言 在网络安全的复杂版图中,XSS 漏洞,即跨站脚本攻击(Cross - Site Scripting),是一类极为普遍且威胁巨大的安全隐患。随着互…...
从 GShard 到 DeepSeek-V3:回顾 MoE 大模型负载均衡策略演进
作者:小天狼星不来客 原文:https://zhuanlan.zhihu.com/p/19117825360 故事要从 GShard 说起——当时,人们意识到拥有数十亿甚至数万亿参数的模型可以通过某种形式的“稀疏化(sparsified)”来在保持高精度的同时加速训…...
【回溯+剪枝】回溯算法的概念 全排列问题
文章目录 46. 全排列Ⅰ. 什么是回溯算法❓❓❓Ⅱ. 回溯算法的应用1、组合问题2、排列问题3、子集问题 Ⅲ. 解题思路:回溯 剪枝 46. 全排列 46. 全排列 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 …...
Flutter解决macbook M芯片Android Studio中不显示IOS真机的问题
下载了最新的Android Studio LadyBug 下载了最新的xcode16.2 结果,只有安卓真机才在Android studio显示, IOS真机只在xcode显示 IOS真机不在android studio显示。 解决方法是: 在终端运行如下命令: sudo xcode-select -s /Applic…...
自签证书的dockerfile中from命令无法拉取镜像而docker的pull命令能拉取镜像
问题现象: docker pull images拉取镜像正常 dockerfile中的from命令拉取镜像就会报出证书错误。报错信息如下: [bjxtbwj-kvm-test-jenkins-6-243 ceshi_dockerfile]$ docker build . [] Building 0.4s (3/3) FINISHED …...
【MySQL】--- 复合查询 内外连接
Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏: MySQL 🏠 基本查询回顾 假设有以下表结构: 查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为…...
QT TLS initialization failed
qt使用QNetworkAccessManager下载文件(给出的链接可以在浏览器里面下载文件),下载失败, 提示“TLS initialization failed”通常是由于Qt在使用HTTPS进行文件下载时,未能正确初始化TLS(安全传输层协议&…...
系统学英语 — 句法 — 复合句
目录 文章目录 目录复合句型主语从句宾语从句表语从句定语从句状语从句同位语从句 复合句型 复合句型,即:从句。在英语中,除了谓语之外的所有句子成分都可以使用从句来充当。 主语从句 充当主语的句子,通常位于谓语之前&#x…...
指针的介绍2前
1.数组名的理解 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int arr[] { 1,2,3,4,5,6,7,8,9 };printf("&arr[0] %p\n", &arr[0]);printf("arr %p\n", arr);return 0; } 观察得到,数组名就是数组首…...
16.Word:石油化工设备技术❗【28】
目录 题目 NO1.2 NO3 NO4 题目 NO1.2 F12:另存为将“Word素材.docx”文件另存为“Word. docx”(“docx”为文件扩展名) 光标来到表格上方→插入→形状→新建画布→单击选中→格式→高度/宽度(格式→大小对话框→取消勾选✔锁定…...
Python-基础环境(01) 虚拟环境,Python 基础环境之虚拟环境,一篇文章助你完全搞懂!
Python的虚拟环境是一种工具,它能够创建一个隔离的独立Python环境。每个虚拟环境都有自己独立的Python解释器和安装的包,不会与其他虚拟环境或系统的全局Python环境发生冲突。虚拟环境特别适用于以下情况: 项目隔离:不同的项目可…...
Dest1ny漏洞库:用友 U8-CRM 系统 ajaxgetborrowdata.php 存在 SQL 注入漏洞
用友U8-CRM系统ajaxgetborrowdata.php存在SQL注入漏洞,文件多个方法存在SQL注入漏洞,未经身份验证的攻击者通过漏洞执行任意SQL语句,调用xp_cmdshell写入后门文件,执行任意代码,从而获取到服务器权限。 hunter app.n…...
java.sql.Date 弃用分析与替代方案
引言 java.sql.Date 是 Java 标准库中的一个类,它继承自 java.util.Date,主要用于在 Java 应用程序与数据库之间进行日期数据的传输。然而,随着 Java 语言的发展,java.sql.Date 以及其父类 java.util.Date 逐渐被认为存在设计缺陷…...
HarmonyOS:状态管理最佳实践
一、概述 在声明式UI编程范式中,UI是应用程序状态的函数,应用程序状态的修改会更新相应的UI界面。ArkUI采用了MVVM模式,其中ViewModel将数据与视图绑定在一起,更新数据的时候直接更新视图。如下图所示: ArkUI的MVVM模式…...
如何提高新产品研发效率
优化研发流程、采用先进工具、提升团队协作、持续学习与改进,是提高新产品研发效率的关键。其中,优化研发流程尤为重要。通过简化流程,减少不必要的环节和复杂性,企业可以显著提升研发效率。例如,采用自动化测试工具和…...
MongoDB平替数据库对比
背景 项目一直是与实时在线监测相关,特点数据量大,读写操作大,所以选用的是MongoDB。但按趋势来讲,需要有一款国产数据库可替代,实现信创要求。选型对比如下 1. IoTDB 这款是由清华大学主导的开源时序数据库&#x…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
