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

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

代码随想录算法训练营第五十七天

1143.最长公共子序列

题目链接:1143.最长公共子序列

  1. 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的text1,和以下标j - 1为结尾的text2,最长重复子数组长度为dp[i][j]
  2. 确定递推公式:
    当text1[i - 1] 和text2[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
    那就看看text1[i - 2]与text2[j - 1]的最长公共子序列 和 text1[ i - 1]与text2[j - 2]的最长公共子序列,取最大的。dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
    }else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
    
  3. dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
  4. 确定遍历顺序:从前向后遍历。
  5. 打印dp数组。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1, 0));int max_dp = 0;for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}max_dp = max(max_dp,dp[i][j]);}}return max_dp;}
};

1035.不相交的线

题目链接:1035.不相交的线

  1. 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的nums1,和以下标j - 1为结尾的nums2,最长重复子数组长度为dp[i][j]
  2. 确定递推公式:
    当nums1[i - 1] 和nums2[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
    那就看看nums1[i - 2]与nums2[j - 1]的最长公共子序列 和 nums1[ i - 1]与nums2[j - 2]的最长公共子序列,取最大的。dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
    }else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
    
  3. dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
  4. 确定遍历顺序:从前向后遍历。
  5. 打印dp数组。
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1,vector<int>(nums2.size() + 1, 0));int max_dp = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}max_dp = max(max_dp,dp[i][j]);}}return max_dp;}
};

53. 最大子序和

题目链接:53. 最大子序和

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int>dp(nums.size(),0);int dp_max = INT_MIN;dp[0]=nums[0];for(int i = 1;i<nums.size();i++){dp[i] = max(nums[i],dp[i-1]+nums[i]);dp_max = max(dp[i],dp_max);}return max(dp[0],dp_max);}
};

392.判断子序列

题目链接:392.判断子序列

  1. 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的t,和以下标j - 1为结尾的s,最长重复子数组长度为dp[i][j],当max_dp==s.size(),s就是t的子序列
  2. 确定递推公式:
    当t[i - 1] 和s[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
    那就看看t[i - 2]与s[j - 1]的最长公共子序列 和 t[ i - 1]与s[j - 2]的最长公共子序列,取最大的。dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    if (t[i - 1] == s[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
    }else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
    
  3. dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
  4. 确定遍历顺序:从前向后遍历。
  5. 打印dp数组。
class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1,vector<int>(t.size() + 1, 0));int max_dp = 0;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}max_dp = max(max_dp,dp[i][j]);}}return max_dp == s.size();}
};

相关文章:

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

代码随想录算法训练营第五十七天 1143.最长公共子序列 题目链接&#xff1a;1143.最长公共子序列 确定dp数组以及下标的含义&#xff1a;dp[i][j] &#xff1a;以下标i - 1为结尾的text1&#xff0c;和以下标j - 1为结尾的text2&#xff0c;最长重复子数组长度为dp[i][j]确…...

RocketMQ事务性消息

RocketMQ事务性消息是一定能保证消息发送成功的 事务消息发送步骤&#xff1a; &#xff08;1&#xff09;发送方将半事务消息发送至RocketMQ服务端。 &#xff08;2&#xff09;RocketMQ服务端将消息持久化之后&#xff0c;向发送方返回ack确认消息已经发送成功。由于消息为…...

mysql (事物)

一.什么是事物 事物是一组操作的集合&#xff0c;不可分割的工作单位&#xff0c;事物会把所有的操作当作一个整体一起向系统提交或撤销操作请求&#xff0c;就是这些操作要么一起成功要么一起失败。 二.事物操作 &#xff08;这个就是一个理解&#xff09; 1.事务特性 原子性…...

kotlin 中的字符串

一、字符类访问 1、字符串的访问跟js一样&#xff0c;可以使用索引来访问或者直接循环。 fun main() {val a: String "2024"// 方式一&#xff1a;for (item in a) {println(item) // 输出每一个字符}// 方式二&#xff1a;println("${a[0]}, ${a[1]}, ${a[2…...

网站线上模板建设的优缺点

优点&#xff1a; 1.搭建的时间短&#xff0c;在线建站&#xff0c;只需要登录注册然后选择网站模板创建网站即可管理自己的网站后台&#xff0c;就几步操作就可以实现。 2.网站出错率少&#xff0c;因为有很多用户在使用&#xff0c;前期所报出来的问题就已经一一…...

哲学家进餐问题

1.最多允许四个哲学家同时进餐&#xff0c;保证有一个筷子是空闲的&#xff0c;从而保证能有有一个哲学家成功进餐&#xff0c;而不导致死锁 semaphore chopstick[5] {1, 1, 1, 1, 1}, mutex4; Pi(){do{think...P(mutex);P(chopstick[i]);P(chopstick[(i1)%5);eat...V(mutex)…...

无人机遥感在农林信息提取中的实现方法与GIS融合应用

在新一轮互联网信息技术大发展的现今&#xff0c;无人机、大数据、人工智能、物联网等新兴技术在各行各业都处于大爆发的前夜。为了将人工智能方法引入农业生产领域。首先在种植、养护等生产作业环节&#xff0c;逐步摆脱人力依赖&#xff1b;在施肥灌溉环节构建智慧节能系统&a…...

联想测开一面(电话面试)笔试60%

联想测开一面&#xff08;电话面试&#xff09;笔试60% 3.21 无自我介绍 基本问项目&#xff0c;问实习 对python自动化测试了解多少 讲一下python中打包和解包的概念 学校无测试相关课程&#xff0c;平时用什么平台去学习的 计算机底层实现原理简要说说&#xff08;软硬结合&…...

【python】tkinter GUI开发: Button和Entry的应用实战探索

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

sm2证书生成(openssl3.0)

1、下载安装包 https://www.openssl.org/source/openssl-3.0.14.tar.gz 2、解压到指定位置 /appserver/openssl-3.0.14 3、安装依赖包 yum -y install gcc perl make zlib-devel perl-CPAN 4、编译 ./config shared --prefix/appserver/SM make depend make make install 5…...

java计算年化利率

接了业务需求需要计算年化利率&#xff0c; 公式定义&#xff1a; IRR计算 在计算 IRR 时&#xff0c;我们希望找到一个折现率r&#xff0c;使得净现值&#xff08;NPV&#xff09;为零。NPV 函数定义如下&#xff1a; NPV ∑ t 0 n C t ( 1 r ) t \text{NPV} \sum_{t0}…...

深入理解ChatGPT工作原理

在人工智能领域&#xff0c;自然语言处理&#xff08;NLP&#xff09;技术的飞速发展让机器能够更加自然和人类进行交流。OpenAI的ChatGPT作为当前最受关注的NLP模型之一&#xff0c;其出色的对话能力引起了业界和学术界的广泛关注。本文将深入探讨ChatGPT的工作原理&#xff0…...

在 Wed 中应用 MyBatis(同时使用MVC架构模式,以及ThreadLocal 事务控制)

1. 在 Wed 中应用 MyBatis&#xff08;同时使用MVC架构模式&#xff0c;以及ThreadLocal 事务控制&#xff09; 文章目录 1. 在 Wed 中应用 MyBatis&#xff08;同时使用MVC架构模式&#xff0c;以及ThreadLocal 事务控制&#xff09;2. 实现步骤&#xff1a;1. 第一步&#xf…...

Elasticsearch index 设置 false,为什么还可以被检索到?

在 Elasticsearch 中&#xff0c;mapping 定义了索引中的字段类型及其处理方式。 近期有球友提问&#xff0c;为什么设置了 index: false 的字段仍能被检索。 本文将详细探讨这个问题&#xff0c;并引入列式存储的概念&#xff0c;帮助大家更好地理解 Elasticsearch 的存储和查…...

169. 多数元素

题目 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3]输出&#xff1a;3 …...

ADS基础教程19 - 电磁仿真(EM)基本概念和实操

EM介绍 一、引言二、基本概念1.EM介绍2.Momentum介绍3.FEM介绍4.Substrate介绍 三、创建Layout并进行Momentum仿真1.创建Layout2.添加Microtrip&#xff08;微带线&#xff09;3.添加Substrate4.Momentum仿真 四、总结 一、引言 本章节开始介绍EM的基本概念、内容以及实现具体…...

LabVIEW RT环境中因字符串拼接导致的系统崩溃问题

在LabVIEW实时操作系统&#xff08;RT&#xff09;环境中运行的应用程序出现字符串拼接后死机的问题&#xff0c;通常涉及内存管理、内存泄漏或其他资源管理问题。以下是一些指导和步骤&#xff0c;帮助解决这个问题&#xff1a; 1. 内存泄漏检测 字符串拼接会在内存中创建新…...

深层网络:层数多真的更好吗?

深层网络&#xff1a;层数多真的更好吗&#xff1f; 在深度学习的世界里&#xff0c;"深度"始终是一个热门话题。随着技术的发展&#xff0c;我们有了越来越多的方法来构建更深的神经网络&#xff0c;这似乎暗示着“层数越多&#xff0c;效果越好”。然而&#xff0…...

【QT5】<知识点> QT常用知识(更新中)

目录 一、更改文本颜色和格式 二、QT容器类 三、字符串与整数、浮点数之间的转换 四、QString常用功能 五、SpinBox的属性介绍 六、滑动、滚动、进度条和表盘LCD 七、时间、日期、定时器 一、更改文本颜色和格式 动态设置字体粗体&#xff1a;QFont对象的setBold方法动态…...

如何将AndroidStudio和IDEA的包名改为分层级目录

新版UIAndroidStudio 1、点击项目目录右上角如图所示的三个点点。 2、然后依次取消Hide empty middle package &#xff0c;Flatten package的勾选 3、注意&#xff1a;一定要先取消hide的勾选&#xff0c;不然目录不会完全分级&#xff08;做错了可以反过来重新设置&#x…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

(二)原型模式

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

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...