算法备忘录·基础算法

本文最后更新于 2023年3月31日上午

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

基础算法

排序

快速排序

核心思想：
1. 设定分界值 $a[l], a[r], a[(l + r) / 2]$ ；
2. 左边小于分界值，右边大于分界值
  - 双指针，两端开始，找到左边一个大于分界值，右边一个小于分界值，就将二者交换
  - 必须严格大于/小于，否则会 Memory Limit Exceeded；
3. 递归

模板

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 (i < j){
    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]\Rightarrow [L,mid], [mid + 1, R]$
2. 递归排序 $[L,mid]$ 和 $[mid + 1,R]$
3. 归并，将左右两个有序序列合并成一个有序序列

模板

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]$
- 所以 while 的判断条件是 l <= r ，这样保证退出循环时，搜索区间是空集
使用 l = mid + 1 和 r = mid -1 是因为 mid 已经被排除了

模板

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())$
- 所以 while 的判断条件是 l < r ，这样保证退出循环时，搜索区间是 $[l,l)$ 空集
为什么是 l = mid +1 和 r = mid，因为每次分割变成 $[l,mid)$ 和 $[mid+1,r)$
返回 r ，因为a[mid] == target时，有 r = mid。这也是为什么能够搜索左边界——当找到 target 后，并不是立刻返回，而是缩小上界
如果 target 不存在，可以修改返回为 a[l] == target ? l : 1

模板

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())$
- 所以 while 的判断条件是 l < r ，这样保证退出循环时，搜索区间是 $[l,l)$ 空集
为什么是 l = mid +1 和 r = mid，因为每次分割变成 $[l,mid)$ 和 $[mid+1,r)$
返回 l - 1 ，因为a[mid] == target时，有 l = mid +1。这也是为什么能够搜索左边界——当找到 target 后，并不是立刻返回，而是缩小下界
如果 target 不存在，可以修改返回为 a[l - 1] == target ? l - 1 : 1

模板

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; // 重点
}

浮点数二分

模板

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'
下面的各个运算均为非负数，负数的情况判断符号位，转换为绝对值加减

高精度加法

注意会有新的进位

模板

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

模板

// 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
注意会有新的进位

模板

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 方法

模板

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

模板

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 之间元素求和
由于需要方便设定 $a_0=0$ 和 $S_0=0$ ，所以录入数据的时候是下标从 $1$ 开始

一维前缀和

$S[i] = a[1] + a[2] + \dots + a[i]$
$a[l] + \dots + a[r] = S[r] - S[l - 1]$ （注意是 $l-1$ ）

二维前缀和

$S[i,j]$ ：第 $i$ 行 $j$ 列格子上左上部分所有元素之和
以 $(x_1,y_1)$ 为左上角， $(x_2,y_2)$ 位右下角的子矩阵所有元素之和： $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[i-1]$
给区间 $[l,r]$ 中的每个数加上 $c$ ： $B[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,\dots,0]$ 数组逐个插入 $a[i]$ 元素得来的
    1
    for (int i = 1; i <= n ; i ++) insert(i, i, a[i]);

二维差分

给以 $(x_1,y_1)$ 为左上角， $(x_2,y_2)$ 位右下角的子矩阵所有元素的加上 $c$ ： $S[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(n^2)$ 根据具体问题中的性质简化到 $O(n)$
- 某种“单调性”
常见问题
- 对于一个序列，用两个指针维护一段区间。e.g：滑动窗口
- 对于两个序列，维护某种次序。e.g：归并排序中合并两个有序序列

模板

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

位运算

求 $n$ 的第 $k$ 位数字
1
n >> k & 1
返回 $n$ 的最后一位 1
1
lowbit(n) = n & -n

离散化

将值域大但是数量少的值映射到一个小值域区间上
步骤
1. 储存所有待离散化的值
2. 排序后去重
  - 一定是先排序！
3. 利用二分法求出对应的离散化的值

模板

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() 函数，则可以用双指针写

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  开始 
}

区间合并

用于将所有存在交集的区间合并

模板

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

算法备忘录系列目录：
第一节算法备忘录·基础算法
 第二节算法备忘录·数据结构
 第三节算法备忘录·STL
第四节算法备忘录·搜索与图论
 第五节算法备忘录·数学知识
 第六节算法备忘录·动态规划
 第七节算法备忘录·贪心
 第八节算法备忘录·时空复杂度分析

笔记

#计算机 #算法

算法备忘录·基础算法

https://justloseit.top/算法备忘录·基础算法/

作者

Mobilis In Mobili

发布于

2021年7月29日

更新于

2023年3月31日

许可协议