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

【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 中的整数。 现在&#xff0c;可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线&#xff0c;这些直线需要同时满足&#xff1a; nums1[i] nums2[j] 且绘制的…...

FFmpeg的基本结构

FFmpeg框架可以简单分为两层&#xff0c;上层是以ffmpeg、ffplay、ffprobe为代表的命令行工具&#xff1b;其底层支撑是一些基础库&#xff0c;包含AVFormat、AVCodec、AVFilter、AVDevices、AVUtils等模块库。 常用函数如下&#xff1a; 1. AVFormat 封装/解封装模块 avf…...

react 受控组件和非受控组件

在 React 中&#xff0c;受控组件和非受控组件是两种处理表单元素&#xff08;如输入框、选择框等&#xff09;值的方式。 1. 受控组件 受控组件是指 React 组件的表单元素的值是由 React 组件的 state 来管理的。换句话说&#xff0c;React 会全程控制表单元素的值&#xff…...

C语言模块化概述

一、函数名的意义 1.c语言是一门面向过程的语言&#xff1a;所谓的过程就是动词&#xff0c;动作。 功能块动词1动词2……动词 2.功能块&#xff1a;就是一堆动词&#xff08;动作&#xff09;的组合&#xff0c;动作通过函数来实现。 3.函数的功能&#xff1a;承上启下 承…...

WPF 中的视觉层和逻辑层有什么区别?

在 WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;视觉层和逻辑层是两个不同的概念&#xff0c;它们分别涉及到界面的展示和应用的行为。要理解这两个层次的区别&#xff0c;我们需要从 WPF 的设计背景、架构以及它们之间的相互关系来全面分析。 …...

Kafka简单实践

使用 Apache Kafka 和 Swoole 的 PHP 实践案例 一、引言 Apache Kafka 是一个开源的分布式流处理平台&#xff0c;能够处理大量的实时数据流。由于其高吞吐量、可扩展性和持久性&#xff0c;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商品库存管理系统(进销存)设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…...

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实验室发现&#xff0c;这种先进的恶意框架是从臭名昭著的 Gh0strat 演变而来的&#xff0c;配备了模块化组件&#xff0c;可在受感染的设备上进行一系列恶意活动。 这些攻击已在游戏相关应用程序中发现&#xf…...

【Hutool系列】反射工具-ReflectUtil

前言 反射是 Java 中一种强大的机制&#xff0c;可以在运行时动态地获取类的信息并操作类的属性和方法。在 Java 中&#xff0c;通过反射可以获取和设置类的字段、调用类的方法、创建类的实例等。Java的反射机制&#xff0c;可以让语言变得更加灵活&#xff0c;对对象的操作也更…...

【操作系统专业课】第二次作业

第1题(进程同步与互斥) 使用二值信号量实现 n 个进程之间的互斥。 1. 定义一个二值信号量 mutex= 1。 二值信号量:二值信号量只有两种取值,0 (资源已被占用)和 1(资源可用)。 2. 进程进入临界区前的操作:每个进程在进入临界区之前,都需要执行 P(mutex) 操作。 P 操作…...

Scala的迭代器

1.对比foreach 它的优点在于&#xff1a; (1) 内存效率高。迭代器采用延迟计算的方式&#xff0c;它不会将整个集合加载到内存中&#xff0c;而是在每次调用next方法时才计算并返回下一个元素。 (2) 统一的遍历方法。迭代器为不同类型的集合&#xff08;如列表、集合、映射等…...

(RK3566驱动开发 - 1).pinctrl和gpio子系统

一.设备树 pinctrl部分可以参考 rockchip 官方的绑定文档 &#xff1a;kernel/Documentation/devicetree/bindings/pinctrl PIN_BANK&#xff1a;引脚所属的组 - 本次例程使用的是 GPIO3_A1 这个引脚&#xff0c;所以所属的组为 3&#xff1b; PIN_BANK_IDX&#xff1a;引脚的…...

css三角制作(二十课)

代码&#xff1a; <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(优先级队列)

✨✨ 欢迎大家来到小伞的大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 小伞的主页&#xff1a;xiaosan_blog 1. priority_queue的介绍和使用 priority_queue文档介绍 优先级队列的实现的关键…...

微信小程序——01开发前的准备和开发工具

文章目录 一、开发前的准备1注册小程序账号2安装开发者工具 二、开发者工具的使用1创建项目2 工具的使用3目录结构4各个页面之间的关系5 权限管理6提交审核和发布 一、开发前的准备 开发前需要进行以下准备&#xff1a; 1 注册小程序账号2激活邮箱3 信息登记4 登录小程序管理后…...

MySQL 的主从复制数据同步

一、什么是 MySQL 的主从复制 MySQL 的主从复制&#xff08;Master-Slave Replication&#xff09;是一种将数据从一个主数据库服务器&#xff08;主库&#xff09;复制到一个或多个从数据库服务器&#xff08;从库&#xff09;的技术。主库负责所有的数据写操作&#xff0c;从…...

python——面向对象

一、面向对象编程 1.1 面向过程与面向对象 面向过程和面向对象都是一种编程方式&#xff0c;只不过再设计上有区别。 1.1.1 面向过程pop&#xff1a; 举例&#xff1a;孩子上学 1. 妈妈起床 2. 妈妈洗漱 3. 妈妈做饭 4. 妈妈把孩子叫起来 5. 孩子起床 6. 孩子洗漱 7. 孩子吃…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...