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

2023-12-15 22:45:30

前言

在这里插入图片描述

?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;
}

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_74939592/article/details/135024605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。