双指针/位运算/离散化/区间和并
-
双指针
- 两个指针指向两个不同的序列
- 两个指针指向同一个序列（归并排序，快速排序）
- 主要作用：将暴力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); //返回答案到原数组 } }