当前位置: 首页 > 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;进一步确保城市基本服务继续发挥作用。对城市可持续发展来讲有效减少内涝的风险是重要…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...