算法基础课(持续更新中)

发表于 更新于 分类于 阅读次数：
| 置顶
本文字数： 4.8k 阅读时长 ≈ 9 分钟

算法基础课

基础算法（一）

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort(int q[],int l,int r)
{
    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);
    }
    
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

归并排序

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

二分

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

基础算法（二）

高精度

高精度加法

本质上是模拟人进行列竖式加法的过程，即$a_1$+…+$a_n$+t，其中当$a$的退一位加起来不超过10则$t=0$否则$t=1$，以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<vector>

using namespace std;

vector<int>add(vector<int>&A,vector<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(1);//最后一个t代表最高位，因此等for循环运行完后再用判断看看进位情况，是的话就在vector后面再加一个1
    return C;
}

int main()
{
    string a,b;
    vector<int>A,B;
    cin>>a>>b;
    
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
//A、B元素进栈都是逆序进栈，比如a='123456',那A=[6.5,4,3,2,1],目的是方便进位多了1的时候整体数组挪动空间不大，否则要是最高位在前边ta进位后面数组所有数字都要往后挪
    
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    return 0;
}
vector相关知识点

  • vector定义 vector 是 C++ 标准模板库（STL）中的一个容器，它可以看作是一个动态数组。它能存储一系列相同类型的元素，并且可以根据需要自动调整大小。使用 vector 需要包含 <vector> 头文件。

  • vector数组相关操作（最后面）增加用.push_back(一个数)，（最后面）删除.pop_back(一个数)，指定位置插入.insert(向量,指定位置)，指定位置删除.erase(向量，指定位置)，清空.clear()，查看大小.size()

  • vector元素的索引和数组一样，也是从 0 开始存储的

  • vector和普通数组区别

    1.大小灵活性

    • 普通数组：大小在定义时就必须确定，且在程序运行过程中不能改变。例如 int arr[10]; 定义了一个大小为 10 的整数数组，之后无法再改变其大小。
    • vector：可以动态调整大小。可以使用 push_back() 方法在末尾添加元素，当空间不足时，vector 会自动分配更大的内存空间来存储元素。

    2.内存管理

    • 普通数组：由程序员手动管理内存。如果数组在栈上分配，其生命周期受限于所在的代码块；如果在堆上分配（使用 new），则需要手动使用 delete 释放内存，否则会造成内存泄漏。
    • vector：自动管理内存。当 vector 不再使用时，其占用的内存会自动释放，无需程序员手动干预。

    3.功能丰富度

    • 普通数组：只提供基本的元素访问功能，操作相对有限。
    • vector：提供了丰富的成员函数，如 size() 获取元素数量、empty() 判断是否为空、clear() 清空元素等，使用起来更加方便。

  • 使用 vector 而不用数组的原因

    在大整数相加的场景中，输入的数字长度是不确定的。如果使用普通数组，需要预先定义一个足够大的数组来存储数字的每一位，但这样可能会浪费大量的内存空间。而 vector 可以根据输入数字的实际长度动态调整大小，避免了内存的浪费，并且其提供的 push_back() 方法可以方便地将数字的每一位添加到容器中，同时在处理进位时也更加方便。因此，使用 vector 能更好地适应这种动态长度的需求。

add函数运行示例

假设我们要计算两个四位数 a = 1234 和 b = 5678 的和。

在代码中，输入的数字以字符串形式存储，然后将其逆序存储到 vector<int> 中，这样做是为了方便处理进位。对于 a = 1234，存储在 vector<int> 中为 A = {4, 3, 2, 1}；对于 b = 5678，存储在 vector<int> 中为 B = {8, 7, 6, 5}。

具体步骤：

  • [x] 初始化

  • vector<int> C;：用于存储相加结果的向量，初始为空。

  • int t = 0;：用于存储每一位相加后的结果以及进位信息，初始值为 0。

  • [x] 循环处理每一位

循环条件为 i < A.size() || i < B.size()，这意味着只要 A 或 B 还有未处理的位，就会继续循环。

  • [ ] 第一次循环（i = 0）

  • if(i < A.size()) t += A[i];：因为 i = 0 小于 A.size()（4），所以 t = t + A[0] = 0 + 4 = 4。

  • if(i < B.size()) t += B[i];：因为 i = 0 小于 B.size()（4），所以 t = t + B[0] = 4 + 8 = 12。

  • C.push_back(t % 10);：将 t % 10（即 2）添加到 C 中，此时 C = {2}。

  • t /= 10;：t 除以 10，得到进位 1，即 t = 1。

  • [ ] 第二次循环（i = 1）

  • if(i < A.size()) t += A[i];：t = t + A[1] = 1 + 3 = 4。

  • if(i < B.size()) t += B[i];：t = t + B[1] = 4 + 7 = 11。

  • C.push_back(t % 10);：将 t % 10（即 1）添加到 C 中，此时 C = {2, 1}。

  • t /= 10;：t 除以 10，得到进位 1，即 t = 1。

  • [ ] 第三次循环（i = 2）

  • if(i < A.size()) t += A[i];：t = t + A[2] = 1 + 2 = 3。

  • if(i < B.size()) t += B[i];：t = t + B[2] = 3 + 6 = 9。

  • C.push_back(t % 10);：将 t % 10（即 9）添加到 C 中，此时 C = {2, 1, 9}。

  • t /= 10;：t 除以 10，得到进位 0，即 t = 0。

  • [ ] 第四次循环（i = 3）

  • if(i < A.size()) t += A[i];：t = t + A[3] = 0 + 1 = 1。

  • if(i < B.size()) t += B[i];：t = t + B[3] = 1 + 5 = 6。

  • C.push_back(t % 10);：将 t % 10（即 6）添加到 C 中，此时 C = {2, 1, 9, 6}。

  • t /= 10;：t 除以 10，得到进位 0，即 t = 0。

  • [x] 处理最后可能的进位

if(t) C.push_back(1);

因为此时 t = 0，所以不需要添加额外的进位，C 仍然为 {2, 1, 9, 6}。

  • [x] 返回结果

return C;：返回存储相加结果的向量 C。

在 main 函数中，将 C 逆序输出，得到最终结果 6912，即 1234 + 5678 = 6912。

auto的用法

auto是C++11的新特性，可以自动识别变量属性。比如auto C=add(A,B);就自动识别了add返回的类型，因此auto C <=> vector<int>c

a[i] - '0' 的作用：将字符串每一位由ASCII码转为整数

在 C++ 中，当你从输入读取一个数字字符串时，比如 "123"，字符串中的每个字符（如 '1'、'2'、'3'）实际上存储的是字符的 ASCII 码值，而不是对应的数值。字符 '0' 到 '9' 的 ASCII 码是连续的，'0' 的 ASCII 码值是 48，'1' 是 49，以此类推，'9' 是 57。

b[i] - '0' 的作用就是将字符形式的数字转换为对应的整数值。例如，当 b[i] 为 '1' 时，'1' 的 ASCII 码值是 49，'0' 的 ASCII 码值是 48，那么 '1' - '0' 就等于 49 - 48 = 1，这样就把字符 '1' 转换为了整数 1。

如果没有 b[i] - '0' 这个操作，直接将字符存储到 vector<int> 中，那么存储的是字符的 ASCII 码值，而不是对应的数值，这会导致后续的计算出现错误。

高精度减法

高精度乘法

高精度除法