C++ 算法基础课 01 —— 基础算法_快速排序/归并排序/二分查找/高精度

理解思想，默写代码模板，写出来调试通过，同一个题可以写3-5次

1 排序

1.1 快速排序(难在划分)

• 快速排序的核心是分治思想：假设我们的目标依然是按从小到大的顺序排列，我们找到数组中的一个分割值，把比分割值小的数都放在数组的左边，把比分割值大的数都放在数组的右边，这样分割值的位置就被确定。数组一分为二，我们只需排前一半数组和后一半数组，复杂度直接减半。采用这种思想，不断的进行递归，最终分割得只剩下一个元素时，整个序列自然就是有序的。
  
• 左边指针 i 不满足小于分界值就停下来，然后右边指针j移动，遇到不满足大于分界值就停下来，接着交换指针 i 和指针 j 互相所指的值，交换完之后，指针 i 和 j 均移动一位。
• 用指针 j 来划分，左边是小于等于分界值，右边大于等于分界值。就是 i 指针左边的数一定小于等于分界值，j 指针右边的数一定大于等于分界值。

1.1.1 模板

• i + r >> 1：i + r 的值右移1位，相当 i + r 的值除以2取整，int是向下取整的函数
  i + r >> 1解释
• 模板1：quick_sort(q, l, j)，x = q[l]或者q[l + r >> 1]
• 当下面递归取 j 时，x 不能取 x = q[r]作为边界

void quick_sort(int q[], int l, int r)// l 是左指针， r是右指针
{
    if (l >= r) return 0;// 左指针 > 右指针时，返回

	// 当x = q[l]里面是左边界l, 则quick_sort(q,l,j)最后必须是j
	// quick_sort(q, l, j)时，x = q[l]或者q[l + r >> 1]均是可以的
    int i = l - 1, j = r + 1, x = q[l + r >> 1];// 右移1位，相当于i + r的值除以2取整
    while (i < j)
    {
        do i ++ ; while (q[i] < x);// 一直做i++,直到找到大于等于x的值，然后再进行j--
        do j -- ; while (q[j] > x);// 做完i++,才做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, i - 1) 写成i - 1是可以的,同时必须修改x = q[l] 为 int x = q[(l + r + 1) / 2]，否则出现边界问题
    // quick_sort(q, i, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 模板2：quick_sort(q, l, i - 1)，x = q[l]或者q[l + r >> 1]
• 当下面递归取 i 时，x 不能取 x = q[l]作为边界

void quick_sort(int q[], int l, int r)// l 是左指针， r是右指针
{
    if (l >= r) return;// 左指针 > 右指针时，返回
    
	// 当x = q[r]里面是右边界r时, 则quick_sort(q,l,i-1)
	// quick_sort(q, l, i - 1)时，x = q[l]或者q[l + r >> 1]均是可以的
	int x = q[(l + r + 1) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do i ++ ; while (q[i] < x);// 一直做i++,知道找到大于等于x的值，然后再进行j++
        do j -- ; while (q[j] > x);// 做完i++,才做j++,直到找到小于等于x的值
        if (i < j) swap(q[i], q[j]);// 找到之后，进行交换
    }
    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.1.2 习题1 —— 785.快速排序

Acwing 785.快速排序

#include
using namespace std;
const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return 0;
    
    // int x = q[l + r >> 1] 也可以
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;// 数据加强了，x不能取边界值
    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);
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n; i++) scanf("%d",&q[i]);
    
    quick_sort(q, 0, n - 1);
    for(int i = 0;i < n; i++) printf("%d ",q[i]);
    
    return 0;
} 
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

1.1.3 习题2 —— 786.第k个数(快速选择算法)

Acwing 786.第k个数

• 左半边的左边界是l，右边界是j
  

#include
using namespace std;

const int N = 100010;
int n, k;
int q[N];

int quick_sort(int l, int r, int k)
{
    if(l == r) return q[l];
    int x = q[(l + r)/2], i = l - 1, j = r + 1;// 双指针方式，x是分界点，区分不同的值
    while(i < j)
    {
        while(q[++i] < x);// 找到小于x的坐标值
        while(q[--j] > x);// 找到大于x的坐标值
        if(i < j) swap(q[i],q[j]);
    }
    
    int sl = j - l + 1;// sl部分数的个数
    if(k <= sl) return quick_sort(l, j, k);// k小于s1就在左半区间找
    
    return quick_sort(j + 1, r, k - sl);// 否则返回右半区间
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> q[i];
    cout << quick_sort(0, n - 1, k) << endl;// 0是左边界，n-1是右边界
    return 0;
}
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

1.2 归并排序(难在合并)

• 难点在于如何把有序的序列合二为一
  
• 举例
  

1.2.1 模板

void merge_sort(int q[], int l, int r)// q是要排序的数组，l和r使左右闭区间
{
    if (l >= r) return;// 判断当前区间

    int mid = l + r >> 1;// 取区间的中点，相当于i + r的值除以2向下取整
    merge_sort(q, l, mid);// 左边递归排序，已经排好顺序
    merge_sort(q, mid + 1, r);// 右边递归排序，已经排好顺序

	// 归并合二为一
    int k = 0, i = l, j = mid + 1;// k表示tmp中合并数字的个数，i是左指针，j是右指针
    while (i <= mid && j <= r) // 左半边边界和右半边边界
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
        
	// 左右两边有一边没有循环结束的话，接到tmp后面去
    while (i <= mid) tmp[k ++ ] = q[i ++ ];// 如果左边没有循环结束，加入到tmp中
    while (j <= r) tmp[k ++ ] = q[j ++ ];// 右边没有循环结束也加入进去

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];// 把结果从tmp中拿回到q里面
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2.2 习题1 —— 787.归并排序

Acwing 787.归并排序

#include
using namespace std;

const int N = 1000010;

int n;
int q[N],tmp[N];

void merge_sort(int q[],int l, int r)
{
    if(l >= r) return;
    
    int mid = l + r >> 1;// 就是 L+R 然后除以2
    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 = l,j = 0;i <= r; i++, j++) q[i] = tmp[j];
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n; i++) scanf("%d",&q[i]);
    
    merge_sort(q, 0, n - 1);
    for(int i = 0;i < n; i++) printf("%d ",q[i]);
    
    return 0;
}
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
36
37
38
39

1.2.3 习题2 —— 788.逆序对的数量

Acwing 788.逆序对的数量

• 解题思路
  

#include
using namespace std;

typedef long long LL;

const int N = 100010;// 数据范围是100000

int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if(l >= r) return 0;
    
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);// 这里res的数据类型是LL
    
    // 归并过程
    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++];
            res += mid - i + 1;// 根据公式得来的
        }
    }
    
    // 扫尾
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    // 物归原主
    for(int i = l, j = 0;i <= r;i++, j++) q[i] = tmp[j];// 这里的i是从l开始
    
    return res;
}

int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i ++) cin >> q[i];
    
    cout << merge_sort(0, n - 1) << endl;
    
    // for(int i = 0; i < n; i++) cout << q[i] << endl;
    
    return 0;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

2 二分查找(已经进行升序或者降序排列)

2.1 整数二分

• 如果遇到相同的数字，模板1可以求出数字的起始位置，模板2可以求出数字的终止位置。如果没有遇到数字重复的情况，则模板1和2均可以求出位置所在。
• 确定check(mid)条件，默写模板
• 最后的结果中 l = r，就是说左右会集合到同一个点

2.1.1 模板1(r = mid, mid = l + r >> 1）

• 条件是左边红色区域，x是初始比较的值，加如判断条件q[mid] >= x，那么true为 r = mid，否则 l = mid + 1。可以求出数字的起始位置
  

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 模板1
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;// int是向下取整
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.1.2 模板2(l = mid, mid = l + r + 1 >> 1)

• 条件是绿色区域，x是初始比较的值，加入判断条件q[mid] <= x，那么true为 l = mid，否则l r = mid - 1。可以求出位置的终止位置
  

// 模板2
// 区间[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

2.1.2 习题1 —— 789.数的范围

Acwing 789.数的范围

• 首先定义check(mid)的规则是 x 右边的数是 >= x，如果q[mid] >= x，表示答案x在左半边。
  
• 然后定义check(mid)的规则是 x 左边的数是 <= x，如果q[mid] <= x，表示答案x在右半边，x左边的数均满足 <= x。
  

#include
using namespace std;

const int N = 1e6 + 10;

int n, m;
int q[N];

int main()
{
    scanf("%d%d",&n, &m);// n表示多少个数字，m表示要查询的个数
    for(int i = 0;i < n; i++) scanf("%d",&q[i]);
    
    while(m--)// 有三个数需要查询
    {
        // 本题中 前一个3是用模板1求起始位置，后一个3是用模板2求终止位置
        int x;
        scanf("%d",&x);
        
        // 从前往后找
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;// (l + r)/2
            if(q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        
        if(q[l]!=x) cout << "-1 -1" << endl;// 这里输出q[l] = q[r]
        else
        {
            cout << l << " ";
            // 从后往前找
            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;
            }
            cout << l << endl;
        }
    }
    return 0;
}
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
36
37
38
39
40
41
42
43
44
45

2.2 浮点数二分

• 右边界不能小于1
  

2.2.1 模板

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;// 也可以输出 r
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.2 习题1(开根号)

• 不用考虑边界问题
  

#include
using namespace std;
int main()
{
	double x;
	cin >> x;
	
	double l = 0, r = x;
    while (r - l > 1e-8)// 如果结果保留6为小数，则写为e-8，多写两位
    {
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf",l);// 输出 l和r均可以
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2.3 习题2 —— 790.数的三次方根

Acwing 790.数的三次方根

#include
using namespace std;

int main()
{
    double x;
    cin >> x;
    
    double l = -10000, r = 10000;
    while(r - l > 1e-8)
    {
        double mid = (l + r)/2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf",l);// 输出 l和r均可以
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3 高精度

3.1 高精度加法

3.1.1 模板

// C = A + B, A >= 0, B >= 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.1.2 习题

Acwing 791.高精度加法

#include
#include
#include
using namespace std;

// C = A + B
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];// t存储Ai + Bi + 上一位的进位
        C.push_back(t%10);// 求余
        t /= 10;// 看是否有下一位的进位
    }
    if(t) C.push_back(1);// 最高位有没有进位
    return C;// 返回的是C的数组
}

int main()
{
    string a, b;
    vector<int>A, B;
    
    cin >> a >> b;// a = "123456", 字符串a可以当作字符数组来处理, 处理后
    // 将a[]中阿拉伯数字字符转换成int数字，需要减去'0'', A 结果是 [6, 5, 4, 3, 2, 1]，最低位是个位数，这种操作叫字符串转整型
    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');
    
    auto c = add(A,B);// auto 是自动推断变量的类型，auto 这里等价于 vector
    // 逆向输出，先输出最高位，因为之前的相加的结果的开头是最低位
    for(int i = c.size() - 1;i >= 0;i --)printf("%d",c[i]);// i从size - 1开始
    return 0;
}
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
36
37

3.2 高精度减法

• 假如给出A < B，则先计算B - A，再在前面加"-"。
• t 值的求法

3.2.1 模板

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];// 先判断B的位数是否存在
        C.push_back((t + 10) % 10);// 当t>=0时，直接赋值为t，当t<0时，t = t + 10，直接用(t+10)%10来表示这两种情况
        if (t < 0) t = 1;// t < 0，进一位，否则不进位
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2.2 习题

Acwing 792.高精度减法

#include
#include
#include
using namespace std;

// 判断是否有A >= B，假定A和B都是正数
bool cmp(vector<int>&A, vector<int>&B)
{
    if(A.size() != B.size()) return A.size() > B.size();// 判断两者的位数，A的位数是否大于B
    for(int i = A.size() - 1; i >= 0; i--)// 从最高位开始比较，最高位在数组的最后的一位
        if(A[i] != B[i])
            return A[i] > B[i];// 返回同一位较大的值
    return true;
}

// C = A - B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0;i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];// 先判断B的位数是否存在
        C.push_back((t + 10)% 10);// 当t >= 0时，直接赋值为t，当t<0时，t = t + 10，直接用(t+10)%10来表示这两种情况
        if(t < 0) t = 1;// t < 0，向前借一位，否则不借位
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();// C.back表示最后一位等于零的话，就弹出来，就是要丢掉前导零，比如123 - 120 = 003，输出的结果C是300，去掉最后的两个零，变成3
    return C;
}

int main()
{
    string a, b;
    vector<int>A, B;
    
    cin >> a >> b;// a = "123456", 字符串a可以当作字符数组来处理, 处理后
    // 将a[]中阿拉伯数字字符转换成int数字，需要减去'0'', A 结果是 [6, 5, 4, 3, 2, 1]，最低位是个位数，这种操作叫字符串转整型
    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');
    
    if(cmp(A,B))// 判断A与B大小关系，在A >= B的情况下，再进行A - B的操作
    {
        auto c = sub(A,B);// auto 是自动推断变量的类型，auto 这里等价于 vector
        // 逆向输出，先输出最高位，因为之前的相加的结果的开头是最低位
        for(int i = c.size() - 1;i >= 0;i --)printf("%d",c[i]);// i 从size - 1开始
    }
    else
    {
        auto c = sub(B,A);
        printf("-");// 当 A < B时，先求B - A，再在前面添加"-"
        for(int i = c.size() - 1;i >= 0;i --)printf("%d",c[i]);// i从size - 1开始
    }
    return 0;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

3.3 高精度乘以低精度

3.3.1 模板

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        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();
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.3.2 习题

Acwing 793.高精度乘以低精度

#include
#include
using namespace std;

vector<int> mul(vector<int>&A, int b)
{
    vector<int> C;
    
    int t = 0;
    for(int i = 0;i < A.size() || t;i ++)// i没有循环完或者t不为零
    {
        if(i < A.size())t += A[i] * b;// t = A[i] * b + t
        C.push_back(t % 10);
        t /= 10;// t = t / 10
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();// C.back表示最后一位等于零的话，就弹出来，就是去掉前导零
    return C;
}

int main()
{
    string a;// 长数字用字符串处理，一般小数字用int保存
    int b;
    cin >> a >> b;
    
    vector<int>A;
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    
    auto C = mul(A,b);// 这里是A，就是处理后的vector数组
    for(int i = C.size() - 1;i >= 0;i --) printf("%d", C[i]);
}
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

3.4 高精度除以低精度

3.4.1 模板

// A / b = C ... r, A >= 0, b > 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.4.2 习题

#include
#include
#include
using namespace std;

// C = A / B, 商是C，余数是r。除法是从最高位开始计算
vector<int> div(vector<int>&A, int b, int &r)// r位引用
{
   vector<int>C;
   r = 0;// 刚开始余数位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;
}

int main()
{
    string a;// 长数字用字符串处理，一般小数字用int保存
    int b;
    cin >> a >> b;
    
    vector<int>A;
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    
    int r = 0;
    auto C = div(A,b,r);// 这里是A，就是处理后的vector数组
    
    for(int i = C.size() - 1;i >= 0;i --) printf("%d", C[i]);// 输出商
    cout << endl;
    cout << r << endl;// 输出余数
}
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
36
37