【算法基础课】一、基础算法（下）｜双指针、位运算、离散化、区间合并

本文主要是介绍【算法基础课】一、基础算法（下）｜双指针、位运算、离散化、区间合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【算法基础课】一、基础算法（下）｜双指针、位运算、离散化、区间合并

---

一、基础算法（下）

1.7 双指针

模板

for (int i = 0, j = 0; i < n; i ++ )
{while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}

常见问题分类：

1. 对于一个序列，用两个指针维护一段区间
2. 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

---

例题

799. 最长连续不重复子序列
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式
第一行包含整数 n。

第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围
$1\le n\le 10^5$

输入样例：
5
1 2 2 3 5
输出样例：
3

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;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 (s[a[i]] > 1) {s[a[j]]--;j++;}res = max(res, i - j + 1);}cout << res << endl;return 0;
}

800. 数组元素的目标和
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

输出格式
共一行，包含两个整数 i 和 j。

数据范围
$数组长度不超过10^5。$
$同一数组内元素各不相同。$
$1\le 数组元素\le 10^9$

输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1

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

1.8 位运算

模板

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

---

例题

801. 二进制中1的个数
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式
第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围
$1\le n\le 100000,$
$0\le 数列中元素的值\le 10^9$

输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2

#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);  // 每次减去x的最后一位1res++;}cout << res << " ";}return 0;
}

1.9 离散化

模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}

---

例题

802. 区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围
$-10^9\le x\le 10^9,$
$1\le n,m\le 10^5,$
$-10^9\le l\le r\le 10^9,$
$-10000\le c\le 10000$

输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5

#include <iostream>
#include <algorithm>
#include <vector>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, 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(make_pair(x, c));alls.push_back(x);}for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;query.push_back(make_pair(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 (int i = 0; i < add.size(); i++) {int x = find(add[i].first);a[x] += add[i].second;}// 预处理前缀和for (int i = 1; i <= alls.size(); i++) {s[i] = s[i - 1] + a[i];}// 处理询问for (int i = 0; i < query.size(); i++) {int l = find(query[i].first), r = find(query[i].second);cout << s[r] - s[l - 1] << endl;}return 0;
}

1.10 区间合并

模板

// 将所有存在交集的区间合并
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;
}

例题

803. 区间合并
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
$1\le n\le 100000,$
$-10^9\le li\le ri\le 10^9$

输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 100010;int n;
vector<PII> segs;void merge(vector<PII> &segs) {vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (int i = 0; i < segs.size(); i++) {if (ed < segs[i].first) {if (st != -2e9) res.push_back({st, ed});st = segs[i].first, ed = segs[i].second;} else {ed = max(ed, segs[i].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() << endl;return 0;
}

这篇关于【算法基础课】一、基础算法（下）｜双指针、位运算、离散化、区间合并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---