当前位置: 首页 > 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…...

【极限压测】从99.9%全红到5%安全线!2026最新横评5款硬核降AI工具

说真的&#xff0c;作为在知乎摸爬滚打好几年的博主&#xff0c;我太理解大家临近交稿时的那种绝望了。眼看着论文初稿要交&#xff0c;结果降ai检测一出来&#xff0c;竟然是红彤彤的99%&#xff1f;&#xff01;那一刻&#xff0c;我感觉脑袋真的“嗡”的一声。好不容易熬夜码…...

SCI期刊AI率要求越来越严:一二区5%以下该怎么降

SCI一二区期刊AI率卡到5%以下&#xff0c;我的论文差点废了——后来这么救回来的 2026年开年&#xff0c;身边三个同学的SCI投稿被拒&#xff0c;理由都一样&#xff1a;AI-generated content detected。不是内容不行&#xff0c;是AI率没过关。 我的判断很直接&#xff1a;S…...

Anything V5图像生成效果实测:高清画质与丰富风格展示

Anything V5图像生成效果实测&#xff1a;高清画质与丰富风格展示 1. 引言&#xff1a;惊艳的二次元创作体验 1.1 模型核心能力概述 Anything V5作为Stable Diffusion生态中的明星模型&#xff0c;专为动漫风格图像生成优化。经过大规模高质量二次元数据训练&#xff0c;它能…...

基于Vue的沧交食堂食品监管系统[vue]-计算机毕业设计源码+LW文档

摘要&#xff1a;本文阐述了一个基于Vue框架开发的沧交食堂食品监管系统。该系统旨在借助现代Web技术&#xff0c;强化对沧交食堂食品安全的监管力度&#xff0c;提升监管效率与质量。系统涵盖了系统用户管理、新闻数据管理、食品相关业务管理以及评论管理等多方面功能。文章详…...

新手也能懂的RAIM算法:用Python复现GNSS完好性监测(附代码与数据)

新手也能懂的RAIM算法&#xff1a;用Python复现GNSS完好性监测&#xff08;附代码与数据&#xff09; 当你用手机导航时&#xff0c;是否想过这些定位信号有多可靠&#xff1f;RAIM&#xff08;Receiver Autonomous Integrity Monitoring&#xff09;算法就像GNSS系统的"质…...

TranslucentTB终极配置指南:轻松打造个性化Windows任务栏透明效果

TranslucentTB终极配置指南&#xff1a;轻松打造个性化Windows任务栏透明效果 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB Translucen…...

终极PrimeVue Toast组件交互事件回调指南:从基础到高级应用

终极PrimeVue Toast组件交互事件回调指南&#xff1a;从基础到高级应用 【免费下载链接】primevue Next Generation Vue UI Component Library 项目地址: https://gitcode.com/GitHub_Trending/pr/primevue PrimeVue是一款功能强大的Vue UI组件库&#xff0c;其中Toast组…...

iMeta入选新锐期刊分区表生物学1区Top

2026年3月24日&#xff0c;2026年新锐期刊分区表正式发布。iMeta被评选为生物学1区Top期刊&#xff0c;标志着iMeta期刊学术声誉与影响力持续提升。自创刊以来&#xff0c;iMeta的每一步成长都离不开期刊编委、审稿专家及广大同行的鼎力支持。未来&#xff0c;iMeta将再接再厉&…...

2026权威评测:盘点毕业论文AIGC免费降重神器

【CSDN 资深算法架构师 / NLP技术专栏 导读】 各位还在发际线边缘挣扎的应届生和硕博党们&#xff0c;到了2026年&#xff0c;如果你的电脑里还装着那种老掉牙的“同义词替换”降重软件&#xff0c;我劝你赶紧停手&#xff01; 最近CSDN社群里哀嚎一片&#xff1a;“知网查重过…...

银河麒麟V4.0.2-sp4服务器到手后,这三步网络配置(IP/DNS/源)一个都不能少

银河麒麟V4.0.2-sp4服务器网络配置实战指南&#xff1a;从零搭建稳定运行环境 刚拿到一台预装银河麒麟V4.0.2-sp4操作系统的服务器时&#xff0c;许多运维工程师常会陷入"有设备却用不起来"的困境——无法远程连接、软件包安装失败、系统更新卡壳&#xff0c;这些问题…...