算法基础课 第一讲基础算法总结

仅贡本人复习用， 如有不足请大佬指出

学习内容1: 快速排序

练习链接： 快速排序
重点理解 快排的实现原理— 用到的是分治的思想， 本身排序是不稳定的, STL中有对应的sort函数，故在平常刷题的过程不用特地自己写出快排，但理解快排的原理我觉得对自己编码能力还是有用的，这里y总的快排模板，里面还有双指针的用法在里面

快排模板

void quick_sort(int q[], int l, int r)    // 这样写的l, r 都是左右端点，并不像stl的左开右闭
{ 
    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);  //这里结束之后的i,j 其关系为 i >= j;

     //此时j下标的左边为小于x的值，其右边为大于base的值，此时的j下标对应的值小于等于x
     //故依次作为两个区间，在这两个区间内再进行快排，注意此时不要写成如下的形式
     // quick_sort(q,l,i -1); quick_sort(q,i, r);
     //因为这种写法在面对数组为 1, 2 的这种情况会无限递归. l + r >> 1 属于下标下取整,
     //故此时的x对应的值为0， 此时指针i指到第一个位置(下标为0)时即停止,j下标--同样到
     //下标为0的位置停止移动，然后if判断false, 此时 i = j = 0, 故执行quick_sort(q,i,r)会无限递归。
     //故为了不必要的边界考虑，将这个模板熟悉，用j下标即可
}

快排的拓展 ： 快速选择 –>

将一个位置的数字排序正确， 相比于快排每次只是递归一半，故其时间复杂度为 O(N);
相关题目链接: 第k个数

代码 – 其实就是快排模板

void quick_sort(int l, int r, int k)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1, base = a[l + r >> 1];
    while(j > i)
    {
        do ++i;while(a[i] < base);
        do --j;while(a[j] > base);
        if(j > i) swap(a[i], a[j]);
    }   

    int len = j - l + 1 ;
    if(len >= k) quick_sort(l, j, k);
    else quick_sort(j + 1, r, k - len);
}

当然stl中也有相对应的库函数 : nth_element()函数, nth_element(a, a + k - 1, a + n);位于头文件 algorithm, 参1， 参3 为 first 和 last用于指定函数的作用范围，参2为指定的位置， 默认的参4缺省为降序规则, 函数将参2指定的位置，指定位置左边的值小于他，其右边的值都大于它， 时间复杂度为O(n);

学习内容2: 归并排序

主要思想 : 分治再合并
链接: 归并排序
代码模板

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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; 
    //前面都合并到一个保存的数组中，最后进行扫尾工作，将其写回原数组
}

学习内容3 ： 二分

可以二分，即存在可以二分的某种性质，可以将左右两边都划为不同的两类，二分本身并不难，但二分的check条件，和边界条件的判断有时候很坑，这里二分建议直接背过y总的模板:

相关练习链接 :
数的范围

整数二分模板

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;  //注意这里必须上取整 + 1, 不然l = mid, 可能在两个的情况下无限递归. 
        if (check(mid)) l = mid;   
        else r = mid - 1;         
    }
    return l;
}

浮点数二分模板

ool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)     // 表示精度，当然也可无脑直接for个100次来达到高精度
     {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;    // 相比于整数二分，由于浮点数能精确二分，故没有+1的写法
        else l = mid;
    }
    return l;
}

学习内容4: 高精度

由于C的数据类型不支持大整数，故面对大数运算时，即使是long long也不够用，故需要实现高精度，java自带大整数类，python本身就是高精度，不用考虑。故这里只有C才需要高精度这个问题， 高精度运算分为高精度加法，减法，乘法，除法;

主要思路: 利用 string 保存大数字， 将其每一位数字储存到vector中

main函数中解决vector的输入

#include<iostream>
#include<vector>
#include<string>
using namespace std;
using VI = vector<int>;

auto main() -> int
{
    string s1, s2;  VI v1, v2;

    cin >> s1 >> s2;

    // 这里的输入采用的是从个位开始push_back的，因为如果发生进位直接在后面push_back即可，不用整个移动数组
    for(int i = s1.size() - 1, j = s2.size() - 1; i >= 0 || j >= 0; --i, --j) 
    {
        if(i >= 0) v1.push_back(s1[i] - '0');    
        if(j >= 0) v2.push_back(s2[j] - '0');
    }

    auto v = add(v1, v2);        // 这里将add换为 sub, mul, div 完成减，乘，除法

    for(int i = v.size() - 1; i >= 0; --i)     // 输出
        cout << v[i] ;
    cout << endl;
    return 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);     // 若还有剩余的进位，直接添加到最高位
    return C;
}

//高精度减法模板 

//减法注意的一个问题就是出现负数的情况，故这里专门有个check函数进行检测

auto check(VI &A, VI &B) -> bool
{
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0; --i)
        if(A[i] != B[i]) return A[i] > B[i];
    return true;
}

auto sub(VI &A, VI &B) -> VI
{
    VI 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)% 10);     // 这里的处理是考虑到借位的情况
        if(t >= 0) t = 0;
        else t = -1;                   // 若此时t<0, 说明此时向最高位借位了,故要减掉1
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();  // 减法是会产生前导0的，故这里为去除前导0,注意C容器的大小是>=2,即>1
    return C;
}

#if 0
    最后的输出部分， 输入部分参考前面加法模板的
    if(check(v1, v2)) v = sub(v1, v2);
    else cout << "-", v = sub(v2, v1);

    for(int i = v.size() - 1; i >= 0; --i)
        cout << v[i] ;
    cout << endl;
    return 0;

#endif 

// 高精度乘法 -- 通常是一个大数 乘以一个较小的数 int 类型
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )  //这里或 || t的意思是只要t不为0，就继续执行取余，除10进位操作
    {
        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(); // 乘法产生前导0的原因是 一个数乘以0
    return C;
}

// 高精度除法  -- 一个大数 除以 一个小数(int)
vector<int> div(vector<int> &A, int b, int &r)   // 这里的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;
}

学习内容5: 前缀和与差分

1. 一维数组前缀和
   S[i] = a[1] + a[2] + … a[i]
   a[l] + … + a[r] = S[r] - S[l - 1]

 for(int i = 1; i <= n; ++i) cin >> s[i];
    for(int i = 1; i <= n; ++i) s[i] += s[i - 1];  // 求前缀和数组

 cout << s[j] - s[i - 1] << endl; // 求某个区间的和

2.二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和 = s[i, j - 1] + s[i - 1, j] - s[i - 1][j - 1] + a[i][j];
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

公式推导

3.差分

差分相当于求前缀和的逆运算， 即存在数组 a1, a2, a3,....,ai, 此时需要构造数组b，使得ai = b1 + b2 + b3 +,…, + bi; 故 a数组 为 b数组的前缀和数组, b数组 为 a数组的差分数组。

其应用为这样一种场景: 当需要在a数组的某个区间，例如[l, r] 区间都加上一个常数C的时候，如果按照常规的做法，需要将a数组从这个循环一遍+C, 如果这时有它的差分数组，我们可以让 bl += C, 然后 br+1 -= C; 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c. 然后再对其求前缀和

差分代码:

#include<iostream>
using namespace std;

constexpr int N = 1e+5 + 10;
int n,m;
int a[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)      // 直接由原数组构造差分数组, 由于默认都是0, 故本身就是一个原数组全为0的差分数组，故相当于看做是执行了一个区间为1的插入操作
    {
        int t; cin >> t;
        a[i] += t; a[i + 1] -= t;
    }

    while(m--)                       // 区间处理， 在[l, r]区间加上一个C
    {
        int l , r , c; cin >> l >> r >> c;
        a[l] += c; a[r + 1] -= c;
    }

    for(int i = 1; i <= n; ++i)     // 求前缀和--> 即处理之后的原数组并输出
    {
        a[i] += a[i - 1];
        cout << a[i] << " ";
    }

    cout << endl;

    return 0;
}

4.二维差分

差分矩阵的公式：

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

公式的推导和例题的题解: 差分矩阵

学习内容6 : 双指针算法

主要思想 : 使用i, j两个指针指向数组，将原本时间复杂度 O(N2) 的变为 O(N);

主要练习：
799. 最长连续不重复子序列
800. 数组元素的目标和
2816. 判断子序列

学习内容7 : 位运算

常用位运算

 n >> k & 1   //求n的第k位数字: n >> k & 1    //k是从第0位开始算起

 n & -n       // 返回n的最后一位1的位置（二进制的第几位）, 这里相当于补码与上原码 

相关练习 801. 二进制中1的个数

学习内容8 离散化

题解 : 离散化例题题解

学习内容9 区间合并

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

auto merge(vector<PII> &v)
{
    int l = -2e+9, r = -2e+9;
    sort(v.begin(), v.end());
    for(auto item : v)
    {
        if(item.first > r)
        {
            if(r != -2e+9) v1.emplace_back(l,r);
            l = item.first;r = item.second;
        }
        else 
            r = max(r, item.second);
    }
    if(r != -2e+9) v1.emplace_back(l, r);     // 最后将剩余的区间处理
}