学了三天基础算法,基本上已经理解了这些算法的思想
总之我想给自己总结一下这三天学到了什么,以及有哪些心得
- 排序
首先是快速排序,这个没什么好说的,只要记住快排的核心思想就行了
第一: 选择一个数组里的数 x,两个指针 i = 0, j = n - 1 互相靠拢,如果两个指针都不合法就交换所指的数: swap(q[i], q[j])
PS: 不合法指的是 q[i] > x && q[j] < x
第二:让左边半边和右边半边做第一步
上代码:
void quick_sort(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); }
归并排序
归并的思想就是将已有序的子序列合并,得到完全有序的序列
主要用于找逆序对
void merge_sort(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); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
- 二分
如果题目规定了有“最大值最小”或者“最小值最大”的东西,那么这个东西应该就满足二分答案的有界性(显然)和单调性(能看出来)。
二分答案应该是在一个单调闭区间上进行的。也就是说,二分答案最后得到的答案应该是一个确定值,而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性,那么这个单调性应该体现在哪里呢?
可以这样想,在一个区间上,有很多数,这些数可能是我们这些问题的解,换句话说,这里有很多不合法的解,也有很多合法的解。我们只考虑合法解,并称之为可行解。考虑所有可行解,我们肯定是要从这些可行解中找到
一个最好的作为我们的答案, 这个答案我们称之为最优解。
最优解一定可行,但可行解不一定最优。我们假设整个序列具有单调性,且一个数x为可行解,那么一般的,所有的x'(x'<x)都是可行解。并且,如果有一个数y是非法解,那么一般的,所有的y'(y'>y)都是非法解。
二分思路很简单,没什么好说的,上代码模板
整数二分:
bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用: int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用: int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
浮点数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
- 高精度 感觉用不太到就没学
- 前缀和,差分
一维前缀和就很简单,只有一个用途,求区间和
公式:
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维比较复杂,需要去理解,作用:求子矩阵的和
公式:
S[i, j] = 第i行j列格子左上部分所有元素的和
S[i, j] = S[i - 1, j] + s[i, j - 1] + S[i - 1, j - 1] + a[i, j]
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
差分
作用:用O(1)的时间给一个区间都加上某个数
一维:给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c
二维:给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
- 位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
- 双指针
作用:优化暴力解法 从O(n^2)到O(n)
上代码模板:
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类: (1) 对于一个序列,用两个指针维护一段区间 (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
- 离散化
有时题目数据很大,比如1 <= a[i] <= 10^9
但是数量很少 1 <= n <= 10^5
此时就可以使用离散化,把每个数和到1 ~ 10^5 一一对应
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 }
- 区间合并
没啥好讲的,自己体会,算法很简单
// 将所有存在交集的区间合并 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; }
总结:
二分答案挺爽的,离散化感觉很有用,前缀和和差分是个很好用的工具
逆序对是个很有意思的点,题目中有时会很巧妙地出现