Acwing算法基础课学习笔记(三)--基础算法之双指针算法 && 位运算 &&离散化 &&区间合并

最长连续不重复子序列

双指针算法的核心在于优化，通常把$O(n^2)$优化成了$O(n)$。而且之前的快排和归并其实也用了双指针的思想。 根据观察发现，当使用i,j两个快慢指针表示当前的指针移动到i的最长不重复序列时候，具有单调性，即i向后移动，j必然向右或者不动，不可能向左移动，这一单调性质导致可以使用双指针算法。 在双指针算法中，一个指针扫描整个数组而移动，关键如何找到对应的另一个指针移动的位置，在本题中，我们定义i为块指针，j为慢指针，j的位置定义为i对应的最长不重复序列的j的位置，因为不重复,i和j元素都不重复，出现次数都为一，因此我们使用一个数组s来记录各个元素出现的次数，i,j不断移动，数组及时更新，每次i更新，便更新j确保j,i区间元素都只出现一次：

#include <iostream> using namespace std; const int N = 100010; int n; int a[N], s[N]; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &a[i]); int res = 0; for(int i = 0, j = 0; i < n; i++) { s[a[i]]++; while(j < i &&s[a[i]] > 1) { s[a[j]]--; j++; } res = max(res, i - j + 1); } printf("%d", res); return 0; }

数组元素的目标和

其实就是leetcode第一题：两数之和。当我们学了哈希表之后可以更快的去做，上面的一题也是可以用哈希表的，这里依然用双指针的方法：

#include <iostream> using namespace std; const int N = 100010; int n, m, x; int a[N], b[N]; int main() { scanf("%d %d %d", &n, &m, &x); for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(int j = 0; j < m; j++) scanf("%d", &b[j]); for(int i = 0,j = m -1; i < n; i++) { while(j >= 0 && a[i] + b[j] > x) j--; if(j >= 0 && a[i] + b[j] == x) printf("%d %d\n",i, j); } return 0; }

二进制中1的个数

位运算的非常经典的一道题，剑指offer上也是有这一题的。 位运算最常用的两种操作

求n的二进制表示中第k位数字：n >> k & 1

返回n的最后一位1：lowbit(n) = n & -n

#include <iostream> using namespace std; int main() { int n; cin >> n; while(n --) { int x, res = 0; cin >> x; while(x) { x = x & (x - 1); res++; } cout << res << " " ; } }

lowbit的解法：

#include<iostream> using namespace std; int lowbit(int x){ return x&(-x); } int main(){ int n; cin>>n; while(n--){ int x; cin>>x; int res=0; while(x) x-=lowbit(x),res++; cout<<res<<' '; } return 0; }

区间和

本题需要用到离散化，为什么要离散化呢，因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，第二个原因，本文是数轴，要是采用下标的话，可能存在负值，所以也不能，所以有人可能会提出用哈希表，哈希表可以吗？答案也是不可以的，因为哈希表不能像离散化那样缩小数组的空间，导致我们可能需要从1-e9遍历到1e9（此处的含义就是假如我们需要计算1e-9和1e9区间内的值，那我们需要从前到后枚举，无论该值是否存在），因为哈希表不能排序，所以我们一般不能提前知道哪些数轴上的点存在哪些不存在，所以一般是从负的最小值到正的最大值都枚举一遍，时间负责度太高，于是就有了本题的离散化。

离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

其实映射最大的难点是前后的映射关系，如何能够将不连续的点映射到连续的数组的下标。此处的解决办法就是开辟额外的数组存放原来的数组下标，或者说下标标志，本文是原来上的数轴上的非连续点的横坐标。 此处的做法是是对原来的数轴下标进行排序，再去重，为什么要去重呢，因为本题提前考虑了前缀和的思想，其实很简单，就是我们需要求出的区间内的和的两端断点不一定有元素，提前加如需要求前缀和的两个端点，有利于我们进行二分搜索，其实二分搜索里面我们一般假定有解的，如果没解的话需要特判，所以提前加入了这些元素，从而导致可能出现重复元素。

本文你用于存储这个关系的数组是alls[N];特地说明下，为什么要开300000+10呢，因为我前面说过了提前考虑了前缀和的因素，加上了2*m个点，又因为怕出现数组越界，多加了10。什么时候会用完300000个空间呢，那就是无重复元素，外加n和m都是1e5次方的打下。

下一步就是写提前数轴点对应的映射后的数组的下标的函数课，此题用的是二分，$log(n+2\ast 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; }

为什么返回r + 1,这是变相的让映射后的数组从1开始。此处描述映射后的数组下标对应的数值用的是a数组。

剩下的就是已经讲过的了，前缀后算法，本题的难点是理清楚这个映射关系。

完整代码如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; vector<int> alls; vector<PII> add; vector<PII> query; 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 = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({ x, c }); alls.push_back(x); } for (int i = 0; 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 x = find(item.first); a[x] += 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; }

区间合并

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; 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 (st != -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() { int n; cin >> n; vector<PII> segs; 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; }