Leetcode 645.最长数对链
2024-09-04 16:29:30
最长数对链
给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。
现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个对数集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。
示例 :
输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意:
- 给出数对的个数在 [1, 1000] 范围内。
思路
Intuition
If a chain of length k ends at some pairs[i], and pairs[i][1] < pairs[j][0], we can extend this chain to a chain of length k+1.
Algorithm
Sort the pairs by first coordinate, and let dp[i] be the length of the longest chain ending at pairs[i]. When i < j and pairs[i][1] < pairs[j][0], we can extend the chain, and so we have the candidate answer dp[j] = max(dp[j], dp[i] + 1).
import java.util.Arrays; class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int N = pairs.length;
int[] dp = new int[N];
Arrays.fill(dp, 1); for (int j = 1; j < N; ++j) {
for (int i = 0; i < j; ++i) {
if (pairs[i][1] < pairs[j][0])
dp[j] = Math.max(dp[j], dp[i] + 1);
}
} int ans = 0;
for (int x: dp) if (x > ans) ans = x;
return ans;
}
}
最新文章
- 【CVE-2016-10009】OpenSSH <; 7.4 - agent Protocol Arbitrary Library Loading
- Learning in Two-Player Matrix Games
- Security.website-that-focus-on-mobile-app-security
- PHP中CURL方法curl_setopt()函数的参数
- android baseActivity
- (转)新手必看:HighCharts几个基础问答
- Vim的文件加密
- swift-自定义无限轮播图
- Linux系统下ssh的相关配置详细解析
- 用CSS3实现带小三角形的div框(不用图片)
- Codeforces Round #390 (Div. 2)
- mysql学习一 常用语句
- webuploader在ie9以下失效原因
- springboot对oracle的配置
- oracle经验记录
- Java只给汉字转URLEncoder
- angular2.0 官网架构文档
- 【python】python函数式编程、高阶函数
- Linux内核学习笔记(3)-- 进程的创建和终结
- [Leetcode Week13]Search a 2D Matrix
热门文章
- Bezier贝塞尔曲线的原理、二次贝塞尔曲线的实现
- POJ 3233 Matrix Power Series (矩阵分块,递推)
- 完全用 Linux 工作
- 使用Scanner类获取键盘输入的会员卡号,并将该数据存储在变量中,输出这个变量的信息
- 架构图(拓扑图)画图工具分析整理(静态,动态,可交互图.层级tu)
- [vijos1066]弱弱的战壕
- C/C++程序基础 (九)排序算法简述
- Centos 安装python 3.7 ,同时兼容python2.7
- linux主机状态检测方式
- SSH密钥验证