双指针算法和位运算 & 离散化和区间合并
双指针算法
核心思想——将 O(n^2)时间复杂度优化到 O(n)
代码模板
输入一个字符串,将中间的每个单词输出一行
最长连续不重复子序列
j 为绿色,i 为蓝色
遍历数组 a 中的每一个元素 a[i], 对于每一个 i,找到 j 使得双指针[j, i]维护的是以 a[i]结尾的最长连续不重复子序列,长度为 i - j + 1, 将这一长度与 r 的较大者更新给 r。
对于每一个 i,如何确定 j 的位置:由于[j, i - 1]是前一步得到的最长连续不重复子序列,所以如果[j, i]中有重复元素,一定是 a[i],因此右移 j 直到 a[i]不重复为止(由于[j, i - 1]已经是前一步的最优解,此时 j 只可能右移以剔除重复元素 a[i],不可能左移增加元素,因此,j 具有“单调性”、本题可用双指针降低复杂度)。
用数组 s 记录子序列 a[j ~ i]中各元素出现次数,遍历过程中对于每一个 i 有四步操作:cin 元素 a[i] -> 将 a[i]出现次数 s[a[i]]加 1 -> 若 a[i]重复则右移 j(s[a[j]]要减 1) -> 确定 j 及更新当前长度 i - j + 1 给 r。
位运算
求 n 的第 k 位数字:n>>k&i;
返回 n 的最后一位 1 的位置:lowbit(n)=n&-n;
将一个整数转换成二进制
x&-x==x&(~x+1)
统计 x 内 1 的个数
二进制中 1 的个数
离散化(整数离散化)
vector<int> alls;//存储所有待离散化的值
sort(alls.begin(),alls.end());//将所有的值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去掉重复元素
代码模板
区间和
区间合并
先按左端点排序,再维护一个区间,与后面一个个区间进行三种情况的比较,存储到数组里去。
评论