Keshawn_lu's Blog

Leetcode 646. 最长数对链

贪心
字数统计: 318阅读时长: 1 min
2022/09/03 Share

题目简介：

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例：

1
2
3
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]

提示：

  • 给出数对的个数在 [1, 1000] 范围内。

思路：

注意是任意顺序，所以可以使用贪心，每次找最小的数，然后以此类推。

所以首先对数组进行排序，然后依次遍历即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool cmp(vector<int>& a, vector<int>& b){

    return a[1] < b[1];
}

class Solution {
public:

    int findLongestChain(vector<vector<int>>& pairs) {

        sort(pairs.begin(), pairs.end(), cmp);

        int res = 1;
        int min = pairs[0][1];	//保存遍历到的最小值
        for(int i = 1; i < pairs.size(); i++){

            if(pairs[i][0] > min){

                res++;
                min = pairs[i][1];
            }
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网