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

【LeetCode】646. 最长数对链

646. 最长数对链(中等)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路

这道题和 300. 最长递增子序列 类似,我们可以定义 dp 数组,其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后,统计一遍各个位置的结果即可得到题目要求的结果。

但是题目中强调了 “任何顺序选择其中的一些数对来构造”,因此我们可以先按照 righti 对数对进行升序排序,这样能够快速判断相邻数对是否构成数对链。

状态定义

对于这道题,我们可以定义 dp[i] 为以 i 结尾的最长数对链的长度

状态转移方程

对于每个位置 i ,如果其之前的位置 j 所对应的数对和位置 i 的数对可以构成数对链,那么我们就可以获得一个以 pairs[i] 结尾、长度为 dp[j] + 1 的更长的数对链。

初始化

对于pairs[0] ,它可以自己形成长度为 1 的数对链,所以 dp[0] = 1;

最终的返回结果

由于 dp[i] 存储的是以 i 结尾的最长数对链的长度,而整个数对中最长数对链可能以任意其中一个元素作为结尾,所以需要遍历 dp 数组,得到最长的数对链。

*max_element(dp.begin(), dp.end());

代码

class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b){return a[1] < b[1];}int findLongestChain(vector<vector<int>>& pairs) {int n = pairs.size();vector<int> dp(n, 0);sort(pairs.begin(), pairs.end(), cmp);// 初始化dp[0] = 1;// 状态转移方程for(int i=1; i<n; ++i){for(int j=0; j<=i; ++j){if(pairs[i][0] > pairs[j][1]){dp[i] = max(dp[i], dp[j] + 1);}else dp[i] = max(dp[i] , 1);}}return *max_element(dp.begin(), dp.end());}
};

相关文章:

【LeetCode】646. 最长数对链

646. 最长数对链&#xff08;中等&#xff09; 思路 这道题和 300. 最长递增子序列 类似&#xff0c;我们可以定义 dp 数组&#xff0c;其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后&#xff0c;统计一遍各个位置的结果即可得到题目要求的结果。 但是题目中强…...

Makefile教程(Makefile的结构)

文章目录 前言一、Makefile的结构二、深入案例三、Makefile中的一些技巧总结 前言 一、Makefile的结构 Makefile 通常由一系列规则组成&#xff0c;每条规则定义了如何从源文件生成目标文件。每个规则又由目标、依赖和命令三部分组成。 下面是 Makefile 规则的基本结构&…...

SpringMVC(后)SSM整合

10、文件上传和下载 10.1、文件下载 ResponseEntity用于控制器方法的返回值类型&#xff0c;该控制器方法的返回值就是响应到浏览器的响应报文 使用ResponseEntity实现下载文件的功能 RequestMapping("/testDown") public ResponseEntity<byte[]> testResp…...

【博弈论】【第一章】博弈论导论

博弈论导论 【例题】选择数字【例题】巴什博弈【例题】射手博弈博弈论的基本概念&#xff1a;参与人战略行动信息支付函数【例题】分100元 课程概述&#xff1a; 【例题】选择数字 两个参与人A和B&#xff0c;轮流选择[3,4,5,6,7,8,9]中的一个整数&#xff08;可重复)。当累计…...

keil移植linux(makefile)

文章目录 运行环境&#xff1a;1.1 freeRTOS_LED工程移植1)修改cubeMX配置2)setting设置3)launch设置4)修改makefile5)修改代码6)实验效果 运行环境&#xff1a; ubuntu18.04.melodic 宏基暗影骑士笔记本 stm32f427IIH6 stlink 9-24v可调电源 robomaster A 板 1.1 freeRTOS_L…...

C++——类和对象(3)

作者&#xff1a;几冬雪来 时间&#xff1a;2023年5月6日 内容&#xff1a;C类和对象内容讲解 目录 前言&#xff1a; 1.运算符重载&#xff08;续&#xff09;&#xff1a; 2.赋值重载&#xff1a; 结尾&#xff1a; 前言&#xff1a; 在上一篇博客中我们再一次讲解了…...

itop-3568开发板驱动学习笔记(24)设备树(三)时钟实例分析

《【北京迅为】itop-3568开发板驱动开发指南.pdf》 学习笔记 文章目录 生产者属性#clock-cells 属性clock-output-namesclock-frequencyassigned-clockclock-indicesassigned-clock-parents 消费者属性 设备树中的时钟信息以时钟树形式体现&#xff0c;时钟树包括时钟的属性和结…...

linux中使用docker部署微服务

目录 一、制作jar包&#xff08;如果看一眼很简单&#xff0c;可以直接使用结尾的jar&#xff09; 1.首先创建一个微服务 demo2 2.启动微服务&#xff08;在DemoApplication上右键执行启动就行&#xff09; 注意&#xff1a;其他操作导致的 可能遇到的报错 3.修改端口 4.新…...

操作系统考试复习—第三章 优先级倒置 死锁问题

当前OS广泛采用优先级调度算法和抢占方式&#xff0c;然而在系统中存在着影响进程运行的资源从而可能产生"优先级倒置"现象 具体解释为&#xff1a;在原本的调度算法设计中&#xff0c;高优先级进程可以抢占低优先级的CPU资源&#xff0c;先执行高优先级任务。但是存…...

OpenHarmony送显流程分析

OpenHarmony送显流程分析 引言 本文档主要记录OpenHarmony在渲染完成之后如何进行合成和送显流程的。这个过程牵涉的代码很多&#xff0c;而且流程也是比较繁琐的。所以我一定要坚持下来。千万不能半途而废&#xff0c;也不要想着一口气吃出一个胖子&#xff0c;路漫漫其修远兮…...

Java面试题字节流字符流

String 编码UTF-8 和GBK的区别 GBK编码&#xff1a;是指中国的中文字符&#xff0c;其实它包含了简体中文与繁体中文字符&#xff0c;另外还有一种字符 “gb2312”&#xff0c;这种字符仅能存储简体中文字符。 UTF-8编码&#xff1a;它是一种全国家通过的一种编码&#x…...

Self-Attention结构细节及计算过程

一、结构 上面那个图其实不是那么重要&#xff0c;只要知道将输入的x矩阵转换成三个矩阵进行计算即可。自注意力结构的输入为 输入矩阵的三个变形 Q&#xff08;query矩阵&#xff09;、K&#xff08;key矩阵&#xff09;、V&#xff08;value矩阵&#xff09;构成&#xff0c;…...

在Ubuntu18.04中安装uWebSockets库

目录 1.下载uWebSockets库2.下载uSockets3.安装openssl开发包4.编译首先说明这里使用的Ubuntu版本为18.04。 1.下载uWebSockets库 下载uWebSockets库有两种方式,一是终端,从Github中克隆uWebSockets库到Ubuntu本地文件夹,二是打开uWebSockets库下载链接自己下载到Windows,然…...

【Fluent】接着上一次计算的结果继续计算,利用计算过程中得到的物理场(温度、速度、压力等)插值Interpolate文件初始化模型的方法

一、问题背景 因为fluent中支持的初始化无非三种类型。 1、Standard initialization 标准初始化 2、Hybridinitialization 混合初始化 3、FMG initialization FMG初始化 另外&#xff0c;还可以用UDF通过坐标判断的方式予以初始化。 但是这些初始化方法都没办法利用以前计算过…...

第二十九章 使用消息订阅发布实现组件通信

PubSubJS库介绍 如果你想在React中使用第三方库来实现Pub/Sub机制&#xff0c;PubSubJS是一个不错的选择。它是一个轻量级的库&#xff0c;可以在浏览器和Node.js环境中使用。 PubSubJS提供了一个简单的API&#xff0c;可以让你在应用程序中订阅和发布消息。你可以使用npm来安…...

Transformer的位置编码

1. 什么是位置编码&#xff0c;为什么要使用位置编码 简单来说位置编码就是给一个句子中的每个token一个位置信息&#xff0c;通过位置编码可以明确token的前后顺序关系。 对任何语言来说&#xff0c;句子中词汇的顺序和位置都是非常重要的。它们定义了语法&#xff0c;从而定…...

Python学习简记

做题时遇到的不知道的知识点会更新在此&#xff1a; python中的int()函数可以用于进制转换 该函数最为常见的使用是用于强制类型转换&#xff0c;实际上&#xff0c;它可以有两个参数 值得强调的是当传入两个参数时第一个参数一定要是字符串类型 字符串方法&#xff1a; lower(…...

windows搭建一个FTP服务器超详细

一.场景&#xff1a; 在开发过程中需要FTP文件上传下载功能&#xff0c;需要在本地或者服务器上搭建一个FTP服务器。 二.详细步骤&#xff1a; 1. 安装FTP服务器支持和配置IIS web服务器 打卡“启动关闭Window功能” 控制面板>程序>启动或关闭Windows功能 或者选择快…...

u01使用率100%报错归档满的问题

今天下午客户报数据库无法连接了&#xff0c;我也立刻登录查看 因为显示orcl1归档满了&#xff0c;我就登录查看磁盘组的空间&#xff0c;发现空间空余很多 就sqlpus登录了&#xff0c;发现u01使用率满了 [oracledb1 ~]$ sqlplus / as sysdba SQL*Plus: Release 11.2.0.4.0 …...

Packet Tracer - 配置扩展 ACL - 场景 2

Packet Tracer - 配置扩展 ACL - 场景 2 拓扑图 地址分配表 设备 接口 IP 地址 子网掩码 默认网关 RTA G0/0 10.101.117.49 255.255.255.248 不适用 G0/1 10.101.117.33 255.255.255.240 不适用 G0/2 10.101.117.1 255.255.255.224 不适用 PCA NIC 10.101…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...