[LC646]最长数对链
2022/9/3 23:26:29
本文主要是介绍[LC646]最长数对链,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目概述
给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。
现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-length-of-pair-chain
解题思路
这道题可以采用贪心的做法。对于一个已经确定的最优子链条,如何选择一个最优的新数对接上去?答案:我们根据数对的第二个数,对数对数组进行升序排序,得到有序的数组arr
。我们记当前已经确定的数对链条的最后一个数对的值为[a,b]
,那么我们需要在arr中找到一个数对[x,y],在满足x > b的情况下,y是最小的(这里利用有序性,直接遍历,检查是否x > b,第一个满足条件的数对,就是y最小数对)。然后按这个思路,不断的寻找新的最优的新数对即可。
关于贪心方法正确性的证明,假设对于当前最优子链条,能找到更优的新数对[x1,y1],那么y1 必然大于按贪心方法找到的 y(我们在之前的定义中,定义y为找到的第一个符合条件的数对)。如果y1 > y, x1 > b 同时成立,那么数对[x, y]必然可以替换[x1, y1],插入到最优链中。这实际上是矛盾的。因此,按贪心方法即能找到最优的数链。
代码
Java
class Solution { public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (o1, o2)-> o1[1] - o2[1]); int cnt = 1; int[] prevElement = pairs[0]; for(int i = 0; i < pairs.length; i++){ if(pairs[i][0] > prevElement[1]){ cnt ++; prevElement = pairs[i]; } } return cnt; } }
这篇关于[LC646]最长数对链的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升