双指针算法、位运算、离散化、区间合并

双指针算法

①指向两个序列 把两个有序序列合并      归并排序

②指向一个序列 两个指针维护一个区间  快速排序

如果用暴力做法，需要把 i，j 都从 0→n 循环一遍  O( n^2 )

所有双指针算法的时间复杂度都是 O(n) 用两个指针扫描一个序列， 每一个指针在所有循环中总共移动的次数不超过 n，两个指针总共移动的次数不超过 2n  O( n )

从中挖掘出某些性质，把 O( n^2 ) 的时间复杂度优化为 O( n )

 

//i整个扫描一遍
for(int i = 0,j = 0;i < n;i++ )
{
    //每次i更新后更新j-> 1.j在i的范围内 2.只要满足某种性质j++
    while(j < i && check(i,j)) j++;
    //题目的具体逻辑
}

输入一个字符串，把其中的每个单词输出：输入字符串中的每个单词用空格隔开，输出的每个单词各占一行

假定字符串的开头没有空格，并且每两个单词之间只有一个空格

#include
#include

using namespace std;

int main()
{
    //读入字符串
    char str[1000];
    gets(str);
    //用n来表示字符串的长度
    int n = strlen(str);

    //第一个指针从0开始一直枚举到结束为止
    for(int i = 0;i < n;i++ ){
        //每次i循环时保证i指向单词的第一个位置-> j要找到单词的最后一个位置-> j从i开始往后扫描 直到扫描到空格为止
        int j = i;
        //只要j没有走到终点 & 不是空格
        while(j < n && str[j] != ' ') j++;
        //循环结束后j指向空格-> 此时从 i 到 j - 1 的所有字母就是当前单词的所有字母
        
        //题目的具体逻辑
        //把当前单词输出
        for(int k = i;k < j;k++ ) cout << str[k];

        //输出回车-> 每个单词占一行
        cout << endl;

        //当前层循环结束后让i指向j 跳过整个区间-> i指向空格-> i++就指向下一个单词
        i = j;
    }
    return 0;
}

最大连续不重复子序列

先枚举终点再枚举起点， check 从 j ~ i 条件是否满足，如果满足则更新答案，取 max(res，从 j 到 i 一共有多长)

红色是 i，绿色是 j，i 、j 具有单调性

注意不能直接去重，因为是连续的一段 (去重后可能就不连续了)

绿色指针最左能到什么位置，使得绿色指针和红色指针之间是没有重复数字的

数据很大、不开数组判重的方法：使用哈希表

先使用暴力做法，然后看数据有没有单调关系，有单调关系就利用单调关系把 O( n^2 ) 的复杂度变成 O(n)

1 2 2 3 5 中最长的不包含重复数字的子序列为 2 3 5

当 i 指向第一个数 1，j 指向 1，当 i 指向第二个数 2，j 还是指向 1(前两个没有重复数字)，当 i 指向第三个数 2，j 只能指向同一个数字(当 i 指向第三个数的时候，j 不管是指向 1 还是 2 都有重复数字，因此 j 只能和 i 指向同一个位置) . . . 

随着红色指针往后移动，绿色指针一定也是往后移动的，不会往前移动→ 只枚举 i，j 每次看一下要不要往后走：check( j，i )，判断 j ~ i 之间有没有重复元素，如果有重复元素就把 j ++，直到 j 和 i 之间没有重复元素为止，最后得到以 i 为右端点，j 为左端点最远在什么地方，对于所有的 j 求出最大值就是答案

题目数据范围比较小：在 0~10w 范围内，可以考虑直接开一个数组 s[ N ]，动态记录一下当前区间中每个数出现多少次

如果 i 往后移动一格，相当于在区间中加入了一个新的数 s[ a[ i ] ] ++

如果 j 往后移动一格，就说明 [ j，i ] 区间中有一个数出去了 s[ a[ j ] ] - -，就可以动态统计区间中有多少个数

前一个 i 结束的时候，对应的 [ i，j ] 区间中是没有重复元素的，如果新加入的 i 导致区间中出现了重复的元素，那么 a[ i ] 就是重复的元素

check( aj ≠ ai)   j 往后走的时候一定要把 a[ i ] 的值去掉一个才可以

#include
using namespace std;

const int N = 100010;

//原来的数
int a[N];
//当前j~i区间每一个数出现的次数->计数器
int s[N];
int main()
{
    cin >> n;
    //读入n个数
    for(int i = 0;i < n;i++ ) cin >> a[i];
    //答案
    int res = 0;
    //每一次加入一个新的数-> a[i]
    for(int i = 0,j = 0;i < n;i++ ) {
        s[a[i]]++;
        //j <= i一定满足,如果 j > i 区间中一个数都没有 一定不会有重复的数
        //新加入的数有重复,重复的数就是a[i]
        while(s[a[i]] > 1){
            s[a[j]]--;
            j++;
        }
        //循环结束后j~i之间就没有重复元素更新答案
        res = max(res,i - j + 1);
    }
    cout << res << endl;
    return 0;
}

位运算

求一个整数 n 的二进制表示中第 k 位是几？

k 的下标如图所示，个位是第 0 位，十位是第 1 位 . . .

10 的二进制表示：1010，右移 3 位就是把最高位移到个位

#include
using namespace std;

int main()
{
    int n = 10;
    //从最高位开始 依次把 n 的各个位数输出
    for(int k = 3;k >= 0; k-- ) cout << (n >> k & 1); 
    return 0;
}

/*输出*/

1010

lowbit(x)

数状数组的基本 *** 作

返回的是一个二进制数，这个二进制数的最高一位 1，就是 x 的最后一位 1

一个整数的负数是原数的补码，补码 = 取反 + 1

统计 x 中 1 的个数→ 每次把 x 的最后一位 1 去掉，当 x = 0 的时候，里面就没有 1 了，减了多少次，就说明 x 中有多少个 1

二进制中 1 的个数

 

#include
using namespace std;

int  lowbit(int x)
{
    return x & -x;
}
int  main()
{
    int n;
    //读入 n 个数
    cin >> n;
    while(n-- )
    {
        //每次读入一个 x
        int x;
        cin >> x;
        //统计 x 中 1 的个数
        int res = 0;
        //当 x != 0 每次把 x 的最后一位 1 减去 减了多少次就说明 x 中有多少个 1 
        while(x) x -= lowbit(x),res ++ ;
        cout << res << ' ';
    }
    return 0;
}

 原码、反码、补码

为什么计算机中的负数不直接用反码来表示，而是用补码来表示？

计算机底层实现是没有减法的，因此要用加法来做减法，负数的性质：x + ( - x ) = 0

#include
using namespace std;

int main()
{
    int n = 10; 
    //-n的二进制表示-> 先转换为无符号整数 从最高位开始输出
    unsigned int x = -n;
    for(int i = 31;i >= 0;i-- ) cout << (x >> i & 1);
}
 10: 000...01010  
-10: 111...10110

离散化

特指整数的离散化、保留顺序的离散化

给出一些数值，数值的范围比较大：0 ~ 10^9，个数比较少：10^5 个数

题目需要以这些数值为下标来进行求解，不能开一个 10^9 的数组，需要把给出的数值映射到从 0 开始的连续自然数

把 1 映射到 [ 0 ]，把 3 映射到 [ 1 ]，把 100 映射到 [ 2 ]，把 2000 映射到 [ 3 ]，把 50000 映射到 [ 4 ] 的过程就被称为离散化

注意：a 数组是有序的，离散化的过程就把 x 映射到下标，找 x 这个值在 a 数组中的下标可以用二分法

由于 a 数组可能有重复元素，需要去重

C++中erase函数的使用,可以用来删除内存擦除_dic56858的博客-CSDN博客

unique 函数 详解_生于忧患，死于安乐2017的博客-CSDN博客_unique函数

//将所有的值排序
sort(alls.begin(),alls.end());
//去掉重复元素
alls.erase(unique(alls.begin(),alls.end()),alls.end());

从 0 到数组 n - 1，二分法找 x 的位置

//从左往右找第一个大于等于 x 的位置
int find(int x)
{
    int l = 0,r = all.size() -1;
    while(l < r)
    {
        int mind = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    //返回位置的下标+1 从1开始映射到n
    return r + 1;  
 }

给出一个无限长的数轴，起初数轴上所有点上的数都是 0，现在有 n 个 *** 作，每次选择一个下标，把下标上的数 x 加上 c，第一次把下标为 100 位置上加上 50，第二次把下标为 100 位置上加上 20. . . *** 作之后有 n 次询问，每次询问 l 和 r 之间的所有数的和，假设要询问 - [ 1000 ] ~ [ 1000 ] 所有数的和：和为 70

示例：

有 3 次 *** 作：第 1 次把下标为 1 的位置加上 2，第 2 次把下标为 3 的位置加上 6，第 3 次把下标为 7 的位置加上 5

有 3 次询问：第 1 次问 [ 1 ] ~ [ 3 ] 所有数的和：和为 8，第 2 次问 [ 4 ] ~ [ 6 ] 所有数的和：和为 0，第 3 次问 [ 7 ] ~ [ 8 ] 所有数的和：和为 5

如果数据的范围比较小，可以用前缀和算法：前缀和、差分_菜徐鸭的博客-CSDN博客

题目给出的数据范围比较大：- 10^9 ~ 10^9，但是涉及的数的个数很少、值域跨度很大但是里面的数很稀疏，只需要用到它们之间的相对关系，每次求所有数的和，其实只要求 L ~ R 之间所有数的和，与每个值的绝对大小无关，只与相对大小有关系，先把所有用到的、不同的数映射成从 1 开始的自然数，映射后的数据范围为 1 ~ 3 × 10^5，用前缀和的方式来解决这个问题

每次求一个区间和的时候，输入一个 L、输入一个 R，求下标 L ~ R 之间所有数的和，其实是想找到 x 在 L ~ R 之间的所有数 x1、x2、. . . xk 求和，只要在 L ~ R 之间就把之前加过的数加上：保序离散化的方式，把所有用到的下标映射到从 1 开始的自然数(需要求前缀和，从 1 开始映射)

每次想给 x 这个位置上的数加上 c，先找到 x 离散化之后的值是多少，在 x 离散化后的值的位置上加上 c 即可：假设 x 离散化后的值是 k，让 a[ k ] += c 即可

求某一个区间里面的所有数的和：求 L ~ R 之间所有数的和，先把 L 和 R 离散化到它们对应的下标的位置，L 离散化后是 kL，R 离散化后是 kR，求 a[ kL ] ~ a[ kR ] 之间的所有数的和即可

把数组上的每个值映射到它的下标，排序后，下标就是它映射的值

a 数组排序后：1、2、100、2000、30000，下标对应为 0、1、2、3、4，把 a 数组中的每个数映射成它的下标：1 映射成 0，2 映射成 1，100 映射成 2

插入 *** 作总数为 n = 10 w、有一个坐标，查询 *** 作总数为 m = 10 w、有两个坐标，离散化的数据规模为 n + 2m，所以开 30 w 个数组

#include
#include
#include  

using namespace std;

const int N = 300010;
//每组 *** 作需要用到两个数 用 pair 存储
typedef pair PII;

int n,m;
//存储的数 前缀和
int a[N],s[N];
//存储所有需要离散化的值
vector alls;
//插入 *** 作 询问 *** 作
vector add,query;

//求 x 这个值离散化后的结果
int find(int x) 
{
    int l = 0,r = alls.size() - 1;
    while(l < r)
    {
        //取中点
        int mid = l + r >> 1;
        //找大于等于 x 的最小的数
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    //返回位置的下标 + 1  把 x 映射到从 1 开始的自然数-> 前缀和不需要处理边界
    return r + 1;  
}

int main()  
{
    //读入所有需要 *** 作的数
    cin >> n >> m;
    //读入所有的插入 *** 作
    for(int i = 0; i < n; i++ )
    {
        //每一个插入操作是两个值-> 在下标 x 的位置加上 c
        int x,c;
        cin >> x >> c;
        add.push_back({x,c});
        
        //需要把 x 离散化-> 把 x 加入待离散化的数组中去
        alls.push_back(x);
    }
    //把所有要用到的下标全部放到了 alls 数组中
    for(int i = 0; i < m;i++ )
    {
        int l,r;  
        //读入所有的左右区间-> 区间的左右端点都是需要离散化的  
        cin >> l >> r;
        //加入到 query 中
        query.push_back({l,r}); 
        //把左右区间全部加到待离散化的数组中
        alls.push_back(l);
        alls.push_back(r);
    }
    //把 alls 数组去重
    //将所有的值排序
    sort(alls.begin(),alls.end());
    //去掉重复元素
    alls.erase(unique(/* alls */alls.begin(),alls.end()),alls.end());
    
    //分别处理两种 *** 作
    //处理插入
    //求 add  *** 作 x 离散化后的值
    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;
}

实现 unique 函数

实现思路为双指针算法：把所有不重复的元素 (所有满足下面性质的数) 放到前 j 个位置

第一个指针 i 遍历所有的数，第二个指针 j 存当前存到了第几个不同的数，遍历的时候时刻保证 j ≤ i，从 0 ~ j - 1 存储的就是所有不同的元素

先排序，排序后，应该挑出什么样元素(每一段相同的第一个数满足的条件)？什么样的元素是不同的？

所有不同的元素一定满足以下性质，只需要把所有满足这些性质的数拿出来，就是所有不同的元素

//返回的是一个迭代器  
vector::iterator unique(vector &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;
}

区间合并

区间合并的应用场景：给出很多的区间，如果两个区间之间有交集，就把它们合并成一个区间(把它们的并集当做新的区间)

题目输入 n 个区间，把这 n 个区间中所有 有交集的区间 进行合并，输出合并之后的区间个数

区间合并算法用于快速地把这 n 个区间中 有交集的区间 进行合并

边界问题：两个区间如果只有端点相交也可以合并

示例：

区间 1 ~ 区间 4、区间 7 ~ 区间 9 可以合并，最终合并之后可以得到 3 个没有任何交集的区间，输出 3

 

①按照所有区间的左端点排序

②扫描整个区间，扫描的过程中，把所有可能 有交集的区间 进行合并

每次维护一个当前的区间，当前区间的左端点为 st，当前区间的右端点为 ed，从前往后扫描的过程当中，假设当前已经扫描到了第 i 个区间，第 i 个区间和当前区间的关系有 3 种 (如图)

①在当前区间的内部

②与当前区间有交集，但是不在内部

③在当前区间的后面，没有交集

注意不会出现在当前区间左边的情况(由于是按照区间的左端点从小到大的顺序来扫描所有区间的，因此第 i 个区间的左端点，一定是在维护区间左端点的右边)

只会出现以上 3 种情况，如果出现任一情况，如何更新我们现在维护的区间？

对于第 1 种情况而言，更新后 st 和 ed 不变

对于第 2 种情况而言，更新 ed 的位置，把维护的区间变长

如果出现第 3 种情况说明：前面维护的区间和当前区间没有交集，而且是按照左端点从小到大的顺序来扫描所有区间，后面所有区间的左端点一定是在当前区间的后面，从当前区间开始，后面的所有区间和当前维护的区间没有任何交集

由于当前维护的区间已经不会与后面的区间有交集，就可以把维护的区间作为一组解，然后把维护的区间更新成第 i 个区间

 

#include
#include
#include
using namespace std;

//每个区间是两个端点 用 pair 来存储 first存储区间的左端点,second存储区间的右端点
typedef pair PII;
const int N = 100010;
//一共有 n 个区间 把所有区间存到 vector 中
int n;
vector segs;
//把区间进行合并
void merge(vector &segs)
{
    //定义答案-> 存储合并之后的结果
    vector res;
    //先把所有区间排序-> pair排序: 优先给左端点排序 再给右端点排序
    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});
    //更新区间为 res
    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;  
}