递归、动态规划、二分查找、贪心算法，升序排列数组，传递回调函数，自定义排序，4 解法求解《646. 最长数对链》
例题
646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：
给出数对的个数在 [1, 1000] 范围内。
答案
递归 · 排序 · 按 c 升序 · 哈希表记忆化剪枝
var findLongestChain = function(pairs) {
pairs.sort((a, b) => a[0] - b[0])
const h = new Map, getId = (b, l) => b * 1000 + l
n = pairs.length, dfs = (i, b, l) => {
const id = getId(b, l)
let t = h.get(id)
if (t !== void 0) return t
if (i === n) return h.set(id, l), l
const [c, d] = pairs[i]
if (c <= b) return t = dfs(i + 1, b, l), h.set(id, t), t
return t = Math.max(dfs(i + 1, b, l), dfs(i + 1, d, l + 1)), h.set(id, t), t
}
return dfs(0, Number.MIN_SAFE_INTEGER, 0)
};动态规划 · 排序 · 按 c 升序
var findLongestChain = function(pairs) {
pairs.sort((a, b) => a[0] - b[0])
const n = pairs.length, dp = new Uint16Array(n).fill(1)
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
return dp[n - 1]
};function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[0] - b[0])
const n = pairs.length, dp = new Uint32Array(n).fill(1)
for (let i = 1; i < n; i++) {
const [c, _] = pairs[i]
for (let j = 0; j < i; j++) {
const [_, b] = pairs[j]
if (b < c) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return dp[n - 1]
};class Solution {
function findLongestChain($pairs) {
usort($pairs, function($a, $b) {
return $a[0] >= $b[0];
});
$n = count($pairs);
$dp = array_fill(0, $n, 1);
for ($i = 1; $i < $n; $i++) {
$c = $pairs[$i][0];
for ($j = 0; $j < $i; $j++) {
$b = $pairs[$j][1];
if ($c > $b) $dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
return $dp[$n - 1];
}
}func findLongestChain(pairs [][]int) int {
sort.SliceStable(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
n := len(pairs)
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
for i := 1; i < n; i++ {
c := pairs[i][0]
for j := 0; j < i; j++ {
b := pairs[j][1]
if c > b {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
return dp[n - 1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}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 i = 1; i < n; i++) {
int c = pairs[i][0];
for (int j = 0; j < i; j++) {
int b = pairs[j][1];
if (c > b) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
}public class Solution {
public int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[0] - b[0]);
int n = pairs.Length;
int[] dp = new int[n];
Array.Fill(dp, 1);
for (int i = 1; i < n; i++) {
int c = pairs[i][0];
for (int j = 0; j < i; j++) {
int b = pairs[j][1];
if (c > b) dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
return dp[n - 1];
}
}#define MAX(a, b) (a > b ? a : b)
static inline int cmp(const void *pa, const void *pb) {
return (*(int**)pa)[0] - (*(int**)pb)[0];
}
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
qsort(pairs, pairsSize, sizeof(int*), cmp);
int* dp = malloc(sizeof(int) * pairsSize);
for (int i = 0; i < pairsSize; i++) { // memset 不能初始化 0 和 -1 以外的值
dp[i] = 1;
}
for (int i = 1; i < pairsSize; i++) {
int c = pairs[i][0];
for (int j = 0; j < i; j++) {
int b = pairs[j][1];
if (c > b) dp[i] = MAX(dp[i], dp[j] + 1);
}
}
return dp[pairsSize - 1];
}class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](vector<int> a, vector<int> b)->bool {
return a[0] < b[0];
});
int n = pairs.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
int c = pairs[i][0];
for (int j = 0; j < i; j++) {
int b = pairs[j][1];
if (c > b) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
};class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda v:v[0])
n = len(pairs)
dp = [1] * n
for i in range(1, n):
c = pairs[i][0]
for j in range(0, i):
b = pairs[j][1]
if c > b: dp[i] = max(dp[i], dp[j] + 1)
return dp[-1]二分查找 · 排序 · 按 c 升序
var findLongestChain = function(pairs) {
pairs.sort((a, b) => a[0] - b[0])
const n = pairs.length, bs = []
for (let i = 0; i < n; i++) {
const [c, d] = pairs[i]
if (bs.length === 0 || c > bs[bs.length - 1]) {
bs.push(d)
} else {
const i = binarySearch(bs.length - 1, m => bs[m] >= c)
bs[i] = Math.min(bs[i], d)
}
}
return bs.length
};
const binarySearch = (r, cb) => {
let l = 0
while (l < r) {
const m = l + r >>> 1
if (cb(m)) r = m
else l = m + 1
}
return l
}function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[0] - b[0])
const n = pairs.length, bs = []
for (let i = 0; i < n; i++) {
const [c, d] = pairs[i]
if (bs.length === 0 || c > bs[bs.length - 1]) {
bs.push(d)
} else {
const j = binarySearch(bs.length - 1, m => bs[m] >= c)
bs[j] = Math.min(bs[j], d)
}
}
return bs.length
};
function binarySearch(r: number, cb: (number)=>boolean): number {
let l = 0
while (l < r) {
const m = l + r >>> 1
if (cb(m)) r = m
else l = m + 1
}
return l
}class Solution {
function findLongestChain($pairs) {
usort($pairs, function($a, $b) {
return $a[0] >= $b[0];
});
$n = count($pairs);
$bs = [];
for ($i = 0; $i < $n; $i++) {
list($c, $d) = $pairs[$i];
if (count($bs) === 0 || $c > end($bs)) {
$bs []= $d;
} else {
$j = $this->binarySearch(count($bs) - 1, function($m) use($bs, $c) {
return $bs[$m] >= $c;
});
$bs[$j] = min($bs[$j], $d);
}
}
return count($bs);
}
function binarySearch($r, $cb) {
$l = 0;
while ($l < $r) {
$m = $l + $r >> 1;
if ($cb($m)) $r = $m;
else $l = $m + 1;
}
return $l;
}
}
func findLongestChain(pairs [][]int) int {
sort.SliceStable(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
bs := []int{}
for _, pair := range pairs {
c, d := pair[0], pair[1]
if len(bs) == 0 || c > bs[len(bs) - 1] {
bs = append(bs, d)
} else {
j := sort.Search(len(bs), func(m int) bool {
return bs[m] >= c
})
bs[j] = min(bs[j], d)
}
}
return len(bs)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int n = pairs.length;
List<Integer> bs = new ArrayList<Integer>();
for (int[] pair : pairs) {
int c = pair[0], d = pair[1];
if (bs.isEmpty() || c > bs.get(bs.size() - 1)) {
bs.add(d);
} else {
int j = binarySearch(bs.size() - 1, (m) -> bs.get(m) >= c);
bs.set(j, Math.min(bs.get(j), d));
}
}
return bs.size();
}
private int binarySearch(int r, Function<Integer, Boolean> cb) {
int l = 0;
while (l < r) {
int m = l + r >> 1;
if (cb.apply(m)) r = m;
else l = m + 1;
}
return l;
}
}public class Solution {
public int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[0] - b[0]);
List<int> bs = new List<int>();
foreach (int[] pair in pairs) {
int c = pair[0], d = pair[1];
if (bs.Count == 0 || c > bs[bs.Count - 1]) {
bs.Add(d);
} else {
int j = BinarySearch(bs.Count - 1, (m) => bs[m] >= c);
bs[j] = Math.Min(bs[j], d);
}
}
return bs.Count;
}
public int BinarySearch(int r, Func<int, bool> cb) {
int l = 0;
while (l < r) {
int m = l + r >> 1;
if (cb(m)) r = m;
else l = m + 1;
}
return l;
}
}#define MIN(a, b) (a < b ? a : b)
static inline int cmp(const void *pa, const void *pb) {
return (*(int**)pa)[0] - (*(int**)pb)[0];
}
bool cb(int m, int* bs, int* c) {
return bs[m] >= *c;
}
int binarySearch(int r, int* bs, int* c) {
int l = 0;
while (l < r) {
int m = (l + r) >> 1;
if (cb(m, bs, c)) r = m;
else l = m + 1;
}
return l;
}
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
qsort(pairs, pairsSize, sizeof(int*), cmp);
int* bs = malloc(sizeof(int) * pairsSize);
int pb = 0;
for (int i = 0; i < pairsSize; i++) {
int c = pairs[i][0], d = pairs[i][1];
if (pb == 0 || c > bs[pb - 1]) {
bs[pb++] = d;
} else {
int j = binarySearch(pb - 1, bs, &c);
bs[j] = MIN(bs[j], d);
}
}
return pb;
}class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](vector<int> a, vector<int> b)->bool {
return a[0] < b[0];
});
vector<int> bs;
for (vector<int> pair : pairs) {
int c = pair[0], d = pair[1];
if (bs.empty() || c > bs.back()) {
bs.emplace_back(d);
} else {
int j = lower_bound(bs.begin(), bs.end(), c) - bs.begin();
bs[j] = min(bs[j], d);
}
}
return bs.size();
}
};class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda v:v[0])
bs = list()
for pair in pairs:
c, d = pair[0], pair[1]
if len(bs) == 0 or c > bs[-1]: bs.append(d)
else:
j = bisect.bisect_left(bs, c)
bs[j] = min(bs[j], d)
return len(bs)贪心 · 排序 · 按 d 升序
var findLongestChain = function(pairs) {
pairs.sort((a, b) => a[1] - b[1])
const n = pairs.length
let r = 1, b = pairs[0][1]
for (let i = 1; i < n; i++) {
const [c, d] = pairs[i]
if (c > b) {
r++
b = d
}
}
return r
};function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[1] - b[1])
let r = 1, b = pairs[0][1]
const n = pairs.length
for (let i = 1; i < n; i++) {
const [c, d] = pairs[i]
if (c > b) {
r++
b = d
}
}
return r
};class Solution {
function findLongestChain($pairs) {
usort($pairs, function($a, $b) {
return $a[1] >= $b[1];
});
$n = count($pairs);
$b = $pairs[0][1];
$r = 1;
for ($i = 1; $i < $n; $i++) {
list($c, $d) = $pairs[$i];
if ($c > $b) {
$r++;
$b = $d;
}
}
return $r;
}
}func findLongestChain(pairs [][]int) int {
sort.SliceStable(pairs, func(i, j int) bool {
return pairs[i][1] < pairs[j][1]
})
r, b, n := 1, pairs[0][1], len(pairs)
for i := 1; i < n; i++ {
c, d := pairs[i][0], pairs[i][1]
if (c > b) {
r++
b = d
}
}
return r
}class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
int r = 1, b = pairs[0][1], n = pairs.length;
for (int i = 1; i < n; i++) {
int c = pairs[i][0], d = pairs[i][1];
if (c > b) {
r++;
b = d;
}
}
return r;
}
}public class Solution {
public int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[1] - b[1]);
int r = 1, n = pairs.Length, b = pairs[0][1];
for (int i = 1; i < n; i++) {
int c = pairs[i][0], d = pairs[i][1];
if (c > b) {
r++;
b = d;
}
}
return r;
}
}static inline int cmp(const void *pa, const void *pb) {
return (*(int**)pa)[1] - (*(int**)pb)[1];
}
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize){
qsort(pairs, pairsSize, sizeof(int*), cmp);
int r = 1, b = pairs[0][1];
for (int i = 1; i < pairsSize; i++) {
int c = pairs[i][0], d = pairs[i][1];
if (c > b) {
r++;
b = d;
}
}
return r;
}class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](vector<int> a, vector<int> b)->bool {
return a[1] < b[1];
});
int r = 1, b = pairs[0][1], n = pairs.size();
for (int i = 1; i < n; i++) {
int c = pairs[i][0], d = pairs[i][1];
if (c > b) {
r++;
b = d;
}
}
return r;
}
};class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda v:v[1])
r, b, n = 1, pairs[0][1], len(pairs)
for i in range(1, n):
c, d = pairs[i][0], pairs[i][1]
if c > b: r, b = r + 1, d
return r