每天一道leetcode:646. 最长数对链(动态规划中等)
今日份题目:
给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。
示例1
输入:pairs = [[1,2], [2,3], [3,4]] 输出:2 解释:最长的数对链是 [1,2] -> [3,4] 。
示例2
输入:pairs = [[1,2],[7,8],[4,5]] 输出:3 解释:最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
提示
-
n == pairs.length -
1 <= n <= 1000 -
-1000 <= lefti < righti <= 1000
题目思路
动态规划,一维dp数组记录到目前为止的最长数对链数值。
状态转移方程:
找到当前位置之前的满足递增的最长dp值的那一组,找不到就是自己(1)。
dp[i]=max(dp[i],dp[j]+1);
代码
class Solution
{
public:int findLongestChain(vector<vector<int>>& pairs) {int n=pairs.size();vector<int> dp(n,1);//记录到目前为止的最长数对链sort(pairs.begin(),pairs.end());for(int i=0;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);//状态转移方程}}}return dp[n-1];}
};
提交结果

欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:646. 最长数对链(动态规划中等)
今日份题目: 给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] [lefti, righti] 且 lefti < righti 。 现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 [c, d] 才可以跟在 p1 [a, b] 后面…...
651页23万字智慧教育大数据信息化顶层设计及建设方案WORD
导读:原文《651页23万字智慧教育大数据信息化顶层设计及建设方案WORD》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。 目录 一、 方案背景 1.1 以教育…...
Vue3 使用json编辑器
安装 npm install json-editor-vue3 main中引入 main.js 中加入下面代码 import "jsoneditor";不然会有报错,如jsoneditor does not provide an export named ‘default’。 图片信息来源-github 代码示例 <template><json-editor-vue class…...
centos7 docker离线安装教程
centos7 docker离线安装教程 离线安装包下载# docker离线安装时需要两个安装包:selinux包、docker包, 下载地址: https://download.docker.com/linux/centos/7/x86_64/stable/Packages/selinux包下载 https://download.docker.com/linux/…...
解决爬虫上下行传输效率问题的实用指南
嗨,大家好!作为一名专业的爬虫程序员,我们经常会面临上下行传输效率低下的问题。在处理大量数据时,如果传输效率不高,可能会导致爬虫任务速度慢,甚至中断。今天,我将和大家分享一些解决爬虫上下…...
Vue2入门学习汇总
1.介绍及安装 1.1 介绍 Vue是一套构建用户界面的渐进式框架。Vue只关注视图层,采用自底向上增量开发的设计。Vue的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。 学习vue之前主要掌握的知识:HTML、CSS、JavaScript、TypeScript …...
收支明细高效管理,轻松查看和统计时间段内的开销收支明细!
亲爱的用户们,您是否经常需要查看某一时间段内的所有开销和收支明细,并进行自动统计和分析?现在,我们为您带来一款智能财务管家,让您轻松管理财务! 首先,我们要进入晨曦记账本主页面࿰…...
c++ 成绩统计
Q: 有一个二维表格数据,它的值全部是整数,其中存储了若干个选手参与5分钟汉字输入比赛的成绩。数据中每一行是一条记录,每条记录包含两个整数,第1个整数为选手编号,它应该是一个4位整数;第2个整…...
PostgreSQL-UDF用户自定义函数-扩展插件
目录 PostgreSQL-UDF用户自定义函数-扩展插件零、前置条件一、创建 .c 和 .sql 文件创建.c文件创建.sql文件 二、创建 .control 和 Makefile 文件创建 .control 文件创建 Makefile 文件 三、编译 & 链接四、psql(或者其他PG backend)中创建扩展 Post…...
接口测试及接口抓包常用测试工具和方法?
作为测试领域中不可或缺的一环,接口测试和抓包技术在软件开发过程中扮演着至关重要的角色。不论你是新手还是有一些经验的小伙伴,本篇文章都会为你详细介绍接口测试的基本概念、常用测试工具和实际操作技巧,让你轻松掌握这一技能。 接口测试…...
C语言入门_Day 6布尔数与比较运算
目录 前言 1.布尔数 2.比较运算 3.易错点 4.思维导图 前言 除了算术计算以外,编程语言中还会大量使用比较运算,并会根据比较运算的结果是“真”还是“假”,来执行不同的代码。 当你想买一杯奶茶,准备支付的时候,支…...
Java中的JDBC
什么是JDBC 1.Java数据库连接技术(Java DataBase Connectivity),能实现Java程序对各种数据库的访问 2.由一组使用Java语言编写的类和接口(JDBC API)组成,它们位于java.sql以及javax.sql中 JDBC访问数据库的步骤: 步骤 1.Class.forName()加载…...
Vue 安装开发者工具
1.下载开发者工具,下载地址:http://book.wiyp.top/App/Vue3开发者工具-谷歌/Vue3.crx 2.打开谷歌浏览器,点击扩展,点击管理扩展程序。 3.开启开发者模式,将 Vue3 开发者工具文件拖拽到浏览器中进行安装。 注ÿ…...
oracle修改临时表出现已使用的事务正在处理临时表问题
错误提示: ORA-14450:试图访问已经在使用的事务处理临时表 解决方法: 通过第一句sql来查找临时表的object_id ,然后代入第二局sql来生成第三句sql语句。 最后再执行第三句sql语句即可kill session,执行修改表的操作。 SELECT * F…...
RestTemplate
RestTemplate介绍 RestTemplate是Spring提供的用于访问RESTful服务的客户端,RestTemplate提供了多种便捷访问远程Http服务的方法,能够大大提高客户端的编写效率。RestTemplate默认依赖JDK提供http连接的能力(HttpURLConnection),…...
rabbitMQ服务自动停止(已解决
1、 在rabbitmq的sbin目录下操作 rabbitmq-plugins enable rabbitmq_management 2、 自己去rabbitmq_server-3.7.5文件夹下创建一个data,再执行这个命令(用自己的目录哈 set RABBITMQ_BASED:\RabbitTools\RabbitMQ\rabbitmq_server-3.7.5\data 然后去配…...
Qt平滑弹出页面
目标功能: (1)按下btn,弹出绿色页面。 (2)按下btn2,绿色页面隐藏。 (3)按下左边余下的区域,绿色页面也隐藏。 (4)平滑地显示和隐藏 效果: form.h #ifndef FORM_H #define FORM_H#include <QWidget>namespace Ui { class…...
第07天 Static关键字作用及用法
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏:每天一个知识点 ✨特色专栏:…...
Redis扩容与一致性Hash算法解析
推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享,打开手机app,额外获得1T空间 https://dr…...
【第七讲---视觉里程计1】
视觉里程计就是通过对图像进行特征提取与匹配得到两帧之间的位姿,并进行估计相机运动。 经典SLAM中以相机位姿-路标来描述SLAM过程 特征提取与匹配 路标是三维空间中固定不变的点,可以在特定位姿下观测到在视觉SLAM中,可利用图像特征点作为…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
