巴中网站建设培训班,创建网站容易吗,贵州网站建设营销公司哪家好,wordpress加qq和微信插件下载前言 ⭐Hello!这里是欧_aita的博客。 ⭐今日语录: 成功的关键在于对目标的持久追求。 ⭐个人主页#xff1a;欧_aita ψ(._. )⭐个人专栏#xff1a; 数据结构与算法 数据库 文章目录 前言合并区间问题#x1f4d5;现实应用大致思路代码实现代码讲解 最长不连续子序列欧_aita ψ(._. )⭐个人专栏 数据结构与算法 数据库 文章目录 前言合并区间问题现实应用大致思路代码实现代码讲解 最长不连续子序列代码实现代码讲解 滑动窗口求最长不重复子序列的长度大致思路代码实现 合并区间问题
现实应用 合并重叠区间 将给定的一组区间合并成尽可能少的不相交或相邻的区间。区间调度 在一系列任务或活动中每个任务有一个开始时间和结束时间选择尽可能多的任务而不相互冲突。时间区间问题 处理一系列时间区间例如查找某个时间点同时发生的事件。日程安排 对一组日程进行调度以确定可以安排多少个活动而不冲突。 大致思路 代码实现
#include iostream
#include vector
#include algorithm
using namespace std;typedef pairint, int PII;const int N 100010;int n;
vectorPII segs;// 区间合并后的区间个数
// 1. 按区间左端点排序
// 2. 左端点st 右端点edvoid merge(vectorPII segs) {vectorPII 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 cstringusing 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 cstringusing 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;
}
