双指针/位运算/离散化/区间和并

  • 双指针

    • 两个指针指向两个不同的序列
    • 两个指针指向同一个序列(归并排序,快速排序)
    • 主要作用:将暴力O(n^2)遍历通过两个指针的某种单调性质优化到O(n),也就是说将内层循环变量j通过与外层循环变量i的关系,将内层循环次数降低不定次
    • 模板:

      for(int i = 1; i < n; ++ i){
      	while(j < i && check(i, j)) j ++ ;
      	//内部逻辑具体分析
      }
      
      //例如将一个字符串中的单词按行输出
      str = "acv adf wers";
      int len = strlen(str);
      //双指针算法
      for(int i = 0; i < len; ++ i){
      	int j = i;
      	while(j < len && str[j] != ' ') j ++ ;
      	
      	//内部逻辑具体分析
      	//输出单词
      	for(int k = i; k < j; ++ k) cout << str[k];
      	cout << endl;
      	int i = j;
      }
      
  • 位运算

    • 常用操作:

      • 求n的二进制的第k位:
        • 将n右移k位 (n >> k)
        • 再取右移k位后的个位 (n >> k) & 1
      • 返回x的二进制中最后一位1的位置:
        • lowbit(x) = x & -x lowbit(x)的二进制中只有一个1,该1就是x的二进制中的最后一位1
        • -x = ~x + 1 补码为反码加一
      • 求n的二进制中1的个数:
        • while(n) n -= lowbit(n), ans++;
        • 当n不为0时,n每次去掉最后一位1,ans即为n的二进制中1的数量
  • 离散化

    • 将无限区间中的有限元素映射到有限的区间中,将稀疏空间变得稠密
    • 不改变元素间的相对位置
    • 模板:

      vector<int> alls;//离散化数组
      sort(alls.begin(), alls.end()); //排序
      alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
      //根据原值查找离散化后的下标
      int find(int x){
      	int l = -1, r = alls.size();
      	while(l + 1 < r){
      		int mid = l + r >> 1;
      		if(alls[mid] >= x) r = mid;
      		else l = mid;
      	}
      	return r + 1; //以1作为起点下标
      }
      //unique函数双指针实现
      //在不递减的数列中快速提取出不重复的数
      vector<int>::iterator unique(vector<int> &a){
      	for(int i = 0, j = 0; i < a.size(); ++ i){
      		if(!i || a[i] != a[i - 1]) //要么是第一个数,要么前一个数不同于后一个数
      			a[j ++ ] = a[i]; //a[0] ~ a[j - 1] 是所有不同的数
      	}
      	return a.begin() + j;
      }
      
      
  • 区间和并

    • 把有有交集的区间合并
    • 将所有区间按左端点从升序排列
    • 遍历所有区间,每次比较相邻两区间是否相交,若前面区间的右端点严格小与后面区间的左端点即为不相交,否则相交
    • 若两区间相交就取并集,否则得到一个合并完成的区间,更新维护的区间,进行下一次合并
    • 模板:

      typedef pair<int, int> PII; 
      vector<PII> segs; //存储不同区间
      //合并区间的函数
      void merge(vector<PII> &segs){
      	vector<PII> res; //存储答案区间
      	sort(segs.begin(), segs.end()); //默认按first升序排序
      	int st = -inf, ed = -inf; //维护的区间初始化
      	for(auto seg : segs){ //遍历所有区间
      		if(ed < seg.first){ //如果维护的区间与新区间不相交说明维护的区间已经合并完成
      			if(st != -inf) res.push_back({st, ed}); //将合并完成的区间存储
      			st = seg.first, ed = seg.second; //更新维护的区间
      		}else ed = max(ed, seg.second); //否则取交集
      		if(st != -inf) res.push_back({st, ed}); //所有区间合并成为一整个区间的情况
      		swap(res, segs); //返回答案到原数组
      	}
      }
      

热门相关:恭喜你被逮捕了   金粉   修真界败类   万古至尊   修真界败类