算法笔记:AcWing - 基础算法
写这篇的初衷:很多算法模板背了就忘,核心是没理解为什么要这样写。这篇试着从”什么时候用”和”为什么有效”两个角度重新整理。
更进一步的初衷:最近要开始找实习了,好久没碰算法,已经比较生疏了,算是一次 “温故而知新”
一、排序:快排 vs 归并
快速排序 —— “分而治之”的典型
什么时候用:日常排序首选,平均性能最好,原地排序不占额外空间。
核心直觉:随便选个数当”标杆”(pivot),把比它小的扔左边,比它大的扔右边,然后对左右两边递归干同样的事。
为什么快:每次划分后,pivot 就回到了它最终应该在的位置。理想情况下每次划分都是中点,递归深度是
但要注意:最坏情况(数组已经有序)会退化成
1 | void quick_sort(vector<int>& arr, int l, int r) { |
易错点:选
arr[l]做 pivot 时,递归要写quick_sort(arr, l, j)而不是l, mid,因为划分后 j 才是分界点。
归并排序 —— 稳定且可预测
什么时候用:
- 需要稳定排序(相同元素的相对顺序不变)
- 链表排序(不需要额外空间)
- 求逆序对(归并过程中可以顺便统计)
核心直觉:先把数组拆到最小(单个元素天然有序),然后两两合并。合并时两个指针分别指向两个有序段,每次取较小的那个。
为什么稳定:合并时遇到相等的元素,优先取左边段的,所以相对顺序不会变。
代价:需要
1 | void merge_sort(vector<int>& arr, int l, int r) { |
二、二分查找:不只是”有序数组找数”
核心思想
二分的本质不是”找数”,而是根据某种单调性,每次排除一半的搜索空间。
关键:找到那个可以判断”答案在左边还是右边”的性质。
整数二分:两个模板
场景 1:找满足性质的最小值(比如找第一个>=x 的位置)
区间划分:[l, mid] 和 [mid+1, r]
1 | int bsearch_1(vector<int>& arr, int l, int r, int x) { |
场景 2:找满足性质的最大值(比如找最后一个<=x 的位置)
区间划分:[l, mid-1] 和 [mid, r]
1 | int bsearch_2(vector<int>& arr, int l, int r, int x) { |
为什么要 +1:整数除法向下取整。当
l = r-1时,不加 1 则mid = l,如果 check 为真,l = mid还是等于 l,死循环。加 1 后mid = r,可以正常推进。
浮点数二分:更简单
不用考虑边界问题,直接缩小区间直到足够小:
1 | double l = 0, r = 1e9; |
三、高精度运算:当数字超出 long long
什么时候用:数字超过 18 位(long long 上限),比如
核心思想:用数组存每一位,模拟小学竖式计算。
存储技巧:倒序存储,arr[0] 存个位,方便进位时直接 push_back。
高精度加法
1 | vector<int> add(vector<int>& A, vector<int>& B) { |
高精度减法
前提:保证 A >= B,如果不确定要先比较大小。
1 | vector<int> sub(vector<int>& A, vector<int>& B) { |
高精度乘法(大数×小数)
1 | vector<int> mul(vector<int>& A, int b) { |
高精度除法(大数÷小数)
注意:除法要正序处理,从高位开始。
1 | vector<int> div(vector<int>& A, int b, int& r) { |
四、前缀和与差分:区间查询/修改的神器
前缀和 —— 快速求区间和
场景:频繁查询某个区间的和,但数组本身不修改。
原理:预处理出 S[i] = a[1] + ... + a[i],那么区间 [l, r] 的和就是 S[r] - S[l-1]。
为什么快:预处理
1 | // 一维前缀和 |
二维前缀和 —— 子矩阵求和
场景:求矩阵中某个子矩形的元素和。
公式:
直觉:大矩形减去左边和上边,但左上角被减了两次,要加回来。
1 | // 预处理 |
差分 —— 快速区间修改
场景:频繁对某个区间统一加/减一个数,最后再查询。
原理:差分和原数组的关系是”前缀和的逆运算”。对原数组区间 [l, r] 加 c,等价于差分数组 b[l] += c,b[r+1] -= c。
为什么快:修改
1 | // 差分数组 |
二维差分 —— 子矩阵批量修改
1 | // 对子矩阵 (x1,y1) 到 (x2,y2) 加 c |
五、双指针法:从 到
核心思想:利用单调性,用两个指针维护一个区间,避免嵌套循环。
典型场景:
- 找最长/最短满足某条件的子数组
- 两数之和
- 滑动窗口问题
模板:
1 | for (int i = 0, j = 0; i < n; i++) { |
例子:找最长不重复子串
1 | for (int i = 0, j = 0; i < n; i++) { |
六、位运算:一些实用技巧
取第 k 位
1 | int bit = (n >> k) & 1; // 右移 k 位后和 1 做与运算 |
Lowbit —— 提取最低位的 1
1 | int lowbit(int n) { |
原理:-n 的补码是 ~n + 1,与 n 相与后只有最低位的 1 保留。
应用:树状数组的核心操作。
七、离散化:值域太大怎么办
场景:数字范围很大(比如
思路:把出现过的数字排序去重,然后用它们的排名代替原值。
1 | vector<int> all; // 收集所有需要离散化的值 |
好处:原本需要开
八、区间合并:把有交集的区间合并
场景:给定一堆区间,合并所有有交集的。
思路:
- 按左端点排序
- 遍历,如果当前区间和上一个有交集就合并,否则新开一个
1 | void merge(vector<pair<int, int>>& segs) { |
小结
这些基础算法的核心不是背模板,而是理解:
| 算法 | 核心思想 | 典型场景 |
|---|---|---|
| 快排 | 分治 + 分区 | 日常排序 |
| 归并 | 分治 + 合并 | 稳定排序、逆序对 |
| 二分 | 单调性排除 | 找边界、答案二分 |
| 前缀和 | 预处理换查询 | 区间求和 |
| 差分 | 延迟修改 | 区间加减 |
| 双指针 | 单调性优化 | 滑动窗口 |
| 离散化 | 值域压缩 | 大值域小数量 |
下一篇整理数据结构部分~
- Title: 算法笔记:AcWing - 基础算法
- Author: Ginkgo
- Created at : 2026-04-05 18:56:34
- Updated at : 2026-04-12 16:22:23
- Link: https://g1nkgo7.github.io/2026/04/05/算法笔记-AcWing-基础算法/
- License: This work is licensed under CC BY-NC-SA 4.0.