做一个网站最低多少钱,网站模板去哪下载,网络科技有限公司网站建设策划书,wordpress文章目录树目录
力扣646. 最长数对链
解析代码 力扣646. 最长数对链
646. 最长数对链
难度 中等
给你一个由 n 个数对组成的数对数组 pairs #xff0c;其中 pairs[i] [lefti, righti] 且 lefti righti 。
现在#xff0c;我们定义一种 跟随 关系#xff0c;当且仅当 b 其中 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.length1 n 1000-1000 lefti righti 1000
class Solution {
public:int findLongestChain(vectorvectorint pairs) {}
}; 解析代码 这道题目让我们在数对数组中挑选出来⼀些数对组成⼀个呈现上升形态的最长的数对链。像不像整数数组中挑选一些数让这些数组成⼀个最长的上升序列因此我们可以把问题转化成我 们学过的一个模型 力扣300. 最长递增子序列。因此我们解决问题的方向在此模型上。 不过与整形数组有所区别。在用动态规划结局问题之前应该先把数组排序。因为我们在计算 dp[i] 的时候要知道所有左区间比 pairs[i] 的左区间小的链对。排完序之后只用往前遍历一遍即可。
状态表示 dp[i] 表示以 i 位置的数对为结尾时最长数对链的长度。 状态转移方程 对于 dp[i] 遍历所有 [0, i - 1] 区间内数对用 j 表示下标找出所有满足 pairs[j] [1] pairs[i][0] 的 j 。找出里面最大的 dp[j] 然后加上 1 就是以 i 位置为结尾的最长数对链。
dp表全初始化成1从左往右填表最后返回dp表的最大值即可。
class Solution {
public:int findLongestChain(vectorvectorint pairs) {sort(pairs.begin(), pairs.end());int n pairs.size(), ret 1;// dp[i] 表示以 i 位置的数对为结尾时最长数对链的长度vectorint dp(n, 1);for(int i 1; i n; i){for(int j 0; j i; j){if(pairs[j][1] pairs[i][0])dp[i] max(dp[j] 1, dp[i]);}ret max(ret, dp[i]);}return ret;}
};
