基础算法

字数统计: 2.5k字   |   阅读时长≈ 11分钟

acwing算法基础课，基础算法

1. 快速排序

  • 分治算法

  • 步骤：

    • 随意选定一个主元 $x$
    • 让左半部的都 $\le x$ , 右半部都 $\ge x$
    • 递归处理左右两边即可

  • 复杂度分析

    • 期望时间复杂度为$O(NlogN)$

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void quick_sort(int l, int r, int q[])
    {
        if(l >= r ) return;
        int x = q[l + r >> 1], i = l - 1,  j = r + 1;
        while(i < j)
        {
            while(q[++i] < x);
            while(q[--j] > x);
            if(i < j) swap(q[i], q[j]);
        }
        quick_sort(l, j, q);
        quick_sort(j + 1, r, q);
    }

2. 快速选择

  • 快速排序的一个应用,快速找出一组数中第 $k$ 大的数

  • 每次根据快速排序每次左右两边的长度选择一边进行递归即可，因为能保证每次左右两边的数有严格的 $left \le right$ 关系

  • 选出来之后，第$k$个数之前的数一定都是小于等于它的

  • 期望时间复杂度为$O(N)$

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int quick_sel(int q[], int l, int r, int k)
    {
        if(l >= r) return q[l];
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j)
        {
            while(q[++i] < x);
            while(q[--j] > x);
            if(i < j) swap(q[i], q[j]);
        }
        int len = j - l + 1;
        if(k <= len) return quick_sel(q, l, j, k);
        else return quick_sel(q, j + 1, r, k - len);
    }

3. 归并排序

  • 分治算法

  • 算法步骤

    • 选定中点 $mid$
    • 递归处理左右两边
    • 二路归并

  • 时间复杂度 $O(NlogN)$

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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 i = l, j = mid + 1, k = 0;
        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 = l, k = 0; i <= r; i ++ , k ++ ) q[i] = tmp[k];
    }

4. 逆序对的数量

  • 归并排序算法的一个简单应用，找出一组数据中逆序对的个数

  • 分析过程

    • 对归并排序做简单分析：每次递归处理完左右两边之后，左右两边之内肯定是没有逆序对出现的，所以逆序对出现在二路归并的过程中，若是归并过程中，一路都是左边的小于右边的，那显然左边小于右边，也不会有逆序对，所以就发生在左边的数大于右边的数的时候，此时会出现逆序对，且自此之后一直到$mid$ 都是逆序对，共产生了$mid - i + 1$组逆序对

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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 i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r)
            if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
            else 
            {
                res += mid - i + 1; // 在这里产生了逆序对
                tmp[k ++ ] = q[j ++ ];
            }
        while(i <= mid) tmp[k ++ ] = q[i ++ ];
        while(j <= r)   tmp[k ++ ] = q[j ++ ];
        for(int i = l, k = 0; i <= r; i ++ , k ++ ) q[i] = tmp[k];
    }

5. 二分

  • 二分算法利用的是二段性，即要处理的数据左右两边满足不同的性质，比如左边$\le x$，右边$\ge x$， 即可作为二分的依据，不需要满足单调性也可以二分
  • 对于二分区间而言，算法的复杂度是$O(logN)$, 非常快

5.1 整数二分

  • 整数二分要处理一些边界问题，所以建议直接套模板即可

  • 模板一: 找满足 chk(mid)的最小的值

    1
    2
    3
    4
    5
    6
    7
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(chk(mid)) r = mid;
        else l = mid + 1;
    }

  • 模板二: 找满足chk(mid)的最大的值

    1
    2
    3
    4
    5
    6
    7
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(a[mid] <=  x) l = mid;
        else r = mid - 1;
    }

5.2 浮点数二分

浮点数二分没有边界问题，放心二分就可以了

比如下面求数的三次方根的问题 

1
2
3
4
5
6
7
double l = -10000, r = 10000;
    while(r - l > 1e-8)
    {
        double mid = (r + l) / 2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }

6. 高精度

高精度指的是大整数的加减乘除，超出了64位整型的存储范围，Java和python都有大整数，是不用考虑这个问题的，但是c++有这个限制

下面的都没啥算法可言，就是简单模拟人手动加减乘除，但是注意存储方式，是低位在前，方便计算

6.1 高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> add(vector<int>& a, vector<int>& b)
{
    int i = 0, t = 0;
    vector<int> c;
    while(i < a.size() || i < b.size())
    {
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
        i ++;
    }
    if(t) c.push_back(1);
    return c;
}

6.2 高精度减法

要先实现一个比较函数，比较两个数的大小，这个板子是大的为a，小的是b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int cmp(vector<int>& a, vector<int>& b)
{
    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 0;
}
vector<int> sub(vector<int>& a, vector<int>& b)
{
    int t = 0, i = 0;
    vector<int> c;
    while(i < a.size())
    {
        t += a[i];
        if(i < b.size()) t -= b[i];
        c.push_back(( t + 10 ) % 10);
        if(t >= 0) t = 0;
        else t = -1;
        i ++ ;
    }
    while(c.size() > 1&& c.back() == 0) c.pop_back(); // 去除前导0
    return c;
}

6.3 高精度乘法

这里是一个大数乘一个小数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> mul(vector<int>& a, int b)
{
    int i = 0, t = 0;
    vector<int> c;
    while(i < a.size() || t)
    {
        if(i <a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
        i ++ ;
    }
    while(c.size() > 1 &&  c.back() == 0) c.pop_back();
    return c;
}

6.4 高精度除法

这里是一个大数据除以一个小数据， 要保留一下余数

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

7. 前缀和与差分

前缀和就是一个数组的前面一部分的和，$S_i = \sum_{i=0}^{i} a_i$

有前缀和就可以轻松算出$\sum_{i=l}^{r}a_i = S_r - S_{l -1}$

差分是前缀和的逆运算，简单说就是构造一个数组，使得这个数组得前缀和是给定的数组，这样，我需要在原数组上的一段区间内加上一个数的时候，只需要操作差分数组的两个端点就好啦，可以将时间复杂度从$O(N)$降到$O(1)$

7.1 一维前缀和

$h_i = h_{i - 1} + a_i$

$\sum_{i=l}^{r}a_i = S_r - S_{l -1}$

7.2 二维前缀和

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

7.1 一维差分

d[l] += c

d[r + 1] -= c

7.2 二维差分

d[x1][y1] += c

d[x2+1][y1] -= c

d[x1][y2+1] -=c

d[x2 + 1][y2 + 1] -= c

8. 双指针算法

双指针算法一般是将一个遍历两重优化成一重循环的算法，可以将$O(N^2)$ 优化为 $O(N)$

双指针算法的本质是单调性，即一个指针前进时，发现另外一个指针至少不会后退，这样就可以进行双指针优化了

所以设计双指针算法的一般步骤是

  • 先设计一个暴力的算法
  • 发现指针之间的单调关系
  • 进行优化

下面提供常见的一些写法

  • 查找最长不重复子序列长度

    1
    2
    3
    4
    5
    6
    for(int i = 0, j = 0; i < n; i ++ )
        {
            s[a[i]] ++ ; // 刚进来记录一下
            while(j < n && s[a[i]] > 1) s[a[j++]] --; // 将指针前移
            res = max(res, i - j + 1);
        }

  • 判断一个字符串是否是另一个字符串的子序列（注意不是子串，子序列只要顺序相同就行，不一定连续）

    1
    2
    3
    4
    5
    6
    7
    int i = 0, j = 0;
    while(i < n && j < m)
    {
        while(j < m && a[i] != b[j]) j ++ ;
        if(j == m) break;
        j ++ , i ++ ;
    }

9. 位运算

  • 取出最低是1的位 $lowbit(x) = x & (-x) = x &( \sim x + 1)$
  • 取出第k位是啥 x >> k & 1

10. 离散化

离散化适用于，数据范围很大，我们需要这些数据作为数组下标，但是数据的个数比较少的情况，这样我们可以使用离散化。

离散化是一种特殊的哈希，只不过哈希是不用保序的，而离散化需要保序，因为需要数据作为下标

是一种映射关系，将大的不连续的坐标映射到了小的连续的坐标

离散化两个重要操作

  • 去重

    1
    2
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

  • 查找，使用二分查找即可，查找大的x坐标，对应到小坐标里是那个坐标

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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; // 从1开始就加1，从0开始就不用加1
    }

11. 区间合并

给你一堆区间，有相连的就要合并，不相连就不合并，问合并之后的区间是多少

典型的贪心问题

  • 先将所有的区间按照左端点排序
  • 维护一个区间
  • 若当前区间的左端点比维护的区间的右端点还要靠右，就是一个新的区间了
  • 若当前区间的左端点在维护的区间内，则只需更新一下当前正在维护区间的右端点即可

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge(vector<PII>& segs)
{
    int st = -2e9, ed = -2e9;
    sort(segs.begin(), segs.end());
    vector<PII> res;
    for(auto& [l, r] : segs)
    {
        if(ed < l)
        {
            if(st != -2e9) res.push_back({st,ed});
            st = l, ed = r;
        }
        else ed = max(ed, r);
    }
    if(st != -2e9) res.push_back({st,ed});
    segs = res;
}
  • © 2019-2022 Wendell
  • Powered by Hexo Theme Ayer

请我喝杯咖啡吧~

支付宝
微信