class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
}
};
646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
提示：
[1, 1000] 范围内。原站题解
javascript 解法, 执行用时: 80 ms, 内存消耗: 44.7 MB, 提交时间: 2022-12-05 18:25:20
/**
* @param {number[][]} pairs
* @return {number}
*/
var findLongestChain = function(pairs) {
let curr = -Number.MAX_VALUE, res = 0;
pairs.sort((a, b) => a[1] - b[1]);
for (const p of pairs) {
if (curr < p[0]) {
curr = p[1];
res++;
}
}
return res;
}
golang 解法, 执行用时: 32 ms, 内存消耗: 6.5 MB, 提交时间: 2022-12-05 18:25:07
func findLongestChain(pairs [][]int) (ans int) {
sort.Slice(pairs, func(i, j int) bool { return pairs[i][1] < pairs[j][1] })
cur := math.MinInt32
for _, p := range pairs {
if cur < p[0] {
cur = p[1]
ans++
}
}
return
}
java 解法, 执行用时: 8 ms, 内存消耗: 41.4 MB, 提交时间: 2022-12-05 18:24:54
class Solution {
public int findLongestChain(int[][] pairs) {
int curr = Integer.MIN_VALUE, res = 0;
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
for (int[] p : pairs) {
if (curr < p[0]) {
curr = p[1];
res++;
}
}
return res;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-05 18:24:38
# 贪心
class Solution(object):
def findLongestChain(self, pairs: List[List[int]]) -> int:
cur, res = -inf, 0
for x, y in sorted(pairs, key=lambda p: p[1]):
if cur < x:
cur = y
res += 1
return res
python3 解法, 执行用时: 60 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-05 18:24:23
# 最长递增子序列
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort()
arr = []
for x, y in pairs:
i = bisect_left(arr, x)
if i < len(arr):
arr[i] = min(arr[i], y)
else:
arr.append(y)
return len(arr)
java 解法, 执行用时: 9 ms, 内存消耗: 41.5 MB, 提交时间: 2022-12-05 18:23:57
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
List<Integer> arr = new ArrayList<Integer>();
for (int[] p : pairs) {
int x = p[0], y = p[1];
if (arr.isEmpty() || x > arr.get(arr.size() - 1)) {
arr.add(y);
} else {
int idx = binarySearch(arr, x);
arr.set(idx, Math.min(arr.get(idx), y));
}
}
return arr.size();
}
public int binarySearch(List<Integer> arr, int x) {
int low = 0, high = arr.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr.get(mid) >= x) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
golang 解法, 执行用时: 28 ms, 内存消耗: 6.6 MB, 提交时间: 2022-12-05 18:23:43
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })
arr := []int{}
for _, p := range pairs {
i := sort.SearchInts(arr, p[0])
if i < len(arr) {
arr[i] = min(arr[i], p[1])
} else {
arr = append(arr, p[1])
}
}
return len(arr)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 45.6 MB, 提交时间: 2022-12-05 18:23:29
/**
* @param {number[][]} pairs
* @return {number}
*/
var findLongestChain = function(pairs) {
pairs.sort((a, b) => a[0] - b[0]);
const arr = [];
for (const p of pairs) {
let x = p[0], y = p[1];
if (arr.length === 0 || x > arr[arr.length - 1]) {
arr.push(y);
} else {
const idx = binarySearch(arr, x);
arr[idx] = Math.min(arr[idx], y);
}
}
return arr.length;
}
const binarySearch = (arr, x) => {
let low = 0, high = arr.length - 1;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] >= x) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
};
javascript 解法, 执行用时: 140 ms, 内存消耗: 44.7 MB, 提交时间: 2022-12-05 18:23:14
/**
* @param {number[][]} pairs
* @return {number}
*/
var findLongestChain = function(pairs) {
const n = pairs.length;
pairs.sort((a, b) => a[0] - b[0]);
const dp = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
};
golang 解法, 执行用时: 48 ms, 内存消耗: 6.5 MB, 提交时间: 2022-12-05 18:23:01
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })
n := len(pairs)
dp := make([]int, n)
for i, p := range pairs {
dp[i] = 1
for j, q := range pairs[:i] {
if p[0] > q[1] {
dp[i] = max(dp[i], dp[j]+1)
}
}
}
return dp[n-1]
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
java 解法, 执行用时: 36 ms, 内存消耗: 41.6 MB, 提交时间: 2022-12-05 18:22:46
class Solution {
public int findLongestChain(int[][] pairs) {
int n = pairs.length;
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
}
python3 解法, 执行用时: 2028 ms, 内存消耗: 15.3 MB, 提交时间: 2022-12-05 18:21:34
'''
定义 dp[i] 为以 pairs[i] 为结尾的最长数对链的长度。
计算 dp[i] 时，可以先找出所有的满足 pairs[i][0]>pairs[j][1] 的 j，
并求出最大的 dp[j]，dp[i] 的值即可赋为这个最大值加一。
这种动态规划的思路要求计算 dp[i] 时，所有潜在的 dp[j] 已经计算完成，
可以先将 pairs 进行排序来满足这一要求。初始化时，dp 需要全部赋值为 1。
'''
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort()
dp = [1] * len(pairs)
for i in range(len(pairs)):
for j in range(i):
if pairs[i][0] > pairs[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
return dp[-1]