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

代码随想录算法训练营Day 53 || 1143.最长公共子序列、1035.不相交的线、53. 最大子序和

1143.最长公共子序列

力扣题目链接

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

  • 输入:text1 = "abcde", text2 = "ace"
  • 输出:3
  • 解释:最长公共子序列是 "ace",它的长度为 3。

示例 2:

  • 输入:text1 = "abc", text2 = "abc"
  • 输出:3
  • 解释:最长公共子序列是 "abc",它的长度为 3。

示例 3:

  • 输入:text1 = "abc", text2 = "def"
  • 输出:0
  • 解释:两个字符串没有公共子序列,返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

思路

  1. 定义状态:创建一个二维数组 dp,其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

  2. 状态转移

    • 如果 text1[i-1] == text2[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
    • 否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  3. 初始化dp[0][j]dp[i][0] 都应初始化为 0,因为空字符串与任何字符串的最长公共子序列长度都是 0。

  4. 填充表格:按行或按列填充整个 dp 表格。

  5. 返回结果dp[text1.length][text2.length] 就是最长公共子序列的长度。

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]

1035.不相交的线

力扣题目链接

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。

以这种方法绘制线条,并返回我们可以绘制的最大连线数。

1035.不相交的线

思路

  1. 定义状态:创建一个二维数组 dp,其中 dp[i][j] 表示数组 A 的前 i 个元素和数组 B 的前 j 个元素可以形成的最大连线数。

  2. 状态转移

    • 如果 A[i-1] == B[j-1],则可以在这两个元素之间绘制一条线,因此 dp[i][j] = dp[i-1][j-1] + 1
    • 否则,不能在 A[i-1]B[j-1] 之间绘制线,所以 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  3. 初始化dp[0][j]dp[i][0] 都应初始化为 0,因为当任一数组为空时,最大连线数为 0。

  4. 填充表格:按行或按列顺序填充 dp 表格。

  5. 返回结果dp[A的长度][B的长度] 就是可以绘制的最大连线数。

class Solution:def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:m, n = len(A), len(B)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if A[i - 1] == B[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]

53. 最大子序和

力扣题目链接(opens new window)

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

  • 输入: [-2,1,-3,4,-1,2,1,-5,4]
  • 输出: 6
  • 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

思路

  1. 定义状态:创建一个数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最大子序和。

  2. 状态转移:对于每个 i,有两种情况:

    • nums[i] 加入前面的子数组中,这种情况下最大子序和是 dp[i-1] + nums[i]
    • nums[i] 开始一个新的子数组,这种情况下最大子序和是 nums[i] 自己。 因此,dp[i] = max(dp[i-1] + nums[i], nums[i])
  3. 初始化dp[0] 应该初始化为 nums[0],因为最开始的最大子序和就是数组的第一个元素。

  4. 结果:遍历 dp 数组,找出最大值,即为最大子序和。

class Solution:def maxSubArray(self, nums: List[int]) -> int:n = len(nums)dp = nums.copy()for i in range(1, n):dp[i] = max(dp[i - 1] + nums[i], nums[i])return max(dp)

相关文章:

代码随想录算法训练营Day 53 || 1143.最长公共子序列、1035.不相交的线、53. 最大子序和

1143.最长公共子序列 力扣题目链接 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串&#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符&#xff08;也可以不删除任何…...

Oracle JDBC数据库驱动程序介绍

Maven Central上所有Oracle JDBC数据库驱动程序 现在不仅可以在Maven Central上使用甲骨文数据库最新版本&#xff0c;而且还可以获得所有受支持的Oracle JDBC驱动程序发行版&#xff0c;包括19.3.0.0、18.3.0.0、12.2.0.1和11.2.0.4。从现在开始&#xff0c;Maven Central确实…...

scipy实现单因素方差分析

经典例题 某校高二年级共有四个班&#xff0c;采用四种不同的教学方法进行数学教学&#xff0c;为了比较这四种教学法的效果是否存在明显的差异&#xff0c;期末统考后&#xff0c;从这四个班中各抽取 5 名考生的成绩&#xff0c;如下所示。 班级 一班 二班 三班 四班 …...

深度学习实战59-NLP最核心的模型:transformer的搭建与训练过程详解,手把手搭建与跑通

大家好,我是微学AI,今天给大家介绍一下深度学习实战59-NLP最核心的模型:transformer的搭建与训练过程详解,手把手搭建与跑通。transformer是一种基于自注意力机制的深度学习模型,由Vaswani等人在2017年的论文《Attention is All You Need》中提出。它最初被设计用来处理序…...

一阶滤波器(一阶巴特沃斯滤波器)

连续传递函数G(s) 离散传递函数G(z) 转换为差分方程形式 一阶巴特沃斯滤波器Filter Designer参数设计&#xff1a;参考之前的博客Matlab的Filter Designer工具设计二阶低通滤波器 设计采样频率100Hz&#xff0c;截止频率20Hz。 注意&#xff1a;设计参数使用在离散系统中&…...

.net core中前端vue HTML5 History 刷新页面404问题

放到启动的应用程序的最后面 app.Run(async (context) > {context.Response.ContentType "text/html";await context.Response.SendFileAsync(Path.Combine(env.WebRootPath, "index.html")); });https://blog.csdn.net/lee576/article/details/88355…...

【152.乘积最大子数组】

目录 一、题目描述二、算法原理三、代码实现 一、题目描述 二、算法原理 三、代码实现 class Solution { public:int maxProduct(vector<int>& nums) {int nnums.size();vector<int> f(n);vector<int> g(n);f[0]g[0]nums[0];int retnums[0];for(int i1;…...

如何开发OA系统场景的系统架构

1.开发OA系统场景的系统架构 针对开发OA系统的场景&#xff0c;以下是一个简单的系统架构示例&#xff0c;包括前端、后端和数据库三个基本部分&#xff1a; 前端&#xff1a; 使用React框架进行前端开发&#xff0c;构建用户界面和交互逻辑。前端模块包括日程管理模块、文档管…...

spring boot 集成 RedisSearch 和 RedisJSON

1. 准备工作 环境说明 java 8&#xff1b;redis7.2.2&#xff0c;redis集成RedisSearch、redisJson 模块&#xff1b;spring boot 2.5在执行 redis 命令&#xff0c; 或者监控 程序执行的redis 指令时&#xff0c;可以采用 redisinsight查看&#xff0c;下载地址。 背景说明 需…...

【Kotlin精简】第8章 协程

1 简介 Kotlin 中的协程提供了一种全新处理并发的方式&#xff0c;您可以在 Android 平台上使用它来简化异步执行的代码。协程是从 Kotlin 1.3 版本开始引入&#xff0c;但这一概念在编程世界诞生的黎明之际就有了&#xff0c;最早使用协程的编程语言可以追溯到 1967 年的 Sim…...

【MATLAB源码-第79期】基于蚯蚓优化算法(EOA)的栅格路径规划,输出做短路径图和适应度曲线。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 蚯蚓优化算法&#xff08;Earthworm Optimisation Algorithm, EOA&#xff09;是一种启发式算法&#xff0c;灵感来源于蚯蚓在自然界中的行为模式。蚯蚓优化算法主要模仿了蚯蚓在寻找食物和逃避天敌时的行为策略。以下是蚯蚓…...

RPC实现简单解析

RPC是什么&#xff0c;先摘取一段解释&#xff1a; RPC全称为远程过程调用&#xff08;Remote Procedure Call&#xff09;&#xff0c;它是一种计算机通信协议&#xff0c;允许一个计算机程序调用另一个计算机上的子程序&#xff0c;而无需了解底层网络细节。通过RPC&#xff…...

【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr

【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr 文章目录 【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr1. 安装视频播放器vlc2. 安装录屏软件ssr 1. 安装视频播放器vlc sudo apt-get install vlcvlc是一款比较简洁的视频播放器&#xff0c;如下所示 2. 安…...

WMS仓储管理系统与TMS系统整合后的优势

随着全球化的加速和供应链网络的日益复杂&#xff0c;仓库和运输成为企业运营中的两个关键环节。为了更高效地管理这两个环节&#xff0c;许多企业开始探索将WMS仓储管理系统和TMS运输管理系统整合的可能性。这种整合不仅可以提升仓库流程的可见性&#xff0c;还有助于改善调度…...

测试的专用

测试...

sqli-labs(Less-4) extractvalue闯关

extractvalue() - Xpath类型函数 1. 确认注入点如何闭合的方式 2. 爆出当前数据库的库名 http://127.0.0.1/sqlilabs/Less-4/?id1") and extractvalue(1,concat(~,(select database()))) --3. 爆出当前数据库的表名 http://127.0.0.1/sqlilabs/Less-4/?id1") …...

Kafka简单汇总

Kafka的结构图 多个Parttion共同组成这个topic的所有消息。每个consumer都属于一个consumer group&#xff0c;每条消息只能被consumer group中的一个Consumer消费&#xff0c; 但可以被多个consumer group消费。即组间数据是共享的&#xff0c;组内数据是竞争的。二、消费模型…...

任务交给谁?委派模式告诉你最佳选择!

文章目录 一、概念二、角色三、代码实现四、委派模式在源码中的体现五、委派模式的优缺点优点缺点 一、概念 委派模式&#xff08;Delegate Pattern)又叫委托模式&#xff0c;是一种面向对象的设计模式。委派模式是一种行为模式&#xff0c;不属于GOF23种设计模式之中基本作用…...

【JavaEE】Servlet(创建Maven、引入依赖、创建目录、编写及打包、部署和验证、smart Tomcat)

一、什么是Servlet&#xff1f; Servlet 是一种实现动态页面的技术. 是一组 Tomcat 提供给程序猿的 API, 帮助程序猿简单高效的开发一个 web app 1.1 Servlet能干什么&#xff1f; &#x1f695;允许程序猿注册一个类, 在 Tomcat 收到某个特定的 HTTP 请求的时候, 执行这个类…...

降低城市内涝风险,万宾科技内涝积水监测仪的作用

频繁的内涝会削弱和损坏城市的关键基础设施&#xff0c;包括道路、桥梁和公用设施。城市内涝风险降低可以减少交通中断事件&#xff0c;也可以保护居民安全并降低路面维修等成本&#xff0c;进一步确保城市基本服务继续发挥作用。对城市可持续发展来讲有效减少内涝的风险是重要…...

别再只会用FFT了!用MATLAB的czt函数实现窄带信号高分辨率频谱分析

别再只会用FFT了&#xff01;用MATLAB的czt函数实现窄带信号高分辨率频谱分析 在信号处理领域&#xff0c;频谱分析是最基础也是最重要的技术之一。传统上&#xff0c;工程师们习惯使用快速傅里叶变换&#xff08;FFT&#xff09;来获取信号的频域信息。然而&#xff0c;当面对…...

用C#和ONNX Runtime搞定车牌识别:从模型部署到双层车牌分割的实战避坑

C#与ONNX Runtime实战&#xff1a;车牌识别系统开发全流程与双层车牌处理精要 车牌识别技术已经从实验室走向了各行各业&#xff0c;从停车场管理到交通执法&#xff0c;再到智慧城市建设&#xff0c;这项技术正在改变我们与车辆的交互方式。作为一名长期奋战在计算机视觉一线的…...

Win11Debloat:让Windows 11系统轻盈如飞的优化工具

Win11Debloat&#xff1a;让Windows 11系统轻盈如飞的优化工具 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutter and custo…...

4个步骤掌握Faze4机械臂开发:从硬件组装到智能控制的完整实践指南

4个步骤掌握Faze4机械臂开发&#xff1a;从硬件组装到智能控制的完整实践指南 【免费下载链接】Faze4-Robotic-arm All files for 6 axis robot arm with cycloidal gearboxes . 项目地址: https://gitcode.com/gh_mirrors/fa/Faze4-Robotic-arm Faze4开源六轴机械臂项目…...

linux https拦截与url解析

uprobe 拦截TLS库 用 eBPF uprobe 拦截 TLS 库&#xff08;OpenSSL/GnuTLS/Go TLS&#xff09;&#xff0c;在加密前 / 解密后捕获明文 HTTP 请求&#xff0c;即可解析出 HTTPS URL&#xff0c;无需 CA 证书、无需修改应用。 核心原理 HTTPS 明文&#xff08;含 URL&#xf…...

智慧园区能源管理系统解决方案

某园区集成生产、办公、生活三大功能&#xff0c;建设有生产厂房、化学品库、辅助用房、气罐站、研发楼、综合楼及其他配套设施&#xff0c;涉及到多种用能&#xff0c;包含电能、天然气、压缩空气、冷热能等&#xff0c;带来日益高昂的能耗成本与能源浪费隐患。 1、制冷空调监…...

信息系统项目管理师(高项)高效考证解决方案:一次通关的行动蓝图

一、 认知破局&#xff1a;理解考试本质与核心挑战信息系统项目管理师&#xff08;俗称“高项”&#xff09;是国家软考高级资格&#xff0c;它不仅是职称证书&#xff0c;更是项目投标的硬性门槛&#xff08;集成/软件企业申报资质、投标时项目经理资格必备&#xff09;。其核…...

PyTorch模型转ONNX避坑指南:从repeat_interleave到Concat类型匹配的实战解决方案

PyTorch模型转ONNX避坑指南&#xff1a;从动态张量到类型匹配的深度解决方案 在模型部署的最后一公里&#xff0c;PyTorch到ONNX的转换常常成为绊倒开发者的隐蔽陷阱。当你在本地训练环境获得完美指标后&#xff0c;准备将模型推向生产时&#xff0c;各种意想不到的导出错误可能…...

3个跨设备游戏自由:Sunshine如何用开源技术打造无缝串流体验

3个跨设备游戏自由&#xff1a;Sunshine如何用开源技术打造无缝串流体验 【免费下载链接】Sunshine Self-hosted game stream host for Moonlight. 项目地址: https://gitcode.com/GitHub_Trending/su/Sunshine 在数字娱乐多元化的今天&#xff0c;游戏玩家常面临高性能…...

Polars 2.0大规模清洗崩溃全解析:内存溢出、Schema冲突、LazyFrame中断——3类高频致命报错的5分钟修复方案

第一章&#xff1a;Polars 2.0大规模清洗崩溃全解析&#xff1a;内存溢出、Schema冲突、LazyFrame中断——3类高频致命报错的5分钟修复方案 当处理TB级结构化数据时&#xff0c;Polars 2.0的LazyFrame虽带来性能飞跃&#xff0c;却也因底层执行引擎变更放大了三类典型崩溃风险。…...