算法备忘录·基础算法

本文最后更新于:2021年11月20日 凌晨

一直以来,没能系统学习算法,是我心中的痛;现在学了y总的算法基础课,做做笔记,希望能够有所收获。
这是第一节,基础算法。

基础算法

排序

快速排序

  • 核心思想:
    1. 设定分界值 a[l],a[r],a[(l+r)/2]a[l], a[r], a[(l + r) / 2]
    2. 左边小于分界值,右边大于分界值
      • 双指针,两端开始,找到左边一个大于分界值,右边一个小于分界值,就将二者交换
      • 必须严格大于/小于,否则会 Memory Limit Exceeded
    3. 递归
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void quick_sort(int a[], int l, int r){
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
    while (l < r){
    do i ++; while(a[i] < x);
    do j --; while(a[j] > x);
    if (i < j) swap(a[i], a[j]);// 注意这里的if判断
    }
    quick_sort(a, l, j), quick_sort(a, j + 1, r);
    }

归并排序

  • 核心思想

    1. [L,R][L,mid],[mid+1,R][L,R]\Rightarrow [L,mid], [mid + 1, R]
    2. 递归排序 [L,mid][L,mid][mid+1,R][mid + 1,R]
    3. 归并,将左右两个有序序列合并成一个有序序列
  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void merge_sort(int a[], int l, int r){
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int i = l, j = mid+1, k=0;
    while (i <= mid && j <= r){
    if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ];
    else tmp[k ++ ] = a[j ++ ];
    }

    // 将另一序列剩下的元素放进合并空间
    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++ ];

    for (int i = l, j=0; i <= r; i ++ , j++ ) a[i] = tmp[j]; // 复制回原数组
    }

二分

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

  • 单调性❌ 二分性✅
  • else if 每个情况写清楚,就能很好地避免错误

整数二分

寻找一个数

  • 搜索区间:[0,a.size()1][0,a.size()-1]

    • 所以 while 的判断条件是 l <= r ,这样保证退出循环时,搜索区间是空集
  • 使用 l = mid + 1r = mid -1 是因为 mid 已经被排除了

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int bsearch(int a[], int target){
    int l = 0, r = a.size() - 1;
    while (l <= r){ // 重点
    int mid = (l + r) >> 1;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) l = mid + 1; // 重点
    else if (a[mid] > target) r = mid - 1; // 重点
    }
    return -1;
    }

寻找左边界

  • 搜索区间:[0,a.size())[0,a.size())

    • 所以 while 的判断条件是 l < r ,这样保证退出循环时,搜索区间是 [l,l)[l,l) 空集
  • 为什么是 l = mid +1r = mid,因为每次分割变成 [l,mid)[l,mid)[mid+1,r)[mid+1,r)

  • 返回 r ,因为a[mid] == target时,有 r = mid。这也是为什么能够搜索左边界——当找到 target 后,并不是立刻返回,而是缩小上界

  • 如果 target 不存在,可以修改返回为 a[l] == target ? l : 1

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int l_bsearch(int a[], int target){
    int l =0, r = a.size(); // 重点
    while (l < r){
    int mid = (l + r) >> 1;
    if (a[mid] == target) r = mid; // 重点
    else if (a[mid] < target) l = mid + 1;
    else if (a[mid] > target) r = mid; // 重点
    }
    return r; // 重点
    }

寻找右边界

  • 搜索区间:[0,a.size())[0,a.size())

    • 所以 while 的判断条件是 l < r ,这样保证退出循环时,搜索区间是 [l,l)[l,l) 空集
  • 为什么是 l = mid +1r = mid,因为每次分割变成 [l,mid)[l,mid)[mid+1,r)[mid+1,r)

  • 返回 l - 1 ,因为a[mid] == target时,有 l = mid +1。这也是为什么能够搜索左边界——当找到 target 后,并不是立刻返回,而是缩小下界

  • 如果 target 不存在,可以修改返回为 a[l - 1] == target ? l - 1 : 1

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int l_bsearch(int a[], int target){
    int l =0, r = a.size(); // 重点
    while (l < r){
    int mid = (l + r) >> 1;
    if (a[mid] == target) l = mid + 1; // 重点
    else if (a[mid] < target) l = mid + 1;
    else if (a[mid] > target) r = mid; // 重点
    }
    return l - 1; // 重点
    }

浮点数二分

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    double bsearch(double l, double r){
    const double eps = 1e-6;
    while (r - l > eps){
    double mid = l + (r -l) / 2;
    if (check(mid)) r = mid;
    else l = mid;
    }
    return l;
    }

高精度

  • 存储:vector<int>,倒序存储,小位在左
    • 这样方便添加新的高位
    • 压位:一般来说我们用数组的一个元素来表示一个位数。但是,为了节省空间,可以一个元素表示多个位数
  • 读取:一般输入都是 string 读入,再逆序存储到 vector<int> 中,记得要-'0'
  • 下面的各个运算均为非负数,负数的情况判断符号位,转换为绝对值加减

高精度加法

  • 注意会有新的进位

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B,A);

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

    if (t) C.push_back(t % 10); // 新的进位
    return C;
    }

高精度减法

  • 需要去除前置 0

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // A >= B
    vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t;
    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(); // 去除前置 0
    return C;
    }

高精度乘法

vector<int> * int

  • 需要去掉前置 0

  • 注意会有新的进位

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    vector<int> mul(vector<int> &a, int b){
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++){
    t += A[i] * b;
    C.push_back(t % 10);
    t /= 10;
    }
    while (t){
    C.push_back(t % 10);
    t /= 10;
    } // 新的进位
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前置 0

    return C;
    }

vector<int> * vector<int>

  • 有更快的 FFT 方法

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    vector<int> mul(vector<int> &A, vector<int> &B){
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i ++){
    for (int j = 0; j < B.size(); j ++){
    C[i + j] += A[i] + B[j];
    }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i ++){
    t += C[i];
    C[i] = t % 10;
    t /= 10;
    }

    while (t){
    C.push_back(t % 10);
    t /= 10;
    } // 新的进位

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前置 0

    return C;
    }

高精度除法

  • 注意 /% 的使用位置

  • 所得结果需要 reverse,然后去前置 0

  • 模板

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

前缀和与差分

前缀和

  • 便于处理从 l 到 r 之间元素求和
  • 由于需要方便设定 a0=0a_0=0S0=0S_0=0,所以 录入数据的时候是**下标从 11 开始 **

一维前缀和

  • S[i]=a[1]+a[2]++a[i]S[i] = a[1] + a[2] + \dots + a[i]
  • a[l]++a[r]=S[r]S[l1]a[l] + \dots + a[r] = S[r] - S[l - 1](注意是 l1l-1

二维前缀和

  • S[i,j]S[i,j] :第 iijj 列格子上左上部分所有元素之和
  • (x1,y1)(x_1,y_1) 为左上角,(x2,y2)(x_2,y_2) 位右下角的子矩阵所有元素之和: S[x2,y2]S[x11,y2]S[x2,y11]+S[x11,y11]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]=A[i]A[i1]B[i]=A[i]-A[i-1]

  • 给区间[l,r][l,r]中的每个数加上 ccB[l]+=c,B[r+1]=cB[l]+=c,B[r+1]-=c

    • 模板

      1
      2
      3
      4
      void insert(int l, int r, int c){
      b[l] += c;
      b[r +1 ] -= c;
      }
    • 这样一来,生成差分数组就有了两种方法

      • 法 1:根据定义

      • 法 2:对原数组,可以视其为 [0,0,,0][0,0,\dots,0] 数组逐个插入 a[i]a[i] 元素得来的

        1
        for (int i = 1; i <= n ; i ++) insert(i, i, a[i]);

二维差分

  • 给以 (x1,y1)(x_1,y_1) 为左上角,(x2,y2)(x_2,y_2) 位右下角的子矩阵所有元素的加上 ccS[x1,y1]+=c,S[x2+1,y1]=c,S[x1,y2+1]=c,S[x2+1,y2+1]+=cS[x_1,y_1] += c,S[x_2+1,y_1]-=c,S[x_1,y_2+1]-=c,S[x_2+1,y_2+1]+=c

双指针算法

  • 将暴力 O(n2)O(n^2) 根据具体问题中的性质简化到 O(n)O(n)

    • 某种“单调性”
  • 常见问题

    • 对于一个序列,用两个指针维护一段区间。e.g:滑动窗口
    • 对于两个序列,维护某种次序。e.g:归并排序中合并两个有序序列
  • 模板

    1
    2
    3
    4
    for (int i = 0, j = 0; i < n; i ++){
    while (j < i && check(i, j)) j ++;
    // 具体问题的逻辑
    }

位运算

  • nn 的第 kk 位数字

    1
    n >> k & 1
  • 返回 nn 的最后一位 1

    1
    lowbit(n) = n & -n

离散化

  • 值域大但是数量少的值映射到一个小值域区间上

  • 步骤

    1. 储存所有待离散化的值
    2. 排序后去重
      • 一定是先排序!
    3. 利用二分法求出对应的离散化的值
  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> alls; // 储存待离散化的值
    sort(alls.begin(),alls.end()); // 排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重


    // 二分法求对应离散化值,找到第一个大于等于 x 的位置,相当于求大于等于 x 的左边界
    int find(int x){
    int l = 0, r = alls.size(), mid;
    while(l < r){
    mid = l + (r - l) / 2;
    if (alls[mid] >= x) r = mid;
    else l = mid + 1;
    }
    return r;
    }
    • 对于有的语言,不含 unique() 函数,则可以用双指针写

      1
      2
      3
      4
      5
      6
      vector<int>::iterator unique(vector<int> &a){
      for(int i = 0; i < a.size(); i ++){
      if (!a[i] || a[i] != a[i - 1]) a[j ++] = a[i];
      } // a[0] ~ a[j - 1] 为所有 a 中不重复的数
      return a.begin() + j;
      }
    • 对于二分查找,也可以直接使用 low_bound() 函数

    1
    2
    3
    int find(int x){
    return low_bound(alls.begin(), alls.end(), x) - alls.begin(); // 下标从 0 开始
    }

区间合并

  • 用于将所有存在交集的区间合并
  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end()); // c++ 在排序 pair 类型时,会先比较第一个,若第一个一样再比较第二个

    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;
    }

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!