基础算法

本文最后更新于 2025年2月25日 下午

基础算法

排序

快速排序

  • 思想：分治策略
  • 稳定性：不具有稳定性(因为值可能相同)。可以将pair<a[i], i>作为二元组排序就可以使其具有稳定性
  • 步骤：
      1. 确立分界点： l, r, (l + r) / 2, 随机对应下标的数组里的值作为x
      2. 调整：分为两段，第一段<=x，第二段>=x
      3. 递归处理左右两段

模板：无需考虑边界问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
}

归并排序

  • 思想：分治策略
  • 稳定性：具有稳定性
  • 步骤：
      1. 确定分界点：mid = (l + r) / 2，下标的值
      2. 递归排序left和right
      3. 归并(合二为一) \(O(n)\) 重复 \(log(n)\) 次。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge_sort(int q[], int l, int r)//调用时注意l,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 ++ ];
	
    //将临时数组复制回q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二分

整数二分

  • 条件：有单调性的一定能二分，能二分的不一定有单调性。二分的本质不是单调性。
  • 本质：边界。存在某种性质，可以把整个区间一分为二，二分就可以寻找这个性质的边界。
  • 边界：该性质将区间一分为二后，左边区间的右端点和右边区间的左端点分别对应两种模板。
  • 有解性：二分一定有解，但题目不一定有解，最后需要判断是否符合题意
  • 步骤：
      1. 如何选择模板，先写出check(mid)函数
      2. 思考如何根据这个函数更新区间，满足性质的时候，边界在右面还是在左面，保证区间内一定有答案
      3. l = mid 或者 r = mid，前者在mid初始化时需要+1。使其离边界“更近”，防止死循环

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

浮点数二分

  • 特点：不需要处理边界，标准的二分
  • 结束标志：区间长度足够小，即 r - l <= 1e-6 等类似数字。或直接循环指定迭代的次数N，相当于精度\(\frac{区间长度}{2^N}\)
  • 经验值：题目要求保留n位小数，那么r - l <= 1e-(n+2)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

易错点：求某个数的平方根，二分范围不是0, x而是0, max(1, x)

高精度

高精度加法

  • vector<int>存储大整数的每一位，个位在前（方便进位）
  • 步骤：
      1. 从个位开始遍历
      2. 设置进位位，初始为t = 0
      3. 按位加上两个整数每一位的值（需判断下标是否在两个整数各自的大小内），若结果大于10，则判断发生进位t = 1
      4. 循环结束后，还要判断t的值，如果为1，需要加上一位1在数组末尾，表示最终的进位。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;	//进位
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法

  • 存储方式与加法一致
  • 大小判别放到使用时判断
  • 步骤：
      1. 从个位开始遍历
      2. 设置借位位，初始为t = 0
      3. 先减去上一位的t，按位加上两个整数每一位的值（需判断减数下标是否在其大小内）
      4. 合并处理减完后大于零小于零的情况。若小于零，还要令t = 1，表明需要借位。
      5. 循环结束后，去掉前导零，同时令位数不少于1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);	//合并处理减完后大于零小于零的情况
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度

  • 与加法类似
  • 大数乘相对小的数，并且实现时将小的数作为整体，按位处理大数的值
  • 防止数据存在乘0的情况，要加入处理前导零的步骤
  • 从个位开始遍历

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度

  • 为了方便与其他运算结合，存储方式仍然采用之前的
  • 从最高位开始遍历，与之前不同
  • 答案的存储方式不同，返回前要使用algorithm中的reverse方法将元素倒转
  • 注意顺序：先倒转再去前导零

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

前缀和与差分

前缀和

  • 如何求\(S_i\)：

\[ S_i=a_1+a_2+\cdots+a_i , S_0=0 \]

1
2
3
4
for(int i = 1; i <= n; i++)
{
    s[i] = s[i-1]+a[i];
}

注意：下标一定从1开始，避免边界判断条件

  • 作用：快速求出任意区间的和[L,R]->\(S_R-S_{L-1}\)

二维前缀和

\[ S[i, j] = 第i行j列格子左上部分所有元素的和 \]

1
2
3
4
5
6
7
for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= m; 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[x_2, y_2] - S[x_1 - 1, y_2] - S[x_2, y_1 - 1] + S[x_1 - 1, y_1 - 1] \]

差分

  • 构造\(b_i\)，一般不需要，只需要考虑如何更新，以0数组为基准进行增减操作，最后再处理成原数组的增减即可

\[ b_i=a_i-a_{i-1} \]

  • 与前缀和互为逆运算
  • 作用：对区间增减一个值，可由复杂度\(O(n)\)变为\(O(1)\)
  • 例如，要使期间[L,R]每个数都+c，则可使b[L]+c且b[R+1]-c

一维差分

1
2
3
4
5
6
// b为差分数组
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

二维差分

1
2
3
4
5
6
7
8
// b为差分矩阵
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

双指针算法

  • 核心思想：
    • for(for) \(O(n^2)\) 转换为 \(O(n)\)
  • 常见问题分类：
    • 对于一个序列，用两个指针维护一段区间
    • 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
1
2
3
4
5
6
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

位运算

n的二进制表示中第k位的值

例如 \(n = 15 = (1111)_2\)

  1. 先把第k位移到最后一位 n >> k
  2. 看个位是几 x & 1
  3. 总结 n >> k & 1

lowbit(x)返回x的最后一位1

\(x = 1010\) lowbit(x) = 10

\(x = 101000\) lowbit(x) = 1000

  • 负数等于按位取反加一
    • -x = ~x + 1
  • x & -x = x & (~x + 1)

​ x = 1010...100...0

​ ~x = 0101...011...1

​ ~x + 1 = 0101...100...0

x & (~x + 1) = 0000...100...0

整数离散化

  • 背景：数组值域很大，个数不多
    • 跨度大，但是很稀疏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls;	//存储所有待离散化的值
sort(alls.begin(), alls.end());	//将所有值排序
all.erase(unique(alls.begin(), alls.end()), alls.end());	//去掉重复元素

//二分求出x对应离散化的值
int find(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是为了映射到 1,2,...,n
}

区间合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将所有存在交集的区间合并
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;
}

数据结构

链表与邻接表

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}

普通队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{

}

单调栈

1
2
3
4
5
6
7
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

单调队列

1
2
3
4
5
6
7
8
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}
notes > CS
#算法 #cpp
基础算法
https://cdro.tech/notes/CS/basic-algorithm/
作者
k9Q6CK42
发布于
2024年12月23日
更新于
2025年2月25日
许可协议