当前位置 博文首页 > 广大菜鸟的博客：算法学习（四）双指针算法/位运算/离散化/区间
案例：
#include<iostream>
using namespace std;
int main() {
char str[1000];
gets_s(str);
int n = strlen(str);
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && str[j] != ' ') j++;
for (int k = i; k < j; k++) cout << str[k];
cout << endl;
i = j;
}
}
#include<iostream>
using namespace std;
/*
输入样例：
5
1 2 2 3 5
输出样例：
3
*/
const int N = 100010;
int a[N], s[N] ,n;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i]; // 1-1000000
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;
}
求n的第k位数字：n>>k &1
返回n的最后一位1：lowbit(n) = n & -n
#include<iostream>
using namespace std;
// 问题：n的二进制表示中第k位是几
// n =(1111)(2)
int main() {
int n = 10;
for (int k = 3; k >= 0; k--)
cout << (n >> k & 1); // 输出1010
}
#include<iostream>
using namespace std;
//返回n的最后一位1：lowbit(n) = n & -n
int lowbit(int n) {
return n & -n;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
int res = 0;
while (x)
x -= lowbit(x), res++;
cout << res << " ";
}
}
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小，离散化仅适用于只关注元素之间的大小关系而不关注元素本身的值!
工作：
1、排序
2、去重
3、索引
/*
vector<int>alls; //存储所有待离散化的值
sort(alls.begin(),alls.end());// 将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去掉重复元素
*/
解释测试样例：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int>PII;
// 值域 0 - 10^9，格数10^5
/*
vector<int>alls; //存储所有待离散化的值
sort(alls.begin(),alls.end());// 将所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去掉重复元素
*/
/*
-10^9<=x<=10^9
1<=n,m<=10^5
-10^9<=l<=r<=10^9
-100000<=c<=100000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
*/
const int N = 300010; // 插入总数10万个，查询总数10万个
int a[N], s[N];
int n, m;
vector<int>alls; //存储所有待离散化的值
vector<PII>add, query;
// 二分求出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
}
int main() {
cin >> n >> m;
for(int i=0;i<n;i++) { //每行包括2个整数x和c,x的位置加上c
int x, c;
cin >> x >> c;
add.push_back({ x,c });
alls.push_back(x);
}
for(int i=0;i<m;i++){ //每行包括2个整数l和r，返回l到r区间的和
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;
}
}
可以替换
alls.erase(unique(alls.begin(), alls.end()), alls.end());
为
unique(alls);
vector<int>::iterator unique(vector<int>& a) {
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (!i || a[i] != a[i - 1]) {
a[j++] = a[i];
}
}
// a[0] - a[j-1]，所有a中不重复的数
return a.begin() + j;
}
https://leetcode-cn.com/problems/merge-intervals/
首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
