Blkcor Dev

some templates

quick sort

算法名称时间复杂度空间复杂度
快速排序O(nlogn)O(logn)

模版如下：

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[l], i = l - 1, j = 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);
}

注意事项：

  • 如果将 quick_sort(q, l ,j)和quick_sort(q, j+1 ,r)换成quick_sort(q, l ,i-1)和quick_sort(q, i, r)，那么x不能取q[l]，会出现边界问题，同理上述模版中也不能将x取为q[r]。
  • 边界问题判断 if(l >= r)也可以换成if(l == r)，这个看个人习惯。

merge sort

算法名称时间复杂度空间复杂度
归并排序O(nlogn)O(n)

模版如下：

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 (int i = 0, j = l; j <= r; i++, j++)
        q[j] = tmp[i];
}

注意这里需要一个临时的数组tmp来存放排好序的结果。

有单调性一定能用二分，但是二分适用于的题目不一定具备单调性的特征。

二分的本质：

image-20230925191550356

我们可以找到一个特征，将我们的区间一分为二，二分的本质就是能找到这个特征的左边界和右边界。（分别对应两个不同的模版）

算法名称时间复杂度空间复杂度
二分查找O(logn)O(1)
  • 整数二分
void binary_search(int q[] ,int x, int n){
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if (q[l] != x) cout << "-1 -1" << endl;
}
 
// 或者
 
void binary_search(int q[],int x, int n){
  int l = 0 ,r = n-1;
  while(l < r){
    int mid = l+r+1 >>1 ;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
  }
  if (q[l] != x) cout << "-1 -1" << endl;
}

记住这两个板子即可。

  • 浮点数二分(以浮点数的平方根为例子)
void binary_search(){
  double x;
  cin << x;
  int l = 0, r = x;
  while(r-l > 1e-8){
    double mid = (r + l) /2;
    if(mid * mid >= x) r = mid;
    else l = mid;
  }
  cout << r << endl;
}

或者可以通过设置迭代次数来实现：

void binary_search(){
  double x;
  cin << x;
  int l = 0, r = x;
  for(int i=0 ;i < 100 ;i++){
    double mid = (r + l) /2;
    if(mid * mid >= x) r = mid;
    else l = mid;
  }
  cout << r << endl;
}

high precision

以[两数相加][https://leetcode.cn/problems/add-two-numbers/] 这道题为例子编写模版

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *res = new ListNode(0);
        ListNode *current = res;
        int t = 0;
        while (l1 || l2) {
            if (l1) {
                t += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                t += l2->val;
                l2 = l2->next;
            }
            current->next = new ListNode(t % 10);
            t /= 10;
            current = current->next;
        }
        if (t) {
            ListNode *last = new ListNode(t);
            current->next = last;
        }
        return res->next;
    }
};

原版子如下:

#include<iostream>
#include<vector>
 
using namespace std;
 
vector<int> add(vactor<int> &A,vactor<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;
}
 
int main(){
  vector<int> A,B;
  string a,b;
  cin >> a >> b;
  for(int i = A.size() -1; i >= 0; i--) A.push_back(a[i]);
  for(int i = B.size() -1; i >= 0; i--) B.push_back(b[i]);
 
	vector<int> C = add(A,B);
 
  for(int i = C.size()-1; i >= 0;i--) cout << C[i];
  return 0;
}

简单了解一下即可，用处不大，根本不会考！。

prefix sum

前缀和和差分是一对逆运算。

什么是前缀和：前缀和可以简单理解为「数列的前n项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

一维前缀和

  • 公式如下：

$$ S_i = \sum_{j=1}^ia_j $$

  • 作用：快速计算「l , r」这个区间的数组的和：

$$ Sum = S_r - S_{l-1} $$

附：

ios::sync_with_stdio(false);
//这句代码的作用是令cin和标准输入输出不同步，可提高cin的读取速度
//但是缺点是不能再使用scanf了

二维前缀和

  • 公式如下：

$$ S_{i,j} = S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + a_{i,j} $$

  • 作用：计算区域的面积 「x1,y1」— 「x2,y2」

$$ Sum = S_{x2,y2} - S_{x_1-1,y2} - S_{x2,y_1-1} + S_{x_1-1,y_1-1} $$

这里有一定微分的思想在里面。

difference

差分和前缀和是一对逆运算。

一维差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

  • 这种策略的定义是令 $b_i :\begin{cases} a_i \quad i=1 \\ a_i-a_{i-1} \quad i\in[2,n] \end{cases}$
  • $a_i$的值是$b_i$的值的前缀和：$a_n = \sum_{i=1}^nb_i$
  • 计算$a_i$的前缀和$sum = \sum_{i=1}^na_i = \sum_{i=1}^n\sum_{j=1}^ib_j = \sum_{i=1}^n(n-i+1)b_i$

板子如下：

#include<iostream>
 
using namespace std;
 
const int N = 100010;
int a[N], b[N];
 
/**
 * 差分操作可以统一理解为插入操作
 * @param l
 * @param r
 * @param c
 */
void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}
 
int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)insert(i, i, a[i]);
    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i++)b[i] += b[i - 1];
    for (int i = 1; i <= n; i++)cout << b[i] << " ";
 
    return 0;
}

二维差分

类比一维差分，我们应该让二维平面的一块区域的所有的 $a_{ij}$ 都加上 c 。

另外对于所有的差分操作，我们只需要考虑如何进行更新即可，无需考虑如何构造差分数组。

二维中我们的插入操作公式：

  • $b_{x_1,y_1} +c$
  • $b_{x_2+1,y_1} -c$
  • $b_{x_1,y_2+1} -c$
  • $b_{x_2+1,y_2+1} + c$

板子如下：

#include<iostream>
 
using namespace std;
 
const int N = 1010;
int a[N][N], b[N][N];
 
/**
 * 差分操作可以统一理解为插入操作
 */
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;
}
 
int main() {
    ios::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);
    while (q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
 
    for (int i = 1; i <= n; i++)b[i] += b[i - 1];
    for (int i = 1; i <= n; i++)cout << b[i] << " ";
 
    return 0;
}

two pointer

将双层for循环的时间复杂度优化到：$O(N)$

模版如下：

#include<iostream>
 
using namespace std;
 
int main(){
  for(int i = 0,j = 0; i < n; i++){
    while(j <= i && check(i,j)) j++;
 
    //具体题目的逻辑
  }
}

以[LCR 016. 无重复字符的最长子串][https://leetcode.cn/problems/wtcaE1/] 这道题为例子进行写板子：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            a[s[i]] ++;
            while (a[s[i]]>1) {
                a[s[j]]--;
                j++;
            };
            res = max(res, i - j + 1);
        }
        return res;
    }
 
private:
    static const int N = 5*1e4 + 10;
    int a[N];
};

bit operation

先确立几个基础的观点：

  • 如何查看n的第k位的值：
1、将n右移k位，将第k位移到最低位
2、&1 取出最低位的值
 
总结就是进行如下的操作：n>>k & 1
  • lowbit(x)：取到x的最后一位1
// lowbit(101100) ==> 100
// lowbit(1010000) ==> 10000

公式：x & (~x + 1) = x & -x

使用：求一个数二进制表示中1的个数：

#include <iostream>
 
using namespace std;
 
int low_bit(int x){
    return x & (-x);
}
 
int main(){
    int n;
    cin >> n;
    while(n--){
        int x,res = 0;
 	       cin >> x;
        while(x) x-= low_bit(x),res++;
        cout << res << " ";
    }
    return 0;
}

discretization

定义

值域：$0$ ~$10^9$，个数：$0$ ~ $10^5$，我们需要把这些数离散到一系列连续的下标上。

重点

  • 这些数字中可能会出现重复的元素，去重
vector<int> alls;
//排序
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
  • 如何算出x离散后的值（在a[]中的下标）（因为上一步已经有序了，直接二分求解）
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 3 4 5 6 .. n
}

题目描述：

image-20231004215153688

板子如下：

#include <iostream>
#include<algorithm>
#include <vector>
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 300010;
 
//a为离散化后的数组 s为a的前缀和数组
int a[N], s[N];
 
//all离散化前的数组 存所有的下标
vector<int> alls;
 
//add处理插入 query处理询问
vector<PII> add, query;
 
int find(int 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 l + 1;
}
 
int main() {
    int m, n;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
 
        alls.push_back(x);
    }
 
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
    }
 
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
 
    //处理插入
    for (auto item: add) {
        int x = find(item.first);
        a[x] += item.second;
    }
 
    //处理前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
 
    //处理询问
    for (auto item: query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
 
    return 0;
}

Merge Intervals

将有交集的区间合并成为一个更大的区间。

关键：找到合并区间的条件。

  • 将区间的左端点进行排序
  • 维护一个区间（初始化为左端点最小的区间）
  • 分为下面三种情况讨论
    • 包含
    • 有交集
    • 没有交集
  • 更新区间

以56. 合并区间为例子进行写板子：

#include <iostream>
#include<algorithm>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end());
        int st = -2e9, ed = -2e9;
        for (auto item: intervals) {
            if (ed < item.front()) {
                //无交集
                if (st != -2e9) res.push_back({st, ed});
                st = item.front(), ed = item.back();
            }
 
                //否则就是有交集
            else ed = max(ed, item.back());
        }
        //防止结果中不存在任何一个区间
        if (st != -2e9) res.push_back({st,ed});
 
        return res;
    }
};