5、基础算法

注意：红色都是重点题目

一、二分查找

二、基础排序

2.1 直接插入排序

void insert_sort(int q[], int len) {
    for (int i = 1; i < len; i++)
        if (q[i] < q[i - 1]) {
            int tmp = q[i], j;
            for (j = i - 1; j >= 0 && q[j] > q[i]; j--)
                q[j + 1] = q[j];
            q[j + 1] = tmp;
        }
}
1
2
3
4
5
6
7
8
9

2.2 希尔排序（考察过读代码）

void shell_sort(int q[], int n) {
    int d = 1;
    while (d < n / 3) d = d * 3 + 1;
    while (d > 0) {
        for (int i = d; i < n; i++) {
            int tmp = q[i], j = i;
            while (j >= d && q[j - d] > tmp)
                q[j] = q[j - d], j -= d;
            q[j] = tmp;
        }
        d /= 3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 冒泡排序

void bobble_sort(int q[], int n) {
    for (int i = 0; i < n; i++) {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
            if (q[j - 1] > q[j]) {
                flag = true;
                int tmp = q[j - 1];
                q[j - 1] = q[j];
                q[j] = tmp;
            }
        if (!flag) return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.4 快速排序

Acwing 785

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);
        if (i < j) {
            int tmp = q[i];
            q[i] = q[j], q[j] = tmp;
        }
    }
    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

2.4.1 查找数组中第 k 大的数

Acwing 786

#include 
#include 
using namespace std;

const int N = 1e5 + 10;

int n, k, a[N];

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

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    printf("%d\n", quick_sort(a, 0, n - 1, k));
    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

2.4 2 按奇偶排序

Leetcode 905

不知道 $leetcode$ 上为什么会报错

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int i = -1, j = nums.size();
        while (i < j) {
            do i ++ ; while (nums[i] % 2 == 0);
            do j -- ; while (nums[j] % 2 != 0);
            if (i < j) swap(nums[i], nums[j]);
        }
        return nums;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

2.5 简单选择排序

void select_sort(int q[], int n) {
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (q[j] < q[min])
                min = j;
        if (min != i) swap(q[min], q[i]);
    }
}
1
2
3
4
5
6
7
8
9

2.6 堆排序

Acwing 838

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], cnt;

void up(int u) {
    while (u / 2 && h[u / 2] > h[u])
        swap(h[u / 2], h[u]), u /= 2;
}

void down(int u) {
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) swap(h[u], h[t]), down(t);
}

int main() {
    scanf("%d%d", &n, &m);
    cnt = n;
    for (int i = 1; i <= n; i++) scanf("%d", h + i);
    for (int i = n / 2; i; i--) down(i); // 建堆
    while (m--) {
        printf("%d ", h[1]);
        h[1] = h[cnt];
        cnt--;
        down(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

2.7 归并排序

Acwing 787

// 数组版本
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, nums[N], tmp[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 = 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", nums + i);
    merge_sort(nums, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", nums[i]);
    puts("");
    return 0;
}

// 不带头结点的链表版本（早年考过）
LNode *merge_sort(LNode *head) {
    if (!head || !head->next) return head; // 只有一个结点
    LNode *fast = head->next, *slow = head;
    while (fast && fast->next) fast = fast->next->next, slow = slow->next;
    LNode *tmp = slow->next;
    slow->next = nullptr;
    LNode *left = merge_sort(head), *right = merge_sort(tmp);
    LNode *h = new LNode(0);
    LNode *res = h;
    while (left && right) {
        if (left->val < right->val) h->next = left, left = left->next;
        else h->next = right, right = right->next;
        h = h->next;
    }
    h->next = left != nullptr ? left : right; // 将剩余结点插入
    return res->next;
}
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

2.7.1 寻找逆序对

Acwing 107

#include 
#include 

using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int n;
LL 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);
    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, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i++) scanf("%d", q + i);
        printf("%lld\n", merge_sort(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
32
33
34
35

三、KMP

Acwing 831

#include 
#include 

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M];
int ne[N];

int main() {
    scanf("%d%s%d%s", &n, p + 1, &m, s + 1);
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n) {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    puts("");
    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

四、双指针经典问题

4.1 最长连续不重复子序列

Acwing 799

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], s[N]; // q存储元素，s记录元素q[i]出现次数

int main() {
    scanf("%d", &n);
    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        scanf("%d", q + i);
        s[q[i]]++;
        while (s[q[i]] > 1) s[q[j++]]--;
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.2 数组元素的目标和

Acwing 800

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

int main() {
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < m; i++) scanf("%d", b + i);
    for (int i = 0, j = m - 1; i < n; i++) {
        while (j && a[i] + b[j] > x) j--;
        if (j && a[i] + b[j] == x) printf("%d %d\n", i, j);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.3 判断子序列

Acwing 2816

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < m; i++) scanf("%d", b + i);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] == b[j]) i++;
        j++;
    }
    i == n ? puts("Yes") : puts("No");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.4 颜色分类（荷兰旗问题）

Leetcode 75

class Solution {
public:
    void sortColors(vector<int> &nums) {
        for (int i = 0, j = 0, k = nums.size() - 1; i <= k;) {
            if (!nums[i]) swap(nums[i++], nums[j++]);
            else if (nums[i] == 2) swap(nums[i], nums[k--]);
            else i++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10

4.5 最小面积子矩阵

Acwing 3487

#include 
#include 

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, k;
int s[N][N];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1][j];
        }
    int res = INF;
    for (int x = 1; x <= n; x++)
        for (int y = x; y <= n; y++)
            for (int i = 1, j = 1, sum = 0; i <= m; i++) {
                sum += s[y][i] - s[x - 1][i];
                while (sum - (s[y][j] - s[x - 1][j]) >= k)
                    sum -= s[y][j] - s[x - 1][j], j++;
                if (sum >= k) res = min(res, (y - x + 1) * (i - j + 1));
            }
    res == INF ? puts("-1") : printf("%d\n", res);
    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

4.6 连续子数组的最大和

Acwing 55

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int res = INT_MIN, last = 0;
        for (auto x: nums) {
            last = max(last, 0) + x;
            res = max(res, last);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

4.7 最大的和

ACwing 126

#include 
#include 
#include 

using namespace std;

const int N = 110;

int n, g[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &g[i][j]);
            g[i][j] += g[i - 1][j];
        }
    int res = INT_MIN;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            int last = 0;
            for (int k = 1; k <= n; k++) {
                last = max(last, 0) + g[j][k] - g[i - 1][k];
                res = max(res, last);
            }
        }
    printf("%d\n", res);
    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

五、并查集（简单应用）

5.1 合并集合

Acwing 836

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m, p[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        int pa = find(a), pb = find(b);
        if (*op == 'M') p[pa] = pb;
        else pa == pb ? puts("Yes") : puts("No");
    }
    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

5.2 格子游戏

Acwing 1250

#include 
#include 

using namespace std;

const int N = 40010;

int n, m, p[N];

int get(int x, int y) {
    return x * n + y;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n * n; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        int x, y;
        char d[2];
        scanf("%d%d%s", &x, &y, d);
        x--, y--;
        int a = get(x, y), b;
        if (*d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            printf("%d\n", i);
            return 0;
        }
        p[pa] = b;
    }
    puts("draw");
    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

5.3 连通块中结点个数

Acwing 837

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;
    while (m--) {
        char op[5];
        int a, b;
        scanf("%s", op);
        if (*op == 'C') {
            scanf("%d%d", &a, &b);
            int pa = find(a), pb = find(b);
            if (pa == pb) continue;
            cnt[pb] += cnt[pa];
            p[pa] = pb;
        } else if (op[1] == '1') {
            scanf("%d%d", &a, &b);
            find(a) == find(b) ? puts("Yes") : puts("No");
        } else {
            scanf("%d", &a);
            printf("%d\n", cnt[find(a)]);
        }
    }
    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

六、字符串哈希

Acwing 841

#include 
#include 

using namespace std;

typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        get(l1, r1) == get(l2, r2) ? puts("Yes") : puts("No");
    }
    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

七、基本数据结构实现

7.1 单链表

Acwing 826

#include 

using namespace std;

const int N = 1e5 + 10;

// head 表示头结点
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少
// idx 存储当前已经用到了哪个结点
int head, e[N], ne[N], idx;

void init() { head = -1, idx = 0; }

// 将x插到头结点
void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx++; }

// 将x插到下标是k的结点后面
void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx++; }

// 将下标是k的结点后面的结点删除
void remove(int k) { ne[k] = ne[ne[k]]; }

int main() {
    int m;
    scanf("%d", &m);
    init();
    while (m--) {
        int k, x;
        char op[2];
        scanf("%s", op);
        if (*op == 'H') {
            scanf("%d", &x);
            add_to_head(x);
        } else if (*op == 'D') {
            scanf("%d", &k);
            if (!k) head = ne[head];
            else remove(k - 1);
        } else {
            scanf("%d%d", &k, &x);
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) printf("%d ", e[i]);
    puts("");
    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

7.3 散列表

Acwing 840

拉链法模拟

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 3;

int h[N], e[N], ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x) return true;
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') insert(x);
        else find(x) ? puts("Yes") : puts("No");
    }
    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

开放地址法模拟

$find()$ 函数的作用：如果数组中存在查找的值，返回查找的地址，如果不存在，该地址即为插入数值的地址。

#include 
#include 
#include 

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;

int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (k == N) k = 0;
    }
    return k;
}

int main() {
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I') h[k] = x;
        else h[k] != null ? puts("Yes") : puts("No");
    }
    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

八、单调栈与单调队列简单应用

8.1 找出序列中每个数左边第一个比它小的数

Acwing 832

#include 
#include <algorithm

using namespace std;

const int N = 1e5 + 10;

int stk[N], tt;

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt--;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[++tt] = x;
    }
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.2 滑动窗口

Acwing 154

#include 
#include 

using namespace std;

const int N = 1e6 + 10;

int n, k;
int a[N], q[N]; // q是队列(队列里面存储的是元素的下标)

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");
    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