双指针/位运算/离散化/区间和并-Toy模板网

这篇具有很好参考价值的文章主要介绍了双指针/位运算/离散化/区间和并。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

双指针

两个指针指向两个不同的序列
两个指针指向同一个序列（归并排序，快速排序）
主要作用：将暴力O(n^2)遍历通过两个指针的某种单调性质优化到O(n)，也就是说将内层循环变量j通过与外层循环变量i的关系，将内层循环次数降低不定次

模板：

for(int i = 1; i < n; ++ i){
	while(j < i && check(i, j)) j ++ ;
	//内部逻辑具体分析
}

//例如将一个字符串中的单词按行输出
str = "acv adf wers";
int len = strlen(str);
//双指针算法
for(int i = 0; i < len; ++ i){
	int j = i;
	while(j < len && str[j] != ' ') j ++ ;
	
	//内部逻辑具体分析
	//输出单词
	for(int k = i; k < j; ++ k) cout << str[k];
	cout << endl;
	int i = j;
}

位运算
- 常用操作：
  - 求n的二进制的第k位：
    - 将n右移k位 (n >> k)
    - 再取右移k位后的个位 (n >> k) & 1
  - 返回x的二进制中最后一位1的位置：
    - lowbit(x) = x & -x lowbit(x)的二进制中只有一个1，该1就是x的二进制中的最后一位1
    - -x = ~x + 1 补码为反码加一
  - 求n的二进制中1的个数：
    - while(n) n -= lowbit(n), ans++;
    - 当n不为0时，n每次去掉最后一位1，ans即为n的二进制中1的数量

离散化

将无限区间中的有限元素映射到有限的区间中，将稀疏空间变得稠密
不改变元素间的相对位置

模板：

vector<int> alls;//离散化数组
sort(alls.begin(), alls.end()); //排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
//根据原值查找离散化后的下标
int find(int x){
	int l = -1, r = alls.size();
	while(l + 1 < r){
		int mid = l + r >> 1;
		if(alls[mid] >= x) r = mid;
		else l = mid;
	}
	return r + 1; //以1作为起点下标
}
//unique函数双指针实现
//在不递减的数列中快速提取出不重复的数
vector<int>::iterator unique(vector<int> &a){
	for(int i = 0, j = 0; i < a.size(); ++ i){
		if(!i || a[i] != a[i - 1]) //要么是第一个数，要么前一个数不同于后一个数
			a[j ++ ] = a[i]; //a[0] ~ a[j - 1] 是所有不同的数
	}
	return a.begin() + j;
}

区间和并

把有有交集的区间合并
将所有区间按左端点从升序排列
遍历所有区间，每次比较相邻两区间是否相交，若前面区间的右端点严格小与后面区间的左端点即为不相交，否则相交
若两区间相交就取并集，否则得到一个合并完成的区间，更新维护的区间，进行下一次合并

模板：

typedef pair<int, int> PII; 
vector<PII> segs; //存储不同区间
//合并区间的函数
void merge(vector<PII> &segs){
	vector<PII> res; //存储答案区间
	sort(segs.begin(), segs.end()); //默认按first升序排序
	int st = -inf, ed = -inf; //维护的区间初始化
	for(auto seg : segs){ //遍历所有区间
		if(ed < seg.first){ //如果维护的区间与新区间不相交说明维护的区间已经合并完成
			if(st != -inf) res.push_back({st, ed}); //将合并完成的区间存储
			st = seg.first, ed = seg.second; //更新维护的区间
		}else ed = max(ed, seg.second); //否则取交集
		if(st != -inf) res.push_back({st, ed}); //所有区间合并成为一整个区间的情况
		swap(res, segs); //返回答案到原数组
	}
}

文章来源地址https://www.toymoban.com/news/detail-605584.html

到了这里，关于双指针/位运算/离散化/区间和并的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！