本文共 4957 字，大约阅读时间需要 16 分钟。

双指针算法

核心思想: 将时间复杂度为O(N^2)的朴素算法优化到O(N)

核心代码:

for(int i = 0,j = 0;i < n;i ++ ){
   	while(j < i && check( (i,j) ) j ++ ;	// 具体的每道题目的基本逻辑:	}

模版:

对于一个给定的字符串 , 其中每个单词间隔1个空格,将它们分割后输出 code:

// 给定一个字符串 将其中的单词分割输出#include 
   
    #include 
    
     using namespace std;const int N = 100010; char c[N];int main(){
       gets(c);    int len = strlen(c);    for(int i = 0, j = 0;i < len; i ++ )    {
           j = i;        while(j < len && c[j] != ' ') j ++ ;        for(int k = i;k < j;k ++ ) printf("%c",c[k]);        cout << endl;        i = j;    }    return 0;}
    
   

模版二:

给定一个序列,求出其最长连续不重复子序列的长度 思路 : 双指针 i , j 暴力做法:

for(int i = 0;i < n;i ++ )	for(int j = 0;j < i;j ++ )	if(check(i,j)) // 相应的操作	res = max (res, i - j + 1);

因为其是单调的 , 可以优化到O(N)

代码如下: 注意: 此代码开了一个数组存放数列中元素出现的数的次数,所以仅仅限于数据量较小的情况,当数据量很大的时候 需要用到 Hashmap 哈希表来进行操作

// 给定一个序列 求其最长连续不重复子序列的长度#include 
   
    #include 
    
     using namespace std;const int N = 100010;int a[N] , s[N]; int 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;}
    
   

---

位运算

十进制 -> 二进制 取余

二进制 -> 十进制 每位*2^n (从 0 开始) 补码的计算公式：

正数：源码、反码和补码都相同。   负数：补码 = 反码（符号位保持不变） + 1

注意： 负数在计算补码的时候，在源码取反的过程中要保留符号位不变，其他位取反，例如：10001010取反11110101（第一个1不变）,补码就为11110110。

模版一:

求 x 的二进制表示中的第 k 位是几 代码如下:

// 求x的二进制表示中第k位数是多少#include 
   
    using namespace std;int main(){
       int x , k ; scanf("%d%d",&x,&k);    cout << (x >> k & 1) << endl;    return 0;}
   

模版二:

树状数组的基本操作 : lowbit(X) 效果 : 返回 X 的最后一位 1 (注意返回的是二进制数) 实现 : x & -x 涉及原理 : 二进制的源码 补码 反码

应用一: 求 x 二进制中 1 的个数

代码如下:

// 求 x 二进制中的 1 的个数是多少#include 
   
    using namespace std;int lowbit(int x){
       return x & -x;}int main(){
       int n ; scanf("%d",&n);    while (n -- )    {
           int x ; scanf("%d",&x);        int cnt = 0;        while (x) x -= lowbit(x), cnt ++ ;        cout << cnt << " " << endl;    }    cout << endl;    return 0;}
   

---

离散化

整数 . 有序

当题目的 整个值域跨度很大 但其值分布的很稀疏的时候, 可以使用离散化 对存储空间进行优化 防止爆栈

1. a [ ] 中可能重复的元素 – 去重
2. 算出 x 离散化后的值 – 二分

模版 :

vector
   
     alls ; // 存储所有待离散化的值sort(alls.begin() , alls.end()) // 将所有值排序alls.erase(unique(alls.begin() , alls.end()) , alls.end()) ; // 去重// 二分求出 x 对应的离散化的值int find(int x){
       int l = 0 , r = all.size() - 1;    while(l < r)    {
           int mid = l + r >> 1;        if(alls[mid] >= x) r = mid;        else l = mid + 1;    }        return r + 1; // 为了配合后面的前缀和 所以从 1 开始 要 + 1;}
   

模版例题:

一个无限长的数轴 , 初始时所有点对应的值都是 0 现有如下操作 , 对任意一个点的数 + c , 有如下询问 , 求任意区间的区间和 现在 经过 m 次操作 q 次询问 输出答案

代码如下:

注意:因为这里查询操作中的数也要一起离散化 , 所以需要将其预先存储到一个pair容器中 , 不能边读入输入的数据边输出.

#include 
   
    #include 
    
     #include 
     
      using namespace std;typedef pair
      
        PII;const int N = 300010;int n , m ;int a[N] , s[N] ;vector
       
         alls;vector
        
          add , query ;// find 函数 求出 x 离散化后的值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; // 映射到从 1 开始的自然数 因为后面要求前缀和 从 1 开始不需要考虑边界问题}int main(){ cin >> n >> m ; for(int i = 0;i < n;i ++ ) { int x , c; cin >> x >> c; add.push_back({ x,c}); // 注意 pair的输入要使用 {} 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) // c++ 11 的新特性 可由auto : 遍历容器 { 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;}
        
       
      
     
    
   

---

区间合并

给定 多个 区间 , 把所有有交集的区间合并成一个 区间

1. 按区间的左端点进行排序
2. 按区间从左右往右扫描 , 每次维护一个区间 // 左端点从小到大

c++中的 sort 排序

-> sort排序pair时 先看first的优先级 再看second的优先级 , 即在此左端点 会优先于 右端点

模版 :

对于给定的区间 , 将有交集的区间合并成一个区间 , 求合并后区间的个数 :

代码如下:

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 100010 ;typedef pair
      
        PII ;int n ;vector
       
         segs ;// 合并区间函数void merge(vector
        
          &segs){ vector
         
           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}) ; // //此处的if判断 防止输入的数组segs里面是空的 即输入的 n 为0的情况 // 如果为空 则不修改 segs = res ;}int main(){ scanf("%d",&n) ; for(int i = 0;i < n;i ++ ) { int l , r; scanf("%d%d",&l,&r); segs.push_back({ l,r}) ; } merge(segs) ; cout << segs.size() << endl; return 0;}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_45877540/article/details/108309575 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！