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

前言

⭐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 右端点edvoid 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;} elseed = 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;
}