基础算法
基础算法合集
常见但是没法归类的一些东西的整理
1. 一些排序算法
会让你手撕的就两个 一个快排 一个归并排序
边界问题好好记一下 撕错了就太丢脸了
1. 快排
void quick_sort(vector<int>& q, int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}快排扩展-数组中第k个数
快排：
找到分界点
分成两个区间并调整
递归排序左边/递归排序右边
这里我们找第K个数，无需排序所有 只要找到一边就可以了
判断依据
K <= sl : 递归left
K > sl : 递归right K = K - sl;
int quick_select(vector<int>& q, int l, int r, int k)
{
if(l == r) return q[l];
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
// 这里不再是递归两边了
int sl = j - l + 1;
if(k <= sl)
return quick_select(q, l, j, k);
else return quick_select(q, j + 1, r, k - sl);
}2. 归并排序
归排:
确定分界点
先递归处理左右两边
把两个有序数组合二为一
void merge_sort(vector<int>& q, int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
vector<int> tmp;
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp.push_back(q[i++]);
else tmp.push_back(q[j++]);
while(i <= mid) tmp.push_back(q[i++]);
while(j <= r) tmp.push_back(q[j++]);
// 贴到原数组中
for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}归并排序扩展-求数组中逆序对的个数
左半边的逆序对 + 右半边的逆序对 + 交叉的逆序对
交叉的逆序对 左右两边分别排序 不影响其数量
这样就沿用归并排序的结构 当q[i] > q[j]的时候 q[i] 和 q[i]后面的数肯定都比q[j]大
所以直接加上 mid - i + 1 就可以了
class Solution {
public:
int reversePairs(vector<int>& nums) {
return merge_sort(nums, 0, nums.size() - 1);
}
int merge_sort(vector<int>& q, int l, int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
// 归并
int i = l, j = mid + 1;
vector<int> tmp;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp.push_back(q[i++]);
else
{
res += mid - i + 1; // i 后面的都是逆序 因为q[i] 后面的数比q[i]大 同样也比 q[j] 大
tmp.push_back(q[j++]);
}
}
while(i <= mid) tmp.push_back(q[i++]);
while(j <= r) tmp.push_back(q[j++]);
// 赋值回去
for(int i = 0, j = l; i < tmp.size(); i++, j++)
q[j] = tmp[i];
return res;
}
};方法2：树状数组
树状数组可以用来求:左边/右边比当前元素大/小的个数
怎么做呢 就是拿值当下标，每次出现就给其加1，这样区间查询就可以查到比当前元素大 or 小的和：即出现次数之和
当然了 由于数据可能很大 这里要保序离散化
// 保序离散化
vector<int> alls = nums;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int find(int 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！
}树状数组的几个操作
class Solution {
public:
int n;
// 离散化
vector<int> tree, alls;
int lowbit(int i)
{
return i & (-i);
}
void update(int i, int val)
{
while(i <= n)
{
tree[i] += val;
i += lowbit(i);
}
}
int query(int i)
{
int sum = 0;
while(i > 0)
{
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
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
}
int reversePairs(vector<int>& nums) {
n = nums.size();
tree = vector<int>(n + 10);
// 1. 离散化
alls = nums;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
int res = 0;
for(int x : nums)
{
int y = find(x);
res += query(n) - query(y);
update(y, 1);
}
return res;
}
};2. 常见的区间问题
区间问题基本都是贪心来搞的 常见的有一下几个
1. 区间合并
按左端点排序 然后遍历区间 如果ed 和新区间的起点分开的话, 就更新合并结果;
看代码就懂了
注意最后可能还剩下一个区间{st, ed} 没有加进去
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;
}除了用pair存之外，二维vector默认也是按照第一个元素排序的 所以不用担心
2. 区间选点
在数轴上选择尽可能少的点, 使得每个区间内至少包含一个选出的点，输出选择的点的最少数量 「请注意：位于区间端点上的点也算在区间内」
方法：
按照区间右端点排序
从前往后以此枚举每个区间的右端点：如果当前取件中已经包含这个右端点 直接pass 否则选择当前区间的右端点
struct Interval{
int l, r;
bool operator<(const Interval& w) const{
return r < w.r;
}
}intervals[N];
int solution()
{
sort(intervals, intervals + n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i++)
{
int l = intervals[i].l, r = intervals[i].r;
if(ed >= l) continue;
else
{
ed = r;
res += 1;
}
}
return res;
}3. 最大不相交区间数量
选择区间之间互不相交（包括端点）
和上面的题是一样的
4. 区间分组
给定区间，请你将这些区间分成若干组，使得每组内部的区间两两之间(包括端点) 没有交集，并使得组数尽可能小
方法：
按照做端点从小到大排序
从前往后处理每个区间 判断能否放入某个现有的组 （记录组内端点最大值）
不能 -> 开新组
找到最小的组：优先队列存右端点
struct Interval{
int l, r;
bool operator<(const Interval& w) const
{
return l < w.l;
}
}intervals[N]
int solution()
{
sort(intervals, intervals + n);
priority_queue<int, vector<int>, greater<int>> heap;
for(int i = 0; i < n; i++)
{
int l = intervals[i].l, r = intervals[i].r;
if(heap.empty() || heap.top() >= l)
{
heap.push(r)
}
else {
heap.pop();
heap.push(r);
}
}
return heap.size();
}3. 常见位运算技巧
常见的一些和 不太常见的一些位运算：
lowbit(x) = i & (-i) 找到最近的1 并扣出来 i & (i - 1) 删除最近的1 i >> k & 1 判断i的第k位是不是1 (注意这里不用写括号 & 的优先级会低一些)
不太常见但是要记的：
数组中出现一次 剩下的元素都出现三次
本来觉得没啥但是ms前两天考了
one = (one ^ x) & (~two);
two = (two ^ x) & (~one);取奇数位/ 取偶数位 取奇数位：
x & 0xAAAA取偶数位：x & 0x5555奇偶位对换
((x & 0xAAAA) >> 1) | ((x & 0x5555) << 1)
4. 滑动窗口合集
滑动窗口分为两种 固定长度的滑动窗口和长度可变的滑动窗口
1. 固定长度的滑动窗口
2. 可变长度的滑动窗口
Last updated