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

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

最长公共子序列

1143. 最长公共子序列 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili

本题和上一题718.最长重复子数组在很多方面相似,区别在与不需要连续,因此在dp数组的推导上有些改变。

由于不需要连续,dp[i][j]的值针对text1和text2相同及不同这两种情况有不同的表示。

首先 dp[i][j]表示序列text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度

当text[i-1] == text[j-1]时,dp[i][j] = dp[i-1][j-1]+1,而当text1[i-1]!=text2[j-1]时,dp[i][j] = max(dp[i-1][j],dp[i][j-1]),dp[i][j]由数组左和上的较大值确定。

由此,dp[i][j]由左上部分确认,当i j为0时,表示的序列为空,空序列与任何序列的最长公共子序列均为空,长度为0,dp[0][0]、dp[0][1]、dp[1][0]都为0。

i,j两个变量循环遍历。

最后返回dp[text1.size()][text2.size()]。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度// 初始化 dp 的大小为 (text1.size()+1) x (text2.size()+1),值全部为 0vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));// 双层循环遍历 text1 和 text2for (int i = 1; i <= text1.size(); i++) {  // i 从 1 开始,直到 text1.size()for (int j = 1; j <= text2.size(); j++) {  // j 从 1 开始,直到 text2.size()// 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同if (text1[i - 1] == text2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前字符不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[text1.size()][text2.size()],即 text1 和 text2 的 LCS 长度return dp[text1.size()][text2.size()];}

算法的时间复杂度为O(m*n),空间复杂度为O(m*n),m和n分别代表两个序列的长度,二维数组,二维循环遍历。

不相交的线

1035. 不相交的线 - 力扣(LeetCode)

和上题一致,换些变量便能解决,不过真要面试的时候,希望能想到吧。

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的最长公共子序列的长度// 初始化 dp 的大小为 (nums1.size()+1) x (nums2.size()+1),值全部为 0vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));// 双层循环遍历 nums1 和 nums2for (int i = 1; i <= nums1.size(); i++) {  // i 从 1 开始,直到 nums1.size()for (int j = 1; j <= nums2.size(); j++) {  // j 从 1 开始,直到 nums2.size()// 如果 nums1 的第 i 个元素和 nums2 的第 j 个元素相同if (nums1[i - 1] == nums2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前元素不包含在 LCS 中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[nums1.size()][nums2.size()],即 nums1 和 nums2 的 LCS 长度// 这也是不相交的直线段的最大数量return dp[nums1.size()][nums2.size()];}

算法的时间复杂度为O(m*n),空间复杂度为O(m*n)。

最大子序和

53. 最大子数组和 - 力扣(LeetCode)

之前用过贪心算法解这道题,当子序和为负,则抛弃当前子序和,从下一个位置开始计算子序和。这里使用动态规划也是类似的。

由于是连续的子序和,dp[i]表示到i为止的最大子序和(此处应包含nums[i])

dp[i] = max(dp[i-1]+nums[i],nums[i]),这里可以想象贪心的思路,当dp[i-1]为负时,自然dp[i-1]+nums[i]要小于nums[i]。

因此,唯一需要的是当前元素的前一位的dp值,dp[0] = nums[0]。

从前往后遍历

最后返回dp数组中的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 创建一个向量 dp,用于存储以第 i 个元素结尾的最大子数组和// 初始化 dp 的大小与 nums 相同,值全部为 0vector<int> dp(nums.size(), 0);// dp[0] 是数组第一个元素的值,因为一个元素的子数组和就是它本身dp[0] = nums[0];// 遍历数组 nums,从第二个元素开始for (int i = 1; i < nums.size(); i++) {// 如果以第 i-1 个元素结尾的最大子数组和小于 0if (dp[i - 1] < 0) {// 则以第 i 个元素结尾的最大子数组和就是第 i 个元素的值// 因为加上前面的子数组和会使得和更小dp[i] = nums[i];} else {// 如果以第 i-1 个元素结尾的最大子数组和大于等于 0// 则将第 i 个元素的值加到以第 i-1 个元素结尾的最大子数组和上// 这样可以保持子数组的连续性dp[i] = dp[i - 1] + nums[i];}}// 使用 STL 中的 max_element 函数找出 dp 中的最大值// 这个最大值就是整个数组的最大子数组和return *max_element(dp.begin(), dp.end());}
};

算法的时间复杂度为O(n),空间复杂度为O(n)。

判断子序列

392. 判断子序列 - 力扣(LeetCode)

同样和最长公共子序列相似,在遍历过程中,当dp[i][j] == s.size()时,表示s为t的子序列,否则s不是t的子序列,具体代码如下。

class Solution {
public:// 定义一个成员函数,用于判断 s 是否为 t 的子序列bool isSubsequence(string s, string t) {// 如果 s 为空字符串,那么它是任何字符串的子序列if (s.size() == 0) {return true;}// 创建一个二维向量 dp,用于存储动态规划的状态值// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的匹配长度vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));// 双层循环遍历 s 和 tfor (int i = 1; i <= s.size(); i++) {  // i 从 1 开始,直到 s.size()for (int j = 1; j <= t.size(); j++) {  // j 从 1 开始,直到 t.size()// 如果 s 的第 i 个字符和 t 的第 j 个字符相同if (s[i - 1] == t[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] = dp[i - 1][j - 1] + 1;// 如果匹配长度等于 s 的长度,说明 s 是 t 的子序列if (dp[i][j] == s.size()) {return true;}} else {// 如果不相同,则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这表示当前字符不包含在子序列中dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 如果遍历完 dp 数组后没有找到匹配长度等于 s 长度的状态,则 s 不是 t 的子序列return false;}
};

算法的时间复杂度为O(m*n),空间复杂度为O(m*n)。

相关文章:

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

最长公共子序列 1143. 最长公共子序列 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili 本题和上一题718.最长重复子数组在很多方面相似&#xf…...

国家自然科学基金标书大全(2002-2024)

数据来源&#xff1a;在20世纪80年代初&#xff0c;为了促进中国的科技体制革新并改革科研资金分配机制&#xff0c;中国科学院的89位院士联名向党和国家领导人提出建议&#xff0c;设立了国家自然科学基金的设立。国自然基金自创立以来&#xff0c;根据国家发展科学技术方针、…...

Python代码打包成exe应用

目录 一、前期准备 二、Pyinstaller打包步骤 Pyinstaller参数详解 三、测试 Spec 文件相关命令 一、前期准备 &#xff08;1&#xff09;首先&#xff0c;我们需要确保你的代码可以在本地电脑上的pycharm正常运行成功。 &#xff08;2&#xff09;我们要先安装Pyinstalle…...

CesiumJS【Basic】- #016 多边形面渲染“花了”的问题

文章目录 多边形面渲染“花了”的问题1 目标2 问题代码3 修正后代码4 总结多边形面渲染“花了”的问题 1 目标 解决多边形的面“花了”的问题 2 问题代码 使用Cesium.PerInstanceColorAppearance渲染后出现色斑 import * as Cesium from "cesium";const viewer …...

qt 开发对信号槽进行二次封装,实现信号槽管理接口。

最近做的一个项目,由于工程需要模块之间能够互相通信,但又不想模块之间耦合度太高 使用信号槽的话,需要两个类的对象或者指针在其中一个类都要体现,这样达不到效果, 想要一个管理类对这些互相通信的类之间进行管理,只需要在各自的类注册发送者和接收者即可,双方通过一…...

本地项目上传到gitee

本地项目通过webstorm上传到gitee 1.登录gitee选择新建仓库 2.输入新建仓库的名字&#xff08;名字与本地项目名一致&#xff09; 3.复制链接 4.找到本地项目&#xff0c;选中地址输入cmd打开命令提示框 5.输入git init初始化git&#xff0c;生成.git文件 6.webstorm中打开项目…...

ONLYOFFICE 8.1版本桌面编辑器测评:超越想象的办公体验!

在当今数字化办公时代&#xff0c;一个功能强大、操作便捷的办公套件对于提高工作效率至关重要。ONLYOFFICE 8.1作为一款备受瞩目的办公软件&#xff0c;凭借其全面的功能、优异的性能和出色的用户体验&#xff0c;为用户带来了超越想象的办公体验。下面&#xff0c;我们将对ON…...

中介子方程三十四

XXFXXuXXWXXuXXdXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXdXXuXWXπXXWXeXyXeXbXπXpXXNXXqXeXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXeXqXXNXXpXπXbXeXyXeXWXXπXWXuXXdXXrXXαXXuXpXXKXηXiXXαXXiXηXKXXpXuXXαXXrXXdXXuXXWXXuXXFXXEXXyXXEXXrXXαXXuXpXXK…...

最新Sublime Text软件安装包分享(汉化版本)

Sublime Text 是一款广受欢迎的跨平台文本编辑器&#xff0c;专为代码、标记和散文编辑而设计。它以其简洁的用户界面、强大的功能和高性能而著称&#xff0c;深受开发者和写作者的喜爱。 一、下载地址 链接&#xff1a;https://pan.baidu.com/s/1kErSkvc7WnML7fljQZlcOg?pwdk…...

AI-智能体基础设施

个性化记忆需要世界模型来协助构建 业界有一个精简的Agent表达公示&#xff0c;即&#xff1a;Agent大模型&#xff08;LLM&#xff09;记忆&#xff08;Memory&#xff09;主动规划&#xff08;Planning&#xff09;工具使用&#xff08;Tool Use&#xff09;。基于该公式&am…...

【docker】docker启动neo4j,并配置内存

注意下&#xff1a;--volume宿主机目录:/data 和 --publish宿主机port:7474 --publish宿主机port:7687 docker run -d \ --publish9801:7474 --publish9802:7687 \ --env NEO4J_AUTHneo4j/passwd \ --volume/opt/docker/data/vol-data/neo4j4.2:/data \ --restart always \ --…...

面试准备记录

6月26日 今日学习 MySQL的1-7题&#xff08;中期报告&#xff0c;加上玩了游戏&#xff0c;就没有认真背题&#xff09; 6月25日 今日复习 JVM的内存管理部分&#xff08;1-31题&#xff09; 6月24日 今日学习 类的生命周期&#xff1f;类加载过程&#xff1f;类加载器有…...

文件管理—linux(基础IO)

目录 ​编辑 一、C语言文件接口&#xff08;库函数&#xff09; hello.c写文件 hello.c读文件 输出信息到显示器 stdin & stdout & stderr 二、系统文件I/O&#xff08;系统调用&#xff09; hello.c 写文件&#xff1a; hello.c读文件 接口介绍 open open…...

【华为OD机试|01】最远足迹(Java/C/Py/JS)

目录 一、题目介绍 1.1 题目描述 1.2 备注&#xff1a; 1.3 输入描述 1.4 输出描述 1.5 用例 二、Java代码实现 2.1 实现思路 2.2 详细代码 2.3 代码讲解&#xff1a; 三、C语言实现 3.1实现步骤 3.2 实现代码 3.3 代码详解 四、Python实现 4.1 实现步骤 4.2 …...

conda安装管理配置

原文链接&#xff1a;conda管理配置 导言 安装卸载 卸载 卸载 docker sudo rm -r /opt/anaconda3 #conda安装位置安装 从镜像archive中下载sh脚本安装 bash ./software/Anaconda3-2024.02-1-Linux-x86_64.sh -b -p /opt/anaconda3 #conda安装位置管理 查看 conda --ver…...

鸿蒙开发HarmonyOS NEXT(一)

最近总听见大家讨论鸿蒙&#xff0c;前端转型的好方向&#xff1f;先入门学习下 目前官方版本和文档持续更新中 一、开发环境 提示&#xff1a;要占用的空间比较多&#xff0c;建议安装在剩余空间多的盘 1、下载&#xff1a;官网最新工具 - 下载中心 - 华为开发者联盟 (huaw…...

新能源革命风起云涌:创新科技引领可持续发展新篇章

随着全球气候变化和环境问题日益严峻&#xff0c;新能源革命正以其不可阻挡的势头&#xff0c;席卷着世界的每一个角落。 创新科技在这场革命中发挥着至关重要的作用&#xff0c;它不仅是新能源开发利用的引擎&#xff0c;更是推动可持续发展的关键力量。 新能源革命的核心在于…...

Java之TimeUnit类

1.TimeUnit类介绍 TimeUnit&#xff08;时间单元&#xff09;是一个描述时间单元的枚举类&#xff0c;在该枚举类中定义有以下的几个时间单元实例&#xff1a;天&#xff08;DAYS&#xff09;、时&#xff08;HOURS&#xff09;、分&#xff08;MINUTES&#xff09;、秒&#…...

【大数据】大数据时代的黎明

目录 前言 深入解读大数据的本质 大数据的起源与演进轨迹 大数据对社会经济的深远影响 经济领域的革新 社会治理与公共服务的智能化 创新体系的重构 面临的挑战与应对 前言 步入21世纪以来&#xff0c;人类文明正站在一个历史性的转折点上&#xff0c;迎来了大数据时代的…...

多接口分线盒在工业自动化中的重要性与应用

简介 多接口分线盒是现代工业自动化中不可或缺的一个组成部分&#xff0c;它主要用于简化复杂的接线系统&#xff0c;提高效率和可靠性。本文将详细探讨多接口分线盒的定义、功能、以及在工业自动化中的应用情况。 无源多接口分线盒 多接口分线盒的定义与功能 多接口分线盒是…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...