代码随想录算法训练营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 输入的字符串只含有小写英文字符。
思路
-
定义状态:创建一个二维数组
dp,其中dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。 -
状态转移:
- 如果
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])。
- 如果
-
初始化:
dp[0][j]和dp[i][0]都应初始化为 0,因为空字符串与任何字符串的最长公共子序列长度都是 0。 -
填充表格:按行或按列填充整个
dp表格。 -
返回结果:
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],且我们绘制的直线不与任何其他连线(非水平线)相交。
以这种方法绘制线条,并返回我们可以绘制的最大连线数。

思路
-
定义状态:创建一个二维数组
dp,其中dp[i][j]表示数组A的前i个元素和数组B的前j个元素可以形成的最大连线数。 -
状态转移:
- 如果
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])。
- 如果
-
初始化:
dp[0][j]和dp[i][0]都应初始化为 0,因为当任一数组为空时,最大连线数为 0。 -
填充表格:按行或按列顺序填充
dp表格。 -
返回结果:
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。
思路
-
定义状态:创建一个数组
dp,其中dp[i]表示以nums[i]结尾的最大子序和。 -
状态转移:对于每个
i,有两种情况:- 把
nums[i]加入前面的子数组中,这种情况下最大子序和是dp[i-1] + nums[i]; - 从
nums[i]开始一个新的子数组,这种情况下最大子序和是nums[i]自己。 因此,dp[i] = max(dp[i-1] + nums[i], nums[i])。
- 把
-
初始化:
dp[0]应该初始化为nums[0],因为最开始的最大子序和就是数组的第一个元素。 -
结果:遍历
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,返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何…...
Oracle JDBC数据库驱动程序介绍
Maven Central上所有Oracle JDBC数据库驱动程序 现在不仅可以在Maven Central上使用甲骨文数据库最新版本,而且还可以获得所有受支持的Oracle JDBC驱动程序发行版,包括19.3.0.0、18.3.0.0、12.2.0.1和11.2.0.4。从现在开始,Maven Central确实…...
scipy实现单因素方差分析
经典例题 某校高二年级共有四个班,采用四种不同的教学方法进行数学教学,为了比较这四种教学法的效果是否存在明显的差异,期末统考后,从这四个班中各抽取 5 名考生的成绩,如下所示。 班级 一班 二班 三班 四班 …...
深度学习实战59-NLP最核心的模型:transformer的搭建与训练过程详解,手把手搭建与跑通
大家好,我是微学AI,今天给大家介绍一下深度学习实战59-NLP最核心的模型:transformer的搭建与训练过程详解,手把手搭建与跑通。transformer是一种基于自注意力机制的深度学习模型,由Vaswani等人在2017年的论文《Attention is All You Need》中提出。它最初被设计用来处理序…...
一阶滤波器(一阶巴特沃斯滤波器)
连续传递函数G(s) 离散传递函数G(z) 转换为差分方程形式 一阶巴特沃斯滤波器Filter Designer参数设计:参考之前的博客Matlab的Filter Designer工具设计二阶低通滤波器 设计采样频率100Hz,截止频率20Hz。 注意:设计参数使用在离散系统中&…...
.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系统的场景,以下是一个简单的系统架构示例,包括前端、后端和数据库三个基本部分: 前端: 使用React框架进行前端开发,构建用户界面和交互逻辑。前端模块包括日程管理模块、文档管…...
spring boot 集成 RedisSearch 和 RedisJSON
1. 准备工作 环境说明 java 8;redis7.2.2,redis集成RedisSearch、redisJson 模块;spring boot 2.5在执行 redis 命令, 或者监控 程序执行的redis 指令时,可以采用 redisinsight查看,下载地址。 背景说明 需…...
【Kotlin精简】第8章 协程
1 简介 Kotlin 中的协程提供了一种全新处理并发的方式,您可以在 Android 平台上使用它来简化异步执行的代码。协程是从 Kotlin 1.3 版本开始引入,但这一概念在编程世界诞生的黎明之际就有了,最早使用协程的编程语言可以追溯到 1967 年的 Sim…...
【MATLAB源码-第79期】基于蚯蚓优化算法(EOA)的栅格路径规划,输出做短路径图和适应度曲线。
操作环境: MATLAB 2022a 1、算法描述 蚯蚓优化算法(Earthworm Optimisation Algorithm, EOA)是一种启发式算法,灵感来源于蚯蚓在自然界中的行为模式。蚯蚓优化算法主要模仿了蚯蚓在寻找食物和逃避天敌时的行为策略。以下是蚯蚓…...
RPC实现简单解析
RPC是什么,先摘取一段解释: RPC全称为远程过程调用(Remote Procedure Call),它是一种计算机通信协议,允许一个计算机程序调用另一个计算机上的子程序,而无需了解底层网络细节。通过RPCÿ…...
【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr
【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr 文章目录 【Ubuntu】Ubuntu20.04下安装视频播放器vlc和录屏软件ssr1. 安装视频播放器vlc2. 安装录屏软件ssr 1. 安装视频播放器vlc sudo apt-get install vlcvlc是一款比较简洁的视频播放器,如下所示 2. 安…...
WMS仓储管理系统与TMS系统整合后的优势
随着全球化的加速和供应链网络的日益复杂,仓库和运输成为企业运营中的两个关键环节。为了更高效地管理这两个环节,许多企业开始探索将WMS仓储管理系统和TMS运输管理系统整合的可能性。这种整合不仅可以提升仓库流程的可见性,还有助于改善调度…...
测试的专用
测试...
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,每条消息只能被consumer group中的一个Consumer消费, 但可以被多个consumer group消费。即组间数据是共享的,组内数据是竞争的。二、消费模型…...
任务交给谁?委派模式告诉你最佳选择!
文章目录 一、概念二、角色三、代码实现四、委派模式在源码中的体现五、委派模式的优缺点优点缺点 一、概念 委派模式(Delegate Pattern)又叫委托模式,是一种面向对象的设计模式。委派模式是一种行为模式,不属于GOF23种设计模式之中基本作用…...
【JavaEE】Servlet(创建Maven、引入依赖、创建目录、编写及打包、部署和验证、smart Tomcat)
一、什么是Servlet? Servlet 是一种实现动态页面的技术. 是一组 Tomcat 提供给程序猿的 API, 帮助程序猿简单高效的开发一个 web app 1.1 Servlet能干什么? 🚕允许程序猿注册一个类, 在 Tomcat 收到某个特定的 HTTP 请求的时候, 执行这个类…...
降低城市内涝风险,万宾科技内涝积水监测仪的作用
频繁的内涝会削弱和损坏城市的关键基础设施,包括道路、桥梁和公用设施。城市内涝风险降低可以减少交通中断事件,也可以保护居民安全并降低路面维修等成本,进一步确保城市基本服务继续发挥作用。对城市可持续发展来讲有效减少内涝的风险是重要…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
