【C++动态规划 最长公共子序列】1035. 不相交的线|1805
本文涉及知识点
C++动态规划
LeetCode1035. 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足:
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。
以这种方法绘制线条,并返回可以绘制的最大连线数。
示例 1:
输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2:
输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3
示例 3:
输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2
提示:
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000
# 动态规划的状态
性质一:令连线(i,j)在nums1的下标是i,nums2的下标是j。则两条连线(i1,j1),(i2,j2),其中i1 < i2,则j1 < j2,否则会交叉。
性质二:我们将各线按i的升序排序排序,根据性质一,则j也是升序。
性质三:令某最优解是{KaTeX parse error: Undefined control sequence: \cdost at position 1: \̲c̲d̲o̲s̲t̲(i1,j1)、(i2,j2)、(i3,j3)KaTeX parse error: Undefined control sequence: \cdost at position 1: \̲c̲d̲o̲s̲t̲}。如果存在j1<j4<j2,则将j2换成j4也是最优解。
动态规划的状态表示
dp[i][j]表示,所有线的上端点下标 <= i,下端下标<=j,且最后一条连线的下端点下标是j。dp[i][j] = -n-1表示不存在的可能。下标从1开始。空间复杂度:O(nm)
动态规矩的转移方程+双指针
dp[i+1] = dp[i] 没有选择上端点i。
nums[j1] == nums[i] 且j1 > j 且j1最小,如果存在合法的j1,则j1 = m
MaxSelf(dp[i+1][j1+1] , dp[i][j]+1)
时间复杂度:O(nm)
动态规划的填表顺序
枚举前置状态
for(i = 0 To n-1) j = 0 To m-1
动态规划的初始化
dp[0][0]=0,其它全为-n-1
动态规划的返回值
max(dp.back())
代码
核心代码
class Solution {public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {const int N = nums1.size();const int M = nums2.size();vector<vector<int>> dp(N + 1, vector<int>(M + 1, -N-1));dp[0][0] = 0;for (int i = 0; i < N; i++) {dp[i + 1] = dp[i];for (int j = 0,j1=0; j < M; j++) {while ((j1 < M) && ((nums2[j1] != nums1[i]) || (j1 < j))) {j1++;}if (j1 >= M)continue;dp[i + 1][j1 + 1] = max(dp[i + 1][j1 + 1], dp[i][j] + 1);}}return *max_element(dp.back().begin(), dp.back().end());}};
单元测试
vector<int> nums1, nums2;TEST_METHOD(TestMethod1){nums1 = { 1, 4, 2 }, nums2 = { 1, 2, 4 };auto res = Solution().maxUncrossedLines(nums1, nums2);AssertEx(2, res);}TEST_METHOD(TestMethod12){nums1 = { 2, 5, 1, 2, 5 }, nums2 = { 10, 5, 2, 1, 5, 2 };auto res = Solution().maxUncrossedLines(nums1, nums2);AssertEx(3, res);}TEST_METHOD(TestMethod13){nums1 = { 1,3,7,1,7,5 }, nums2 = { 1,9,2,5,1 };auto res = Solution().maxUncrossedLines(nums1, nums2);AssertEx(2, res);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
相关文章:

【C++动态规划 最长公共子序列】1035. 不相交的线|1805
本文涉及知识点 C动态规划 LeetCode1035. 不相交的线 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足: nums1[i] nums2[j] 且绘制的…...

FFmpeg的基本结构
FFmpeg框架可以简单分为两层,上层是以ffmpeg、ffplay、ffprobe为代表的命令行工具;其底层支撑是一些基础库,包含AVFormat、AVCodec、AVFilter、AVDevices、AVUtils等模块库。 常用函数如下: 1. AVFormat 封装/解封装模块 avf…...
react 受控组件和非受控组件
在 React 中,受控组件和非受控组件是两种处理表单元素(如输入框、选择框等)值的方式。 1. 受控组件 受控组件是指 React 组件的表单元素的值是由 React 组件的 state 来管理的。换句话说,React 会全程控制表单元素的值ÿ…...
C语言模块化概述
一、函数名的意义 1.c语言是一门面向过程的语言:所谓的过程就是动词,动作。 功能块动词1动词2……动词 2.功能块:就是一堆动词(动作)的组合,动作通过函数来实现。 3.函数的功能:承上启下 承…...
WPF 中的视觉层和逻辑层有什么区别?
在 WPF(Windows Presentation Foundation)中,视觉层和逻辑层是两个不同的概念,它们分别涉及到界面的展示和应用的行为。要理解这两个层次的区别,我们需要从 WPF 的设计背景、架构以及它们之间的相互关系来全面分析。 …...
Kafka简单实践
使用 Apache Kafka 和 Swoole 的 PHP 实践案例 一、引言 Apache Kafka 是一个开源的分布式流处理平台,能够处理大量的实时数据流。由于其高吞吐量、可扩展性和持久性,Kafka 成为构建微服务架构和大数据处理的重要工具。Swoole 是一个高性能的异步网络通…...
JS
文章目录 项目地址一、JS1.1 if语句1.2 for循环1.2 三元表达式1.3 switch1.4 数组的push方法1.5 fuction1.5.1 arguments1.6 匿名函数1.7 预解析1.8 js对象1.8.1创建一个类1.8.2 遍历对象1.9 js的内置对象1.9.1 随机整数二、DOM2.1 获取元素2.2 事件基础2.2.1 事件三要素2.2.2 …...

【原创】java+ssm+mysql商品库存管理系统(进销存)设计与实现
个人主页:程序猿小小杨 个人简介:从事开发多年,Java、Php、Python、前端开发均有涉猎 博客内容:Java项目实战、项目演示、技术分享 文末有作者名片,希望和大家一起共同进步,你只管努力,剩下的交…...

three.js 杂记
欧拉角旋转变换 x,y,z 弧度单位 THREE.MathUtils.DEG2RAD 度数转弧度 new THREE.Euler( - 90 * THREE.MathUtils.DEG2RAD, 0, 0 ) radius:半径 setFromSphericalCoords ( radius : Float, phi : Float, theta : Float ) : this 从球坐标中的radius、phi和theta设置该向量…...

基于Hadoop、hive的数仓搭建实践
文章目录 架构图Hadoop搭建Hive 搭建MySQL搭建官网文档下载配置配置hive环境变量配置日志文件配置hive-site 复制mysql 驱动包删除日志包初始化元数据启动metastore服务使用hive CLI启动hiveServer2访问hiveserver2客户端连接beeline shell连接 Dbeaver连接经验 基于HDFS Hive…...

新的恶意软件活动通过游戏应用程序瞄准 Windows 用户
一种新的恶意软件 Winos4.0 被积极用于网络攻击活动。FortiGuard实验室发现,这种先进的恶意框架是从臭名昭著的 Gh0strat 演变而来的,配备了模块化组件,可在受感染的设备上进行一系列恶意活动。 这些攻击已在游戏相关应用程序中发现…...

【Hutool系列】反射工具-ReflectUtil
前言 反射是 Java 中一种强大的机制,可以在运行时动态地获取类的信息并操作类的属性和方法。在 Java 中,通过反射可以获取和设置类的字段、调用类的方法、创建类的实例等。Java的反射机制,可以让语言变得更加灵活,对对象的操作也更…...
【操作系统专业课】第二次作业
第1题(进程同步与互斥) 使用二值信号量实现 n 个进程之间的互斥。 1. 定义一个二值信号量 mutex= 1。 二值信号量:二值信号量只有两种取值,0 (资源已被占用)和 1(资源可用)。 2. 进程进入临界区前的操作:每个进程在进入临界区之前,都需要执行 P(mutex) 操作。 P 操作…...
Scala的迭代器
1.对比foreach 它的优点在于: (1) 内存效率高。迭代器采用延迟计算的方式,它不会将整个集合加载到内存中,而是在每次调用next方法时才计算并返回下一个元素。 (2) 统一的遍历方法。迭代器为不同类型的集合(如列表、集合、映射等…...

(RK3566驱动开发 - 1).pinctrl和gpio子系统
一.设备树 pinctrl部分可以参考 rockchip 官方的绑定文档 :kernel/Documentation/devicetree/bindings/pinctrl PIN_BANK:引脚所属的组 - 本次例程使用的是 GPIO3_A1 这个引脚,所以所属的组为 3; PIN_BANK_IDX:引脚的…...

css三角制作(二十课)
代码: <style>/* 边框原理 */.box1 {width: 0;height: 0;border-top: 100px solid pink;border-bottom: 100px solid blue;border-left: 100px solid yellow;border-right: 100px solid greenyellow;}/* 三角制作 */.box2 {width: 0;height: 0;border: 100px …...

C++_priority_queue(优先级队列)
✨✨ 欢迎大家来到小伞的大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:C学习 小伞的主页:xiaosan_blog 1. priority_queue的介绍和使用 priority_queue文档介绍 优先级队列的实现的关键…...

微信小程序——01开发前的准备和开发工具
文章目录 一、开发前的准备1注册小程序账号2安装开发者工具 二、开发者工具的使用1创建项目2 工具的使用3目录结构4各个页面之间的关系5 权限管理6提交审核和发布 一、开发前的准备 开发前需要进行以下准备: 1 注册小程序账号2激活邮箱3 信息登记4 登录小程序管理后…...
MySQL 的主从复制数据同步
一、什么是 MySQL 的主从复制 MySQL 的主从复制(Master-Slave Replication)是一种将数据从一个主数据库服务器(主库)复制到一个或多个从数据库服务器(从库)的技术。主库负责所有的数据写操作,从…...

python——面向对象
一、面向对象编程 1.1 面向过程与面向对象 面向过程和面向对象都是一种编程方式,只不过再设计上有区别。 1.1.1 面向过程pop: 举例:孩子上学 1. 妈妈起床 2. 妈妈洗漱 3. 妈妈做饭 4. 妈妈把孩子叫起来 5. 孩子起床 6. 孩子洗漱 7. 孩子吃…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...

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

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...