当前位置: 首页 > news >正文

算法刷题Day28:BM66 最长公共子串

题目链接,点击跳转

题目描述:

在这里插入图片描述

解题思路:

方法一:暴力枚举

  1. 遍历str1的每个字符x,并在str2中寻找以相同元素x为起始的最长字符串。
  2. 记录最长的公共子串及其长度。

代码实现:

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)),其中 nm 分别是两个字符串的长度。
空间复杂度:O(1)
缺点:时间复杂度过高,在字符串较长时会超时。

方法二:动态规划

  1. 使用一个二维数组来记录子串长度
  2. 状态转移方程
    如果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),其中 nm 分别是两个字符串的长度。
空间复杂度: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 最长公共子串

题目链接&#xff0c;点击跳转 题目描述&#xff1a; 解题思路&#xff1a; 方法一&#xff1a;暴力枚举 遍历str1的每个字符x&#xff0c;并在str2中寻找以相同元素x为起始的最长字符串。记录最长的公共子串及其长度。 代码实现&#xff1a; def LCS(self, str1: str, st…...

论文阅读笔记:MambaOut: Do We Really Need Mamba for Vision?

论文阅读笔记&#xff1a;MambaOut: Do We Really Need Mamba for Vision? 1 背景2 创新点3 方法4 模块4.1 Mamba适合什么任务4.2 视觉识别任务是否有很长的序列4.3 视觉任务是否需要因果token混合模式4.4 关于Mamba对于视觉的必要性假设 5 效果 论文&#xff1a;https://arxi…...

HarmonyOS:ForEach:循环渲染

一、前言 ForEach接口基于数组类型数据来进行循环渲染&#xff0c;需要与容器组件配合使用&#xff0c;且接口返回的组件应当是允许包含在ForEach父容器组件中的子组件。例如&#xff0c;ListItem组件要求ForEach的父容器组件必须为List组件。 API参数说明见&#xff1a;ForEa…...

Python3 【函数】项目实战:5 个新颖的学习案例

Python3 【函数】项目实战&#xff1a;5 个新颖的学习案例 本文包含5编程学习案例&#xff0c;具体项目如下&#xff1a; 简易聊天机器人待办事项提醒器密码生成器简易文本分析工具简易文件加密解密工具 项目 1&#xff1a;简易聊天机器人 功能描述&#xff1a; 实现一个简易…...

XSS 漏洞全面解析:原理、危害与防范

目录 前言​编辑 漏洞原理 XSS 漏洞的危害 检测 XSS 漏洞的方法 防范 XSS 漏洞的措施 前言 在网络安全的复杂版图中&#xff0c;XSS 漏洞&#xff0c;即跨站脚本攻击&#xff08;Cross - Site Scripting&#xff09;&#xff0c;是一类极为普遍且威胁巨大的安全隐患。随着互…...

从 GShard 到 DeepSeek-V3:回顾 MoE 大模型负载均衡策略演进

作者&#xff1a;小天狼星不来客 原文&#xff1a;https://zhuanlan.zhihu.com/p/19117825360 故事要从 GShard 说起——当时&#xff0c;人们意识到拥有数十亿甚至数万亿参数的模型可以通过某种形式的“稀疏化&#xff08;sparsified&#xff09;”来在保持高精度的同时加速训…...

【回溯+剪枝】回溯算法的概念 全排列问题

文章目录 46. 全排列Ⅰ. 什么是回溯算法❓❓❓Ⅱ. 回溯算法的应用1、组合问题2、排列问题3、子集问题 Ⅲ. 解题思路&#xff1a;回溯 剪枝 46. 全排列 46. 全排列 ​ 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 …...

Flutter解决macbook M芯片Android Studio中不显示IOS真机的问题

下载了最新的Android Studio LadyBug 下载了最新的xcode16.2 结果&#xff0c;只有安卓真机才在Android studio显示&#xff0c; IOS真机只在xcode显示 IOS真机不在android studio显示。 解决方法是&#xff1a; 在终端运行如下命令&#xff1a; sudo xcode-select -s /Applic…...

自签证书的dockerfile中from命令无法拉取镜像而docker的pull命令能拉取镜像

问题现象&#xff1a; docker pull images拉取镜像正常 dockerfile中的from命令拉取镜像就会报出证书错误。报错信息如下&#xff1a; [bjxtbwj-kvm-test-jenkins-6-243 ceshi_dockerfile]$ docker build . [] Building 0.4s (3/3) FINISHED …...

【MySQL】--- 复合查询 内外连接

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; MySQL &#x1f3e0; 基本查询回顾 假设有以下表结构&#xff1a; 查询工资高于500或岗位为MANAGER的雇员&#xff0c;同时还要满足他们的姓名首字母为…...

QT TLS initialization failed

qt使用QNetworkAccessManager下载文件&#xff08;给出的链接可以在浏览器里面下载文件&#xff09;&#xff0c;下载失败&#xff0c; 提示“TLS initialization failed”通常是由于Qt在使用HTTPS进行文件下载时&#xff0c;未能正确初始化TLS&#xff08;安全传输层协议&…...

系统学英语 — 句法 — 复合句

目录 文章目录 目录复合句型主语从句宾语从句表语从句定语从句状语从句同位语从句 复合句型 复合句型&#xff0c;即&#xff1a;从句。在英语中&#xff0c;除了谓语之外的所有句子成分都可以使用从句来充当。 主语从句 充当主语的句子&#xff0c;通常位于谓语之前&#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; } 观察得到&#xff0c;数组名就是数组首…...

16.Word:石油化工设备技术❗【28】

目录 题目 NO1.2 NO3 NO4 题目 NO1.2 F12&#xff1a;另存为将“Word素材.docx”文件另存为“Word. docx”&#xff08;“docx”为文件扩展名&#xff09; 光标来到表格上方→插入→形状→新建画布→单击选中→格式→高度/宽度&#xff08;格式→大小对话框→取消勾选✔锁定…...

Python-基础环境(01) 虚拟环境,Python 基础环境之虚拟环境,一篇文章助你完全搞懂!

Python的虚拟环境是一种工具&#xff0c;它能够创建一个隔离的独立Python环境。每个虚拟环境都有自己独立的Python解释器和安装的包&#xff0c;不会与其他虚拟环境或系统的全局Python环境发生冲突。虚拟环境特别适用于以下情况&#xff1a; 项目隔离&#xff1a;不同的项目可…...

Dest1ny漏洞库:用友 U8-CRM 系统 ajaxgetborrowdata.php 存在 SQL 注入漏洞

用友U8-CRM系统ajaxgetborrowdata.php存在SQL注入漏洞&#xff0c;文件多个方法存在SQL注入漏洞&#xff0c;未经身份验证的攻击者通过漏洞执行任意SQL语句&#xff0c;调用xp_cmdshell写入后门文件&#xff0c;执行任意代码&#xff0c;从而获取到服务器权限。 hunter app.n…...

java.sql.Date 弃用分析与替代方案

引言 java.sql.Date 是 Java 标准库中的一个类&#xff0c;它继承自 java.util.Date&#xff0c;主要用于在 Java 应用程序与数据库之间进行日期数据的传输。然而&#xff0c;随着 Java 语言的发展&#xff0c;java.sql.Date 以及其父类 java.util.Date 逐渐被认为存在设计缺陷…...

HarmonyOS:状态管理最佳实践

一、概述 在声明式UI编程范式中&#xff0c;UI是应用程序状态的函数&#xff0c;应用程序状态的修改会更新相应的UI界面。ArkUI采用了MVVM模式&#xff0c;其中ViewModel将数据与视图绑定在一起&#xff0c;更新数据的时候直接更新视图。如下图所示&#xff1a; ArkUI的MVVM模式…...

如何提高新产品研发效率

优化研发流程、采用先进工具、提升团队协作、持续学习与改进&#xff0c;是提高新产品研发效率的关键。其中&#xff0c;优化研发流程尤为重要。通过简化流程&#xff0c;减少不必要的环节和复杂性&#xff0c;企业可以显著提升研发效率。例如&#xff0c;采用自动化测试工具和…...

MongoDB平替数据库对比

背景 项目一直是与实时在线监测相关&#xff0c;特点数据量大&#xff0c;读写操作大&#xff0c;所以选用的是MongoDB。但按趋势来讲&#xff0c;需要有一款国产数据库可替代&#xff0c;实现信创要求。选型对比如下 1. IoTDB 这款是由清华大学主导的开源时序数据库&#x…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...