代码随想录算法训练营第五十七天|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…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
