[蓝桥杯刷题]合并区间、最长不连续子序列、最长不重复数组长度

前言

?Hello!这里是欧_aita的博客。
?今日语录: 成功的关键在于对目标的持久追求。
?个人主页：欧_aita
ψ(._. )>?个人专栏：
数据结构与算法
数据库

合并区间问题📕

现实应用

• 合并重叠区间： 将给定的一组区间合并成尽可能少的不相交或相邻的区间。
• 区间调度： 在一系列任务或活动中，每个任务有一个开始时间和结束时间，选择尽可能多的任务而不相互冲突。
• 时间区间问题： 处理一系列时间区间，例如查找某个时间点同时发生的事件。
• 日程安排： 对一组日程进行调度，以确定可以安排多少个活动而不冲突。

大致思路

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

// 区间合并后的区间个数
// 1. 按区间左端点排序
// 2. 左端点st 右端点ed

void merge(vector<PII>& segs) {
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back(make_pair(st, ed));
            st = seg.first, ed = seg.second;
        } else
            ed = max(ed, seg.second);

    if (st != -2e9) res.push_back(make_pair(st, ed));

    // 用合并后的区间更新原始向量
    segs = res;
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

代码讲解

sort(seg.begin(),seg.end());

这里的排序是通过vector数组中的pair数组中的first数据元素大小判断的。

最长不连续子序列📕

代码实现

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str[1000];

    cout << "Enter a string: ";
    fgets(str, sizeof(str), stdin);

    int n = strlen(str);

    for (int i = 0; str[i]; i++) {
        int j = i;
        while (j < n && str[j] != ' ') {
            j++;
        }

        // 输出提取的单词
        for (int k = i; k < j; k++) {
            cout << str[k];
        }

        cout << endl;

        i = j;
    }

    return 0;
}

代码讲解

for (int i = 0; str[i]; i++) {
        int j = i;
        while (j < n && str[j] != ' ') {
            j++;
        }

        // 输出提取的单词
        for (int k = i; k < j; k++) {
            cout << str[k];
        }

        cout << endl;

        i = j;
    }

注意for循环的末端，将子序列的最后一个字符下标赋给了i，然后在for循环中i又+1就是下一个空格或者末端的位置

fgets(str, sizeof(str), stdin);：使用fgets函数从标准输入中读取用户输入的字符串，并存储到str数组中。sizeof(str)确保不会超出数组的边界。

滑动窗口求最长不重复子序列的长度📕

大致思路

在这个过程中不断计数，求取最长不重复数组长度。

代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];

    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}