第一章 基础算法（三）

双指针算法

核心在于优化了O(n^2)成O(n)

for (int i = 0, j = 0; i < n; i ++ )
{while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}
常见问题分类：(1) 对于一个序列，用两个指针维护一段区间(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

799. 最长连续不重复子序列

800. 数组元素的目标和 

位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

801. 二进制中1的个数 

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素// 二分求出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
}

802. 区间和 

区间合并

本质是贪心排序(会议安排那种)

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{vector<PII> 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});segs = res;
}

803. 区间合并