代码随想录算法训练营第五十七天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列
代码随想录算法训练营第五十七天
1143.最长公共子序列
题目链接:1143.最长公共子序列
- 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的text1,和以下标j - 1为结尾的text2,最长重复子数组长度为dp[i][j]
- 确定递推公式:
当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]); }
- dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
- 确定遍历顺序:从前向后遍历。
- 打印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.不相交的线
- 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的nums1,和以下标j - 1为结尾的nums2,最长重复子数组长度为dp[i][j]
- 确定递推公式:
当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]); }
- dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
- 确定遍历顺序:从前向后遍历。
- 打印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.判断子序列
- 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的t,和以下标j - 1为结尾的s,最长重复子数组长度为dp[i][j],当max_dp==s.size(),s就是t的子序列
- 确定递推公式:
当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]); }
- dp数组如何初始化:如果两个数组都没重复,最小值就是0,数组都初始化成0。
- 确定遍历顺序:从前向后遍历。
- 打印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.最长公共子序列 题目链接:1143.最长公共子序列 确定dp数组以及下标的含义:dp[i][j] :以下标i - 1为结尾的text1,和以下标j - 1为结尾的text2,最长重复子数组长度为dp[i][j]确…...

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

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

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

网站线上模板建设的优缺点
优点: 1.搭建的时间短,在线建站,只需要登录注册然后选择网站模板创建网站即可管理自己的网站后台,就几步操作就可以实现。 2.网站出错率少,因为有很多用户在使用,前期所报出来的问题就已经一一…...
哲学家进餐问题
1.最多允许四个哲学家同时进餐,保证有一个筷子是空闲的,从而保证能有有一个哲学家成功进餐,而不导致死锁 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融合应用
在新一轮互联网信息技术大发展的现今,无人机、大数据、人工智能、物联网等新兴技术在各行各业都处于大爆发的前夜。为了将人工智能方法引入农业生产领域。首先在种植、养护等生产作业环节,逐步摆脱人力依赖;在施肥灌溉环节构建智慧节能系统&a…...
联想测开一面(电话面试)笔试60%
联想测开一面(电话面试)笔试60% 3.21 无自我介绍 基本问项目,问实习 对python自动化测试了解多少 讲一下python中打包和解包的概念 学校无测试相关课程,平时用什么平台去学习的 计算机底层实现原理简要说说(软硬结合&…...

【python】tkinter GUI开发: Button和Entry的应用实战探索
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
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计算年化利率
接了业务需求需要计算年化利率, 公式定义: IRR计算 在计算 IRR 时,我们希望找到一个折现率r,使得净现值(NPV)为零。NPV 函数定义如下: NPV ∑ t 0 n C t ( 1 r ) t \text{NPV} \sum_{t0}…...
深入理解ChatGPT工作原理
在人工智能领域,自然语言处理(NLP)技术的飞速发展让机器能够更加自然和人类进行交流。OpenAI的ChatGPT作为当前最受关注的NLP模型之一,其出色的对话能力引起了业界和学术界的广泛关注。本文将深入探讨ChatGPT的工作原理࿰…...

在 Wed 中应用 MyBatis(同时使用MVC架构模式,以及ThreadLocal 事务控制)
1. 在 Wed 中应用 MyBatis(同时使用MVC架构模式,以及ThreadLocal 事务控制) 文章目录 1. 在 Wed 中应用 MyBatis(同时使用MVC架构模式,以及ThreadLocal 事务控制)2. 实现步骤:1. 第一步…...

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

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

ADS基础教程19 - 电磁仿真(EM)基本概念和实操
EM介绍 一、引言二、基本概念1.EM介绍2.Momentum介绍3.FEM介绍4.Substrate介绍 三、创建Layout并进行Momentum仿真1.创建Layout2.添加Microtrip(微带线)3.添加Substrate4.Momentum仿真 四、总结 一、引言 本章节开始介绍EM的基本概念、内容以及实现具体…...

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

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

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

如何将AndroidStudio和IDEA的包名改为分层级目录
新版UIAndroidStudio 1、点击项目目录右上角如图所示的三个点点。 2、然后依次取消Hide empty middle package ,Flatten package的勾选 3、注意:一定要先取消hide的勾选,不然目录不会完全分级(做错了可以反过来重新设置&#x…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...