📟作者主页:慢热的陕西人
🌴专栏链接:C++算法
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
主要讲解了双指针,位运算,离散化以及区间合并。
Ⅴ. 双指针
是一种利用单调规律将二重循环的时间复杂度降为O(N)的算法;
例如:剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣(LeetCode)
如果我们用暴力算法的话,肯定是需要O(N)的复杂度,但是我们采用双指针方式可以实现在O(N)的时间复杂度实现
代码:
int lengthOfLongestSubstring(string s) { int map[257] = { 0 }; int res = 0; for(int i = 0; i < s.size(); ++i) { map[s[i]]++; while(map[s[i]] > 1) { map[s[j]]--; ++j; } res = max(res, i - j + 1); } return res; }
Ⅵ. 位运算
位运算通常是利用二进制的一些性质展开的
例如:剑指 Offer 15. 二进制中1的个数 - 力扣(LeetCode)
class Solution { public: uint32_t lowbit(uint32_t x) { return (x & ~x + 1); } int hammingWeight(uint32_t n) { int sum = 0; while(lowbit(n)) n &= ~lowbit(n), sum++; return sum; } };
其中
lowbit(n)
函数返回的是n
的第一个1的数字:例如5(101),他就返回1;
Ⅶ.离散化:
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小
有时候我们的数据范围是
(0 , 10e9)
,但是数据的总数却可能只有(0, 10e5)
, 这时候我们没必要去开10e9
的空间,只需要开最大10e5
的空间所要离散化的数据映射到这个小空间里;例如;{1000, 1111, 1200, 1100, 1250}
我们映射下来
[ 1000 − > 1 ] , [ 1100 − > 2 ] , [ 1111 − > 3 ] , [ 1200 − > 4 ] , [ 1250 − > 5 ] [1000->1],[1100->2],[1111->3],[1200->4],[1250->5] [1000−>1],[1100−>2],[1111−>3],[1200−>4],[1250−>5]
所以我们要实现离散化需要做非常重要的两步:①如何将离散化后的数据进行去重;
②如何计算出数据离散化后对应的值;
代码如下:
vector<int> alls;//存储待离散化的数据 sort(alls.begin(), alls.end());//排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); //①对排列好的数据进行去重 //②计算出数据离散化后对应的值 int find(int x) { int l = 0; r = alls.size() - 1; while(l < r) { int mid = (l + r) >> 1; if(alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1;//根据题意 }
例题:
测试数据:
//输入 3 3 1 2 3 6 7 5 1 3 4 6 7 8 //输出 8 0 5
代码:
#include<iostream> #include<vector> #include<algorithm> #define N 300010 using namespace std; typedef pair<int, int> PII; int a[N], s[N]; vector<int> alls; vector<PII> add, query; int n, m;//n次操作, m个区间 int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; } int main() { cin >> n >>m; for (int i = 1; i <= n; ++i) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 1; i <= m; ++i) { int l, r; cin >> l >> r; query.push_back({ l, r }); alls.push_back(l); alls.push_back(r); } //去重操作 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); //处理加数 for (auto item : add) { int pot = find(item.first); a[pot] += item.second; } //计算前缀和 for (int i = 1; i <= alls.size(); ++i) s[i] = s[i - 1] + a[i]; //处理请求 for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }
Ⅶ. 区间合并
给定多个区间,然后将有交集的区间合并(取并集);
处理如下图的功能:
实现的思路步骤;
①先利用以区间的左端点为标准排序所有的区间。
②合并:
(1)先将第一个区间的端点作为标准
st
和end
;(2)开始遍历后面的区间:
如果区间的左端点小于标准
end
并且右端点小于标准的end
那么就不用进行操作,直接遍历下一个区间; 如果区间的左端点小于标准
end
并且右端点大于标准的end
那么我们就更新标准的end
为当前的区间的右端点; 如果区间的左端点大于标准的
end
那么我们将当前的标准存储起来(已经称为一个合并后的区间),并且开始从(1)开始执行。代码:
#include<iostream> #include<vector> #include<algorithm> using namespace std; #define N 100010; typedef pair<int, int> PII; int n; vector<PII> segs; 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 (ed != -2e9) res.push_back({ st, ed });//已经满足合并区间的条件,所以将这个区间存储起来 st = seg.first, ed = seg.second; //即将开始合并新的区间,要将第一个区间的端点作为标准 } else ed = max(ed, seg.second); //判断合并区间的右端点 if (st != -2e9) res.push_back({ 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(); return 0; }
到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话,可以点赞,收藏,顺便关注一下!
如果文章内容有错误,欢迎在评论区指正文章来源:https://www.toymoban.com/news/detail-602511.html
文章来源地址https://www.toymoban.com/news/detail-602511.html
到了这里,关于C++基础算法离散化及区间合并篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!