位运算

原码反码补码

x + （-x） = 0image.png

  • 位运算 —— 模板题 AcWing 801. 二进制中1的个数image.png
  • 求n的第k位数字: n >> k & 1 【先把第k位移到最后一位，然后看下个位是几：& 1】
  • 返回n的最后一位1：lowbit(n) = n & -n 【lowbit(n) = n &( ~n + 1)】
    • 应用：统计一个数中有多少个1
    • 10010 -》 10
    • 10010000 -》 10000image.png

      双指针算法

      最核心的用途就是可以优化~~ 暴力就是n^2的时间复杂度，但是所有双指针算法都是O（n）

双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

  1. // 具体问题的逻辑<br />}<br />常见问题分类：<br />    (1) 对于一个序列，用两个指针维护一段区间
  • 输出单词句子中的每个单词。【空格隔开】
  • 最长连续不重复子序列【leetcode】（滑动窗口题目）
    • i j 遍历，检查 i j 之间的字符串序列是否满足条件
    • 规律就是i增加的时候，j是不会往回走的。【单调性】image.png


  • (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

    离散化

    特征整数的有序离散化。
    有一堆数值，范围很大，个数比较少，数的范围很大。需要把这个序列映射到其他的范围。

离散化 —— 模板题 AcWing 802. 区间和

vector alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素 unique返回值是去重后的序列的下一个值的下标，~end之间直接擦除就好
image.png

  1. uniq函数的实现：双指针算法，排序之后什么样的元素是要保留的呢？
  2. - 要么是第一个，要么和前一个元素不一样。

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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, 2, …n。
}

应用：

区间和：
image.png
数据范围比较小，用前缀和，预处理，开数组~。
值域很大，但是只用到了其中很小一部分的值，用到了离散化。把所有用过的下标映射到从1开始的自然数。
image.png
image.png

区间合并

区间合并 —— 模板题 AcWing 803. 区间合并。
image.png
贪心

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

   //1. 首先按照区间的左端点排序~。然后
    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);
// 最后的区间加入到答案里面去。判断是为了防止给的区间是null
    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}