双指针算法
核心思想:
将朴素二重循环优化到O(n)
模板
for(i = 0,j = 0;i<n;i++)
{
while(j<n && check(i,j))
{
j++;
}
//然后这里是每道题目的具体逻辑
}
例题
把一句话中每个单词逐行输出。
//提取一句话中的每一个单词逐个输出
#include <bits/stdc++.h>
using namespace std;
int main()
{
char str[1000];
cin.getline(strsd,1000);
int n = strlen(str);
for(int i = 0;i<n;i++)
{
int j = i;
while(j<n && str[j]!=' ') j++; //(模板),每次j在空格处停下
//这道题的具体逻辑
for(int k = i;k<j;k++)
{
cout<<str[k];
}
cout<<endl;
i = j; //再进行循环,i++,刚好指向下一个单词首字母
}
return 0;
}
//本题用数组来记录某个数在区间内出现的次数,只能用于数据范围小的情况
//学了哈希表之后用哈希表更好
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int res;
int a[N],s[N]; //a[N]存数组,s[N]记录某个数在区间内出现次数
int main()
{
cin>>n;
for(int i = 0;i<n;i++) cin>>a[i];
for(int i = 0,j = 0;i<n;i++) //枚举区间结束位置i
{
s[a[i]]++; //当i指向一个新的数,即区间内把这个数包含了,出现次数要+1
while(j<=i && s[a[i]]>1) //代表区间内有重复数字
{
s[a[j]]--; //j往后挪,原本指向的数就被提出[j,i]区间了
j++; //j是单调往后挪的,随着i往后,j要不不动要不往后,不可能往前
}
//退出循环时,j是处于满足区间没有重复数字的离i最远的位置
res = max(res,i-j+1); //每次遍历到一个新的i,都会对应一个最优的j,都会有一个res,看看这么多个i哪个是最长的区间
}
cout<<res<<endl;
return 0;
}
双指针算法的思路
先写一个暴力解法,然后观察枚举的时候i和j之间有没有什么单调关系,然后套一下双指针的模板,
使得时间复杂度降为O(n);
位运算常用操作
1. n的二进制表示中,第k位是什么
做法:
- 先把第k位移到最后一位 n>>k
- n&1
- 合二为一: (n>>k)&1
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n = 10;
//把10的二进制的每一位输出来(先输出高位)
for(int k = 3;k>=0;k--)
{
cout<<(n>>k&1)<<endl;
}
return 0;
}
2. lowbit(x) :返回x的最后一位1
例如:
x = 1010 lowbit(x) = 10
x = 101000 lowbit(x) = 1000
lowbit()的工作原理:x & -x
因为 -x = x取反+1 = ~x+1,所以lowbit(x) = x&(~x+1)
lowbit(x)的应用:统计二进制数中1的个数
#include <bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
return x&-x;
}
int main()
{
int n;
cin>>n;
int res;
while(n--)
{
int x;
cin>>x;
res = 0;
while(x)
{
x-=lowbit(x); //每次减去x的最后一位1
res++; //直到x为0跳出循环,能减多少次就有多少个1
}
cout<<res<<' ';
}
return 0;
}
离散化
离散化的含义:当有一组整数,值域非常大但是个数非常少,即很稀疏。我们可以保序地将其映射到从0(或1)开始的连续下标中。
注意
1. 可能有重复元素,需要去重
2. 如何算出每个下标离散后的新下标————二分法
3.
vector<int> alls; //存储所有待离散化的稀疏下标
sort(alls.begin(),alls.end()); //将这些下标排序
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去重
unique的作用是把数组a中特定部分的重复多余元素全摘出来放到该数组的最后面,并返回这些重复元素的第一个位置。
erase的作用是去除数组中某部分的元素。
这样搭配使用,实现去重。
//二分求出x对应的离散化的值(已经排好序了,可以用二分)
int find(int x)
{
int l = 0;
int 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开始.否则从0开始,根据实际需要选择
}
例题:区间和(原题链接)
离散化的思想:把所有用到的下标存到一个数组alls里,排个序,去个重,再映射到连续下标上
/*这题的范围是−10^9≤x≤10^9,但他每次对一个下标的数进行+c,就算每次操作的数都不一
样,也最多只能操作10^5个数接下来。然后m次查询[l,r],就算这m次的l各不相同,r各不
相同,也不与之前用过的n个(10^5)坐标相同,一通操作下来最多只有3*10^5个下标会被
访问,与2*10^9的值域差太远了,太稀疏了,所以我们用离散化。
把原坐标轴上的数保序映射到从1开始的连续下标上(从1开始是因为要用前缀和),映射
之后,值域就变成了1~300000,就可以用前缀和来解决了
然后访问[l,r]也是把l和r先转换成离散化映射后的kl和kr再运用前缀和公式
*/
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 300010;
int n,m;
int a[N],s[N]; //a数组是存离散化后的结果,s是前缀和
vector<int> alls; //vector用来存所有要离散化的值
vector<PII> add,query; //代表第一个操作赋值和第二个操作求区间和
int find(int x) //求x离散化后映射到的下标
{
int l = 0; //alls是从0开始到alls.size() - 1 的
int r = alls.size()-1; //映射的是1~alls中元素个数的下标范围,(要前缀和所以1开始)
while(l<r)
{
int mid = l+r >> 1;
if(alls[mid]>=x) r = mid;
else l = mid + 1;
}
return r + 1; //因为我们要映射到的是从1开始的,所以这里+1
}
int main()
{
cin>>n>>m;
for(int i = 0;i<n;i++)
{
int x,c; //在下标为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());
//处理插入add,对add操作用到的坐标映射新坐标
for(auto item : add) //遍历vector<PII> add
{
int new_x = find(item.first); //x离散化后就是new_x
a[new_x] += item.second; //即c
}
//预处理前缀和
for(int i = 1;i<=alls.size();i++)
{
s[i] = s[i-1] + a[i];
}
//处理询问query,对query操作用到的坐标映射新坐标
for(auto item : query)
{
int new_l = find(item.first);
int new_r = find(item.second);
cout<<s[new_r] - s[new_l - 1]<<endl;
}
return 0;
}