双指针算法 （n）

思想：把直接的暴力转化为用两个指针的形式，这样可以达到（n）的时间复杂度

for(int i=0,j=0;i<n;i++)
{
    while(j<=i&&check(j,i))j++;
    res=max(res,i-j+1);
}

位运算

求二进制数的第k为是多少。
n>>k&1 为的k位的数。
10的二进制数是1010 是从个位开始数，个位为第0位。
x&-x 求出的是x的二进制中的最后一位1的值.

如 10 二进制为 00001010 -10 的二进制为11110110 10 & -10 等于 00000010;
10 的原码为 00001010 反码为:11110101 补码为:11110110 .

离散化

把单调数据波动比较大->转化为较为集中。这就是离散化。
1 把数据排序 sort(alls.begin(),alls.end());
2 去重 alls.erase(unique(alls.begin(),alls.end()),alls.end());
3 得到离散化的结果。

可以由以前的下表x找到离散化后的下表。

int find(int x)
{
    int l=0,r=alls.szie()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid;
    }
    return l+1; //让离散化的下标从一开始
}

手写的unique

vector<int>::iterator(vector<int> &a)
{
    for(int i=0,j=0;i<a.size();i++)
    {
        if(!i||a[i]!=a[i-1])
        a[j++]=a[i];
    }
    return a.begin()+j;
}

区间合并

1.先以左端点排序
2.便利全部边 如果有相交就取尾端长的，否在可以得到一个不相交的区间

typedef pair<int,int> PII;
vector<PII>segs;
sort(segs.begin(),segs.end());
int st=-2e9 en=2e9;
void merge()
{
    vector<PII> c;
    sort()
    for(int i=0;i<segs.size();i++)
   {
      auto t=segs[i];
      if(t.first>en)
      {
          if(st!=-2e9)c.push_back({st,en});
          st=t.first,en=t.second;
      }
      else en=max(en,t.second);

    }
    return ;
}