leetcode646. 最长数对链(java)

最长数对链

  • 题目描述
    • 贪心
    • 解法二 动态规划 dp

题目描述

难度 - 中等
leetcode646. 最长数对链(java)

给你一个由 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

在这里插入图片描述

贪心

要挑选最长数对链的第一个数对时,最优的选择是挑选第二个数字最小的,这样能给挑选后续的数对留下更多的空间。挑完第一个数对后,要挑第二个数对时,也是按照相同的思路,是在剩下的数对中,第一个数字满足题意的条件下,挑选第二个数字最小的。按照这样的思路,可以先将输入按照第二个数字排序,然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。

代码演示:

    public int findLongestChain(int[][] pairs) {Arrays.sort(pairs, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});int ans = 0;int cur = Integer.MIN_VALUE;for(int[] p : pairs){if(cur < p[0]){ans++;cur = p[1];}}return ans;}

在这里插入图片描述

解法二 动态规划 dp

起始先将 pairs 根据第一维排升序(或直接双关键字排升序)。
考虑定义 f[i] 为以 pairs[i] 为结尾的最长数对链长度,所有 f[i] 中的最大值为答案。
不失一般性考虑 f[i] 该如何转移:不难发现 f[i]为所有满足「下标范围在 [0,i−1],且 pairs[j][1]<pairs[i][0]条件的 f[j]+1 的最大值。

但实际上,我们只需要从 j=i−1 开始往回找,找到第一个满足 pairs[j][1]<pairs[i][0]的位置 j 即可。

容易证明该做法的正确性:假设贪心解(该做法)找到的位置 jjj 不是最优位置,即存在比 j 更小的合法下标 j′ 满足 f[j′]>f[j]]。根据我们的排序规则必然有 pairs[j′][0]<=pairs[j][0]的性质,则可知 pairs[j] 必然可以代替 pairs[j′] 接在原本以 pairs[j′]为结尾的最优数链上(最优数链长度不变,结果不会变差),则至少有 f[j′]=f[j]。

代码演示:

  public int findLongestChain(int[][] pairs) {Arrays.sort(pairs,(a,b) -> {return a[0] - b[0];});int ans = 1;int n = pairs.length;int[] dp = new int[n];for(int i = 0; i < n;i++){dp[i] = 1;for(int j = i - 1; j >= 0 && dp[i] == 1;j--){if(pairs[j][1] < pairs[i][0]){dp[i] = dp[j] + 1;}}ans = Math.max(ans,dp[i]);}return ans;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/137299.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RHCSA_Linux 从命令行管理文件

目录 一、文件命令规范&#xff1a; 二、创建链接文件 1、创建软链接文件 2、创建硬链接文件 三、目录操作命令 1、创建目录 -- mkdir 2、统计目录及文件的空间占用情况 -- du 3、删除目录文件 四、创建、删除普通文件 1、创建普通文件 2、删除普通文件 五、数据流和…

Vivado下PLL实验

文章目录 前言一、CMT&#xff08;时钟管理单元&#xff09;1、CMT 简介2、FPGA CMT 框图3、MMCM 框图4、PLL 框图 二、创建工程1、创建工程2、PLL IP 核配置3、进行例化 三、进行仿真1、创建仿真文件2、进行仿真设置3、进行行为级仿真 四、硬件验证1、引脚绑定2、生成比特流文…

SAP 打note步骤

SAP 打note步骤 先确定需要实施的note 1.登录sap支持门户网站&#xff0c;查找note文件。https://support.sap.com/en/index.html 2.下载note文件到本地 3.事务代码SNOTE上传note文件 4.实施note,选中上传note&#xff0c;执行 5.往后一直确认 6.显示已实施成功 7.查看系…

驱动开发练习,platform实现如下功能

实验要求 驱动代码 #include <linux/init.h> #include <linux/module.h> #include <linux/platform_device.h> #include <linux/mod_devicetable.h> #include <linux/of_gpio.h> #include <linux/unistd.h> #include <linux/interrupt…

爬虫技术对携程网旅游景点和酒店信息的数据挖掘和分析应用

导语 爬虫技术是一种通过网络爬取目标网站的数据并进行分析的技术&#xff0c;它可以用于各种领域&#xff0c;如电子商务、社交媒体、新闻、教育等。本文将介绍如何使用爬虫技术对携程网旅游景点和酒店信息进行数据挖掘和分析&#xff0c;以及如何利用Selenium库和代理IP技术…

【element-ui】el-date-picker 之picker-options时间选择区间禁用效果的实现

element-ui 时间选择器的时间区间禁用dom层引入:picker-option <el-date-pickerv-model"searchFormObj.workTime"clearablevalue-formate"yyyy-MM-dd":picker-options"pickerOptions"placeholder"请选择时间" ></el-date-pi…

反转单链表

思路图1&#xff1a; 代码&#xff1a; struct ListNode* reverseList(struct ListNode* head){if(headNULL)//当head是空链表时 {return head; }struct ListNode* n1NULL;struct ListNode* n2head;struct ListNode* n3head->next;if(head->nextNULL)//当链表只有一个节…

SpringCloud——微服务

微服务技术栈 在之前的开发过程中&#xff0c;我们将所有的服务都部署在一台服务器中&#xff0c;当我们的服务开始越来越多&#xff0c;业务越来越复杂&#xff0c;当一台服务器不能承担我们的业务的时候&#xff0c;就需要将不同的业务分开部署在不同的服务器上&#xff0c;…

成集云 | 用友U8集成聚水潭ERP(用友U8主管库存)| 解决方案

源系统成集云目标系统 方案介绍 用友U8是一套企业级的解决方案&#xff0c;可满足不同的制造、商务模式下&#xff0c;不同运营模式下的企业经营管理。它全面集成了财务、生产制造及供应链的成熟应用&#xff0c;并延伸客户管理至客户关系管理&#xff08;CRM&#xff09;&am…

MQTT服务器搭建

本次搭建的MQTT服务器是emqx提供的服务器 1、下载 https://www.emqx.com/en/downloads/broker 从官网下载5.2.0版本emqx-5.2.0-windows-amd64.zip 下载完成直接安装 2、配置&#xff0c;修改端口号 mqtt默认端口号 常规的用法&#xff0c;我们一般使用和开放这两个端口&am…

selenium转到新页面操作以及使用execute_script执行js代码获取页面元素

selenium操作页面&#xff1a;在一个A网页中有按钮&#xff0c;点击后&#xff0c;会新建一个B页面&#xff0c;接下来所有的webdriver操作要全部在B页面中。 A页面中&#xff0c;点击“去签到”后&#xff0c;跳转到B页面。 A&#xff1a; B&#xff1a; 代码如下&#xff…

QGIS怎么修改源代码?持续更新...

修改配置文件保存位置 修改目的&#xff1a;放着和本地安装的其他QGIS共用一份配置文件 修改文件&#xff1a;core/qgsuserprofilemanager.cpp 修改位置&#xff1a;第37行 return basePath QDir::separator() "my_profiles";修改完毕后&#xff0c;再次生成一下…

【操作系统】聊聊磁盘IO是如何工作的

磁盘 机械磁盘 主要是由盘片和读写磁头组成。数据存储在盘片的的环状磁道上&#xff0c;读写数据前需要移动磁头&#xff0c;先找到对应的磁道&#xff0c;然后才可以访问数据。 如果数据都在同一磁道上&#xff0c;不需要在进行切换磁道&#xff0c;这就是连续IO&#xff0c;可…

uview组件库的安装

更多的请查看官方文档uView 2.0 - 全面兼容 nvue 的 uni-app 生态框架 - uni-app UI 框架 (uviewui.com) // 如果您的根目录没有package.json文件的话&#xff0c;请先执行如下命令&#xff1a; // npm init -y 安装 npm install uview-ui2.0.36 // 更新 // npm update uvie…

Python常用库(六):科学计算库-Numpy[上篇]:创建、访问、赋值

1.Numpy 1.1 介绍 NumPy是Python中非常流行且重要的科学计算库&#xff0c;提供了一个强大的多维数组对象(ndarray)和许多数学操作&#xff0c;包括矩阵运算、线性代数、微积分等等。 numpy是Python中一个非常有用的工具&#xff0c;特别是在需要进行数值计算、线性代数计算、…

JS 原型和原型链

原型和原型链 1. 了解原型和原型链1.1 原型1.2 原型链 2. 原型2.1 prototype2.2 __proto__ 隐式原型 3. 原型链 1. 了解原型和原型链 1.1 原型 原型&#xff1a; prototype 又称显示原型 1、原型是一个普通对象 2、只有构造函数才具备该属性 3、公有属性可操作 1.2 原型链 原…

MySQL数据库详解 二:数据库的高级语言和操作

文章目录 1. 克隆表 ---- 将数据表的数据记录生成到新的表中1.1 方式一&#xff1a;先创建新表&#xff0c;再导入数据1.2方式二&#xff1a;创建的时候同时导入 2. 清空表 ---- 删除表内的所有数据2.1 delete删除2.2 truncate删除&#xff08;重新记录&#xff09;2.3 创建临时…

如何使用ArcGIS中的Arcmap进行矢量和栅格数据裁剪?

在地理信息系统(GIS)中&#xff0c;我们经常需要处理各种空间数据&#xff0c;而矢量和栅格数据是最常见的两种数据类型。有时候&#xff0c;我们需要对数据进行裁剪&#xff0c;以提取出我们需要的特定区域的数据。本文将介绍如何使用ArcGIS中的Arcmap软件对矢量和栅格数据进行…

2054. 两个最好的不重叠活动;1255. 得分最高的单词集合;858. 镜面反射

2054. 两个最好的不重叠活动 核心思想:枚举小堆。因为你最多可以参加两个时间不重叠活动&#xff0c;所以我们就枚举其中一个活动&#xff0c;用一个堆来维护右边界的最小值&#xff0c;因为我们的event是排序的&#xff0c;前面满足的max_r_v&#xff0c;后面的event也肯定满…

网络防御--防火墙

拓扑 Cloud 1 作为电脑与ENSP的桥梁 防火墙配置 登录防火墙 配置IP地址及安全区域 添加地址对象 配置策略 1、内网可以访问服务器 结果 2、内网可以访问公网 结果 配置NAT策略 结果