当前位置: 首页 > 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;可利用图像特征点作为…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...