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

每天一道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. 最长数对链(动态规划中等)

今日份题目&#xff1a; 给你一个由 n 个数对组成的数对数组 pairs &#xff0c;其中 pairs[i] [lefti, righti] 且 lefti < righti 。 现在&#xff0c;我们定义一种 跟随 关系&#xff0c;当且仅当 b < c 时&#xff0c;数对 p2 [c, d] 才可以跟在 p1 [a, b] 后面…...

651页23万字智慧教育大数据信息化顶层设计及建设方案WORD

导读&#xff1a;原文《651页23万字智慧教育大数据信息化顶层设计及建设方案WORD》&#xff08;获取来源见文尾&#xff09;&#xff0c;本文精选其中精华及架构部分&#xff0c;逻辑清晰、内容完整&#xff0c;为快速形成售前方案提供参考。 目录 一、 方案背景 1.1 以教育…...

Vue3 使用json编辑器

安装 npm install json-editor-vue3 main中引入 main.js 中加入下面代码 import "jsoneditor";不然会有报错&#xff0c;如jsoneditor does not provide an export named ‘default’。 图片信息来源-github 代码示例 <template><json-editor-vue class…...

centos7 docker离线安装教程

centos7 docker离线安装教程 离线安装包下载# docker离线安装时需要两个安装包&#xff1a;selinux包、docker包&#xff0c; 下载地址&#xff1a; https://download.docker.com/linux/centos/7/x86_64/stable/Packages/selinux包下载 https://download.docker.com/linux/…...

解决爬虫上下行传输效率问题的实用指南

嗨&#xff0c;大家好&#xff01;作为一名专业的爬虫程序员&#xff0c;我们经常会面临上下行传输效率低下的问题。在处理大量数据时&#xff0c;如果传输效率不高&#xff0c;可能会导致爬虫任务速度慢&#xff0c;甚至中断。今天&#xff0c;我将和大家分享一些解决爬虫上下…...

Vue2入门学习汇总

1.介绍及安装 1.1 介绍 Vue是一套构建用户界面的渐进式框架。Vue只关注视图层&#xff0c;采用自底向上增量开发的设计。Vue的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。 学习vue之前主要掌握的知识&#xff1a;HTML、CSS、JavaScript、TypeScript …...

收支明细高效管理,轻松查看和统计时间段内的开销收支明细!

亲爱的用户们&#xff0c;您是否经常需要查看某一时间段内的所有开销和收支明细&#xff0c;并进行自动统计和分析&#xff1f;现在&#xff0c;我们为您带来一款智能财务管家&#xff0c;让您轻松管理财务&#xff01; 首先&#xff0c;我们要进入晨曦记账本主页面&#xff0…...

c++ 成绩统计

Q&#xff1a; 有一个二维表格数据&#xff0c;它的值全部是整数&#xff0c;其中存储了若干个选手参与5分钟汉字输入比赛的成绩。数据中每一行是一条记录&#xff0c;每条记录包含两个整数&#xff0c;第1个整数为选手编号&#xff0c;它应该是一个4位整数&#xff1b;第2个整…...

PostgreSQL-UDF用户自定义函数-扩展插件

目录 PostgreSQL-UDF用户自定义函数-扩展插件零、前置条件一、创建 .c 和 .sql 文件创建.c文件创建.sql文件 二、创建 .control 和 Makefile 文件创建 .control 文件创建 Makefile 文件 三、编译 & 链接四、psql&#xff08;或者其他PG backend&#xff09;中创建扩展 Post…...

接口测试及接口抓包常用测试工具和方法?

作为测试领域中不可或缺的一环&#xff0c;接口测试和抓包技术在软件开发过程中扮演着至关重要的角色。不论你是新手还是有一些经验的小伙伴&#xff0c;本篇文章都会为你详细介绍接口测试的基本概念、常用测试工具和实际操作技巧&#xff0c;让你轻松掌握这一技能。 接口测试…...

C语言入门_Day 6布尔数与比较运算

目录 前言 1.布尔数 2.比较运算 3.易错点 4.思维导图 前言 除了算术计算以外&#xff0c;编程语言中还会大量使用比较运算&#xff0c;并会根据比较运算的结果是“真”还是“假”&#xff0c;来执行不同的代码。 当你想买一杯奶茶&#xff0c;准备支付的时候&#xff0c;支…...

Java中的JDBC

什么是JDBC 1.Java数据库连接技术(Java DataBase Connectivity)&#xff0c;能实现Java程序对各种数据库的访问 2.由一组使用Java语言编写的类和接口(JDBC API)组成&#xff0c;它们位于java.sql以及javax.sql中 JDBC访问数据库的步骤&#xff1a; 步骤 1.Class.forName()加载…...

Vue 安装开发者工具

1.下载开发者工具&#xff0c;下载地址&#xff1a;http://book.wiyp.top/App/Vue3开发者工具-谷歌/Vue3.crx 2.打开谷歌浏览器&#xff0c;点击扩展&#xff0c;点击管理扩展程序。 3.开启开发者模式&#xff0c;将 Vue3 开发者工具文件拖拽到浏览器中进行安装。 注&#xff…...

oracle修改临时表出现已使用的事务正在处理临时表问题

错误提示&#xff1a; ORA-14450:试图访问已经在使用的事务处理临时表 解决方法&#xff1a; 通过第一句sql来查找临时表的object_id &#xff0c;然后代入第二局sql来生成第三句sql语句。 最后再执行第三句sql语句即可kill session&#xff0c;执行修改表的操作。 SELECT * F…...

RestTemplate

RestTemplate介绍 RestTemplate是Spring提供的用于访问RESTful服务的客户端&#xff0c;RestTemplate提供了多种便捷访问远程Http服务的方法,能够大大提高客户端的编写效率。RestTemplate默认依赖JDK提供http连接的能力&#xff08;HttpURLConnection&#xff09;&#xff0c;…...

rabbitMQ服务自动停止(已解决

1、 在rabbitmq的sbin目录下操作 rabbitmq-plugins enable rabbitmq_management 2、 自己去rabbitmq_server-3.7.5文件夹下创建一个data&#xff0c;再执行这个命令&#xff08;用自己的目录哈 set RABBITMQ_BASED:\RabbitTools\RabbitMQ\rabbitmq_server-3.7.5\data 然后去配…...

Qt平滑弹出页面

目标功能&#xff1a; (1)按下btn&#xff0c;弹出绿色页面。 (2)按下btn2,绿色页面隐藏。 (3)按下左边余下的区域&#xff0c;绿色页面也隐藏。 (4)平滑地显示和隐藏 效果&#xff1a; form.h #ifndef FORM_H #define FORM_H#include <QWidget>namespace Ui { class…...

第07天 Static关键字作用及用法

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a;每天一个知识点 ✨特色专栏&#xff1a…...

Redis扩容与一致性Hash算法解析

推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享&#xff0c;打开手机app&#xff0c;额外获得1T空间 https://dr…...

【第七讲---视觉里程计1】

视觉里程计就是通过对图像进行特征提取与匹配得到两帧之间的位姿&#xff0c;并进行估计相机运动。 经典SLAM中以相机位姿-路标来描述SLAM过程 特征提取与匹配 路标是三维空间中固定不变的点&#xff0c;可以在特定位姿下观测到在视觉SLAM中&#xff0c;可利用图像特征点作为…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...