算法入门：时间复杂度与基础排序算法

空间复杂度分析

• 仅使用常数级别的额外空间（i, j 和 swapped 变量）。
• 空间复杂度：O(1)（原地排序）。

二、排序算法（入门级别）

排序是很实用的、常用的（几乎是必需品，只不过现在封装得很好，让你感觉不到）。

排序的学习可以让你了解一些算法的基本思想与操作技巧（暴力、比较、交换、分治、减治、空间换时间等）。

• 排序算法也是分析时间/空间复杂度的理想模型。
• 排序也是计算机科学早期研究的核心问题（如 1956 年希尔排序的提出）。

2.1 选择排序

排序算法中最简单直观的。

思路：不断缩小范围确定当前范围内的最小/最大值，随后将最小/最大值与目标位置进行交换。那么每一趟筛选的行为就是选出第 n 个最小/最大值！

举例： 从小到大排序下方数字

• 18、1、5、27、12（下标范围 0 ~ 4，最小值 1 与下标 0 的 18 交换）
• 1、18、5、27、12（下标范围 1 ~ 4，最小值 5 与下标 1 的 18 交换）
• 1、5、18、27、12（下标范围 2 ~ 4，最小值 12 与下标 2 的 18 交换）
• 1、5、12、27、18（下标范围 3 ~ 4，最小值 18 与下标 3 的 27 交换）
• 1、5、12、27、18（下标范围 4 ~ 4，单个元素自然有序）

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

void select_sort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int pos = i; // 假设认为当前范围最小值 pos 就是当前范围的第一个数
        for (int j = i + 1; j < n; j++) {
            if (arr[pos] > arr[j]) { // 发现当前范围更小的数
                pos = j; // 记录这个数的下标
            }
        }
        // 交换这俩数
        int t = arr[i]; arr[i] = arr[pos]; arr[pos] = t;
    }
}

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    select_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2.2 冒泡排序

见名知意，冒泡就是说将目前第 n 个最大/最小的数，冒泡到顶端。如果顶端有了 k 个泡，那么就要排在 k 个泡之后成为第 k+1 个泡。

思路：由于每次冒泡都需要排在之前泡泡的后面，并且之前冒泡的数值肯定是合理的。所以缩小冒泡范围并把当前范围最小/最大的值，通过相邻元素两两交换最后冒泡到范围顶端。

举例： 从小到大排序下方数字

• 18、1、5、27、12 （下标范围 0 ~ 4，18 > 1 交换）1、18、5、27、12 （下标范围 0 ~ 4，18 > 5 交换）1、5、18、27、12 （下标范围 0 ~ 4，18 < 5 不交换）1、5、18、27、12 （下标范围 0 ~ 4，27 > 12 交换）1、5、18、12、27（第一个泡泡）
• 1、5、18、12、27 （下标范围 0 ~ 3，1 < 5 不交换）1、5、18、12、27 （下标范围 0 ~ 3，5 < 18 不交换）1、5、18、12、27 （下标范围 0 ~ 3，18 > 12 交换）1、5、12、18、27
• 1、5、12、18、27 （下标范围 0 ~ 2，1 < 5 不交换）1、5、12、18、27 （下标范围 0 ~ 2，5 < 12 不交换）1、5、12、18、27
• 1、5、12、27、18 （下标范围 0 ~ 1，1 < 5 不交换）1、5、12、18、27
• 1、5、12、18、27（下标范围 0 ~ 0，单个元素自然有序）

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

void bubble_sort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
            }
        }
    }
}

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    bubble_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2.2.1 稳定/不稳定排序的说法

如果一个排序算法在排序后能够保持相等元素的原始相对顺序，那么这个算法就是稳定的。

[("Alice",90),("Bob",85),("Chris",90),("Dave",80)]
// 稳定排序的升序（Alice 和 Chris 都是 90 分，Alice 原本在 Chris 前面，排序后仍然在前面。）
[("Dave",80),("Bob",85),("Alice",90),("Chris",90)].
// 不稳定排序的升序（可能 Alice 就在 Chris 的后面）
[("Dave",80),("Bob",85),("Chris",90),("Alice",90)]

2.3 插入排序

插入排序类似于两堆扑克牌，从无序列扑克牌堆里面选牌插入到有序扑克牌堆。

思路：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分找到合适的位置插入。

举例：从小到大排序下方数字

• 18、1、5、27、12（初始状态，第一个元素 18 视为已排序）
• 1、18、5、27、12（将 1 插入到 18 前面）
• 1、5、18、27、12（将 5 插入到 1 和 18 之间）
• 1、5、18、27、12（27 已经在正确位置）
• 1、5、12、18、27（将 12 插入到 5 和 18 之间）

#include <iostream>
using namespace std;
int arr[50];

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    for (int i = 1; i < n; ++i) {
        // 要插入的元素
        int t = arr[i]; // 存起来
        int j = i - 1; // 18 1 5 27 12
                       // 1 5 18 27 12
        for (; j >= 0; --j) {
            if (arr[j] > t) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = t;
    }
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

2.4 希尔排序

希尔排序是插入排序的改进版，通过分组（分治思想）让插入排序提高了效率。

思路：

1. 选择一个增量序列（通常为 n/2, n/4, …, 1）。
2. 依据每个增量去分组，然后将每组都进行插入排序。
3. 到最后增量为 1，也就是要进行一次完整的插入排序。

希尔排序会有一种假象：让初学者误认为嵌套循环多就是速度慢的、进而忽略了有序序列对插入排序具体实现过程的影响。

举例：从小到大排序下方数字 [18, 1, 5, 27, 12, 9, 6, 15]

1. 初始增量=4（数组长度 8/2）：
   • 分组：[18,12], [1,9], [5,6], [27,15]
   • 排序后：[12,18], [1,9], [5,6], [15,27]
   • 数组变为：[12, 1, 5, 15, 18, 9, 6, 27]
2. 增量=2：
   • 分组：[12,5,18,6], [1,15,9,27]
   • 排序后：[5,6,12,18], [1,9,15,27]
   • 数组变为：[5, 1, 6, 9, 12, 15, 18, 27]
3. 增量=1（标准插入排序）：
   • 最终排序结果：[1, 5, 6, 9, 12, 15, 18, 27]

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

void shell_sort(int* arr, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) { // 增量序列
        for (int i = gap; i < n; i++) { // 对每个分组进行插入排序
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    shell_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2.5 计数排序

核心思想：统计每个元素出现的次数，然后按顺序输出。

特点：

• 非比较排序，时间复杂度 O(n+k)，k 为数据范围。
• 适用于整数且范围不大的情况。
• 稳定排序。

void countingSort(int arr[], int n) {
    // 假设数据范围在 0 到 100 之间
    int count[101] = {0};
    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) count[arr[i]]++;
    // 按顺序填充原数组
    int index = 0;
    for (int i = 0; i <= 100; i++) {
        while (count[i]--) {
            arr[index++] = i;
        }
    }
}

2.6 归并排序（前置知识：双指针）

归并排序：应用快慢指针与递归去解决排序问题的算法。

#include <iostream>
using namespace std;
// 5 4 3 2 1
void merge_sort(int* arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    int tmp[10];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (arr[i] < arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];
    for (i = l, k = 0; i <= r; ++i, ++k) {
        arr[i] = tmp[k];
    }
}

int main(void) {
    int n;
    int arr[10]; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

2.7 快速排序（前置知识：双指针）

快速排序：应用左右指针与递归去解决排序问题的算法。

#include <iostream>
using namespace std;
// 5 4 3 2 1
void quick_sort(int* arr, int l, int r) {
    if (l >= r) return;
    int x = arr[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (arr[i] < x);
        do j--; while (arr[j] > x);
        if (i < j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

int main(void) {
    int n;
    int arr[10]; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    return 0;
}

三、大整数四则运算

接下来，继续锻炼模拟思维。

何为大整数：通常指的是非常大的整数，其值远超常规数据类型（如 32 位或 64 位整数）能直接表示的范围。

意义：

• 现代加密算法（如 RSA、ECC）依赖大质数或大整数运算，防止暴力破解。例如：RSA-2048 使用两个 1024 位的质数相乘，生成密钥。
• 精确计算极大数值（如天文数字、阶乘、斐波那契数列等）。

3.1 加法

大整数加法应该算是四个运算法则里，最好理解的了。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void) {
    string a, b; cin >> a >> b;
    vector<int> A;
    vector<int> B;
    // 做倒置存入到 vector 中（倒置是因为比较好处理，可以不倒置）
    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');
    }
    /* 4321 765 */
    int t = 0; // 维护进位值
    vector<int> C; // 存储最后结果
    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 > 0) C.push_back(t); // 若最后进位值还有，那么就属于进多了一位
    for (int i = C.size() - 1; i >= 0; --i) {
        cout << C[i];
    }
    return 0;
}

3.2 减法

大整数减法会遇到负数问题的处理，还有前置 0。关键点在于这里~

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 必须要判断出 A、B 两个数谁更大
bool isMax(vector<int> A, vector<int> B) {
    if (A.size() == B.size()) {
        for (int i = A.size() - 1; i >= 0; --i) {
            if (A[i] == B[i]) {
                continue;
            }
            return A[i] > B[i];
        }
        return true;
    } else {
        return A.size() > B.size();
    }
}

int main(void) {
    string a, b; cin >> a >> b;
    vector<int> A;
    vector<int> 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');
    }
    bool flag = isMax(A, B);
    if (!flag) // 如果 B 比 A 大则将他们交换，因为我们要默认 A - B 进行模拟运算
    {
        vector<int> temp = A;
        A = B;
        B = temp;
    }
    int t = 0; // 借位
    vector<int> C;
    for (int i = 0; i < A.size() || i < B.size(); ++i) {
        int num = -t;
        if (i < A.size()) num += A[i];
        if (i < B.size()) num -= B[i];
        if (num < 0) {
            t = 1;
            num += 10;
        } else {
            t = 0;
        }
        C.push_back(num % 10);
    }
    while (C.size() > 1 && C[C.size() - 1] == 0) {
        C.pop_back();
    }
    if (C.size() == 1 && C[0] == 0) {
        cout << 0 << endl;
        return 0;
    }
    if (!flag) cout << "-";
    for (int i = C.size() - 1; i >= 0; --i) {
        cout << C[i];
    }
    return 0;
}

3.3 乘法

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    string a, b; cin >> a >> b;
    vector<int> A;
    vector<int> 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');
    }
    /* 4321 765 */
    vector<int> C(1000005);
    if (A.size() < B.size()) swap(A, B);
    for (int i = 0; i < B.size(); ++i) {
        int j = 0;
        int t = 0;
        for (; j < A.size(); ++j) {
            int num = A[j] * B[i] + t;
            int ret = num % 10;
            t = num / 10;
            C[i + j] += ret;
            C[i + j + 1] += C[i + j] / 10;
            C[i + j] = C[i + j] % 10;
        }
        if (t > 0) C[i + j] += t;
    }
    bool flag = true;
    for (int i = A.size() + B.size(); i >= 0; --i) {
        if (i > 0 && flag && C[i] == 0) {
            continue;
        }
        if (flag && C[i] != 0) {
            flag = false;
        }
        cout << C[i];
    }
    return 0;
}

3.4 除法

除法这里用到了大整数减法。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 比较两个大整数
bool isGreaterOrEqual(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 true;
}

// 减法函数
vector<int> subtractBigInt(vector<int> A, vector<int> B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); ++i) {
        int num = -t;
        if (i < A.size()) num += A[i];
        if (i < B.size()) num -= B[i];
        if (num < 0) {
            t = 1;
            num += 10;
        } else {
            t = 0;
        }
        C.push_back(num % 10);
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// 除法函数
pair<vector<int>, vector<int>> divideBigInt(vector<int> dividend, vector<int> divisor) {
    vector<int> quotient;
    vector<int> remainder = dividend;
    if (!isGreaterOrEqual(remainder, divisor)) {
        return {vector<int>{0}, remainder};
    }
    vector<int> current;
    for (int i = remainder.size() - 1; i >= 0; --i) {
        current.insert(current.begin(), remainder[i]);
        while (current.size() > 1 && current.back() == 0) current.pop_back();
        int q = 0;
        while (isGreaterOrEqual(current, divisor)) {
            current = subtractBigInt(current, divisor);
            q++;
        }
        quotient.push_back(q);
    }
    reverse(quotient.begin(), quotient.end());
    while (quotient.size() > 1 && quotient.back() == 0) quotient.pop_back();
    return {quotient, current};
}

int main() {
    string a, b; cin >> a >> b;
    vector<int> 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');
    auto [quotient, remainder] = divideBigInt(A, B);
    cout << "Quotient: ";
    for (int i = quotient.size() - 1; i >= 0; --i) cout << quotient[i];
    cout << "\nRemainder: ";
    for (int i = remainder.size() - 1; i >= 0; --i) cout << remainder[i];
    return 0;
}

四、数组基本操作

4.1 增删改查

• 增

int arr[50]; // 开辟足够大的数组
int arr[2] = {5}; // 比如现在有两个元素了，我们增加一个元素。那就是 为下标 2 赋值

• 删

// 通过覆盖元素实现删除
int arr[50] = {1, 2, 3, 4, 5};
// 起始位置为待删除元素位置 终止位置为最后元素位置
for (int i = 0; i < n; ++i) {
    arr[i] = arr[i + 1];
}
// 由于删掉一个元素 所以长度 从 n => n - 1
for (int i = 0; i < n - 1; ++i) {
    cout << arr[i] << " ";
}

• 改

arr[5] = 18; // 改就是重新赋值

• 查

cout << arr[5] << endl; // 直接访问即可

4.2 数组元素交换与自身插入

• 数组元素交换

// 其实就是依赖于下标找到 A 和 B 然后进行 交换操作
int temp = arr[2]; arr[2] = arr[3]; arr[3] = temp;

• 自身插入：在一个数组中，A 元素要插入到 B 元素的前面或后面

// 这个主要用的是 与删除操作 元素覆盖逆着来的写法。
// 比如我们要把下标 3 的元素 插入到目前下标为 1 的前面
int t = arr[3];
for (int i = 3 - 1; i >= 1; --i) {
    arr[i + 1] = arr[i]; // 这个元素覆盖就是从左往右覆盖的 (由于会覆盖掉待移动的元素，所以我们提前用 变量 t 存储起来了)
}
arr[1] = t; // 从下标 1 开始都整体往右移动了一位，所以我们只需要将 下标 1 位置重新赋值为 t 即可完成需求
// 比如我们要把下标 3 的元素 插入到目前下标为 1 的后面
int t = arr[3];
for (int i = 3 - 1; i > 1; --i) {
    arr[i + 1] = arr[i]; // 这个元素覆盖就是从左往右覆盖的 (由于会覆盖掉待移动的元素，所以我们提前用 变量 t 存储起来了)
}
arr[1 + 1] = t;

4.3 实现动态数组

动态数组是普通数组的增强版。

主要它是要实现以下几个扩展功能：

• 自动扩容
• 增删改查方法
• size 方法

#include <iostream>
#include <cstring>
using namespace std;

template<typename T>
class DynamicArray {
private:
    T* data;
    size_t size;
    size_t capacity;

    // 扩容
    void reserve(size_t new_capacity) {
        if (new_capacity <= capacity) return;
        T* new_data = new T[new_capacity]; // 分配新内存
        for (size_t i = 0; i < size; i++) {
            new_data[i] = data[i];
        }
        delete[] data; // 释放旧内存
        data = new_data;
        capacity = new_capacity;
    }

public:
    DynamicArray(size_t init_capacity = 4) : size(0), capacity(init_capacity > 0 ? init_capacity : 4) {
        data = new T[capacity]; // 分配初始内存
    }

    // 析构函数（释放内存）
    ~DynamicArray() {
        delete[] data;
    }

    void push_back(const T& elem) {
        if (size >= capacity) {
            reserve(capacity * 2);
        }
        data[size++] = elem; // size 就是下标 size++ 就是数量
    }

    void remove(size_t index) {
        if (index >= size) {
            throw out_of_range("index out of bounds");
            return;
        }
        for (int i = index; i < size - 1; ++i) {
            data[i] = data[i + 1];
        }
        data[size - 1].~T(); // 调用析构函数
        size--; // 数量少了一个！
    }

    T& operator[](size_t index) {
        if (index >= size) {
            throw out_of_range("index out of bounds");
        }
        return data[index];
    }

    size_t get_size() const {
        return size;
    }

    size_t get_capacity() const {
        return capacity;
    }
};

int main(void) {
    DynamicArray<int> arr;
    arr.push_back(12);
    for (int i = 0; i < arr.get_size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

五、双指针

双指针严格来说不能是算法，它更像是一种技巧或思想。到后面的学习里，我们还会讲到贪心，它也是一种思想。双指针常被用于线性有单调性趋势遍历的优化之中！使其从 O(n^2) => O(n)。

5.1 快慢指针（龟兔指针）

概念：通过使用两个指针以不同的速度遍历数据结构（线性结构）。 —— 滑动窗口与快慢指针的思想就很类似。

检测链表是否有环 找链表中间节点 删除倒数第 N 个节点 判断是否为回文链表 寻找数组中重复元素

• 快指针：先行一步满足前置条件（探索者）快速遍历并检测符合条件的数据。
• 慢指针：配合快指针解决需求（建造者）维护已处理数据的正确边界。

利用两者之间的速度差，可以在某个时刻根据特殊规则，获得或处理某些数据。

大白话：根据需求，当发现只需要用一个变量，先行一步拿到前置条件，再用另一个变量配合该前置条件，就可以完成需求时，那么你应该尝试下快慢指针。

5.1.1 有序数组去重

#include <iostream>
using namespace std;
int arr[50];

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    if (n == 0) return 0; // 边界检查
    int i = 0; // 慢指针（为了配合快指针的）
    for (int j = 1; j < n; ++j) { // 快指针的目的是找到非重复项
        if (arr[j] != arr[i]) {
            // 找到之后，用非重复项覆盖掉重复项
            i++;
            arr[i] = arr[j]; // 覆盖重复项
        }
    }
    // 输出去重后的数组（前 i+1 个元素）
    for (int k = 0; k <= i; ++k) {
        cout << arr[k] << " ";
    }
    cout << endl;
    return 0;
}

5.1.2 数组的原地删除

原地删除某元素：比如数组 1,2,3,4,5,6,6,2,1,2,3,2 你就想把里面的 2 全部删掉。逆向思维去看，其实就是只保留不是 2 的元素。

#include <iostream>
using namespace std;

void remove_element(int arr[], int n, int val) {
    int slow = 0;
    for (int fast = 0; fast < n; ++fast) {
        // 快指针去遍历
        if (arr[fast] != val) {
            // 进行筛选
            arr[slow++] = arr[fast]; // 慢指针给数组重新赋值符合条件的 arr[fast]
        }
    }
}

5.1.3 最长连续不重复子序列（经典例题）

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main(void) {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int maxLen = 0; // 记录最长长度
    // n^3
    // n^2
    // 计数排序
    // n
    int cnt[maxN] = {0};
    int i = 0; // 慢指针
    for (int j = 0; j < n; ++j) {
        cnt[arr[j]]++;
        while (cnt[arr[j]] > 1) {
            cnt[arr[i]]--;
            i++;
        }
        if (maxLen < j - i + 1) maxLen = j - i + 1;
    }
    cout << maxLen << endl;
    return 0;
}

5.2 左右指针

左右指针是一种强大的算法技巧，其归属于双指针。特别适合处理数组和字符串问题。与快慢指针不同，左右指针同时从序列的两端向中间移动，形成 对称扫描！

左右指针最直接的应用就是：二分查找、二分法答案。

5.2.1 基础模板

void two_pointers(int* arr, int n) {
    int l = 0, r = n - 1; // r 是最后元素的下标
    while (l < r) {
        // 只要 l < r 就继续扫描
        if 左侧条件满足 {
            l++;
        }
        if 右侧条件满足 {
            r--;
        }
        // 当然可能同时满足（这个所谓的条件，都是人为定的）
    }
}

5.2.2 两数之和 II - 输入有序数组 (LeetCode 167)

题目：给定一个已按非递减顺序排列的整数数组 numbers，请你从数组中找出两个数，它们的和等于目标数 target。假设每个输入只对应唯一的答案，并且不能使用相同的元素两次。

那么这道题。如果暴力去做，怎么样也得 O(n^2)。但由于题目说提供的数据是有序的，就可以利用左右指针优化到 O(n)。

void two_sum(int* arr, int n, int target) {
    // 若升序，肯定遵循左小右大
    int l = 0, r = n - 1;
    while (l < r) {
        int total = arr[l] + arr[r];
        if (total == target) {
            cout << l << " " << r << endl;
            break;
        } else if (total < target) {
            // 证明左边的太小了
            l++;
        } else {
            // 证明右边的太大了
            r--;
        }
    }
    cout << "" << endl;
}

5.2.3 反转字符串 (洛谷 P5705【深基 2.例 7】数字反转)

题目：编写一个函数，将输入的字符串反转过来。

#include <iostream>
using namespace std;

int main(void) {
    string a; cin >> a;
    int i = 0, j = a.size() - 1;
    while (i < j) {
        char t = a[i]; a[i] = a[j]; a[j] = t;
        i++; j--;
    }
    cout << a << endl;
    return 0;
}

六、二分法

6.1 二分查找

• while(l < r)

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main(void) {
    int n, x;
    cin >> n >> x;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (arr[mid] > x) {
            r = mid - 1;
        } else if (arr[mid] < x) {
            l = mid + 1;
        } else {
            cout << mid << endl;
            return 0;
        }
    }
    if (arr[l] == x) cout << l << endl;
    else cout << -1 << endl;
    return 0;
}

• while(l <= r)

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main(void) {
    int n, x; cin >> n >> x;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] > x) {
            r = mid - 1;
        } else if (arr[mid] < x) {
            l = mid + 1;
        } else {
            cout << mid << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

6.2 左右边界

• while(l < r)

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main(void) {
    int n, x; cin >> n >> x;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int l = 0, r = n - 1; // 1 2 2 2 3
    while (l < r) {
        int mid = (l + r) / 2;
        if (arr[mid] >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (arr[l] == x) cout << l << endl;
    else cout << -1 << endl;
    l = 0, r = n - 1; // 1 2 2 2 3
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (arr[mid] <= x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (arr[r] == x) cout << r << endl;
    else cout << -1 << endl;
    return 0;
}

• while(l <= r)

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main(void) {
    int n, x; cin >> n >> x;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int l = 0, r = n - 1; // 1 2 2 2 3
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    if (arr[l] == x) cout << l << endl;
    else cout << -1 << endl;
    l = 0, r = n - 1; // 1 2 2 2 3
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] > x) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (arr[r] == x) cout << r << endl;
    else cout << -1 << endl;
    return 0;
}

七、筛质数

质数：只能被 1 与自身整除的数。

7.1 朴素法 O(nlogn)

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

bool isPrime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i < x; ++i) {
        if (x % i == 0 && x != 2) {
            return false;
        }
    }
    return true;
}

int main(void) {
    int n; cin >> n;
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) {
            cout << i << endl;
        }
    }
    return 0;
}

这里还会有个数学证明，优化了遍历条件。提高了效率，使其 i < x 化为 i * i <= x。

• 首先我们要知道，x = a * b，x / a = b。那么此时比如 i = a，则 x / i = b，也就是说如果一旦它有个因子是 a，肯定会有个 b 的，我们的 i 就是帮他试试有没有这样的因子 a。这个是前提！那么问题了，如果 x 可以被平方根，是不是就直接能确定因子 sqrt(x)，那么就不难发现，其它因子无非就是比 sqrt(x) 大或者小，如果 a 是比 sqrt(x) 大，那么 b 就比 sqrt(x) 小，这是肯定的。此时我们其实就可以给 i 规定最大范围，即 i <= sqrt(x) 这是没毛病的，因为只要我在 小于等于 sqrt(x) 范围内尝试是否有一个因子，那么另外一个因子也就被确定了。合乎数学逻辑。

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

bool isPrime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0 && x != 2) {
            return false;
        }
    }
    return true;
}

int main(void) {
    int n; cin >> n;
    for (int i = 2; i <= n; ++i) {
        if (isPrime(i)) {
            cout << i << endl;
        }
    }
    return 0;
}

7.2 埃氏筛 O(nloglogn)

朴素筛的时候，我们就知道用数学所谓的 平方根，因子相关知识进行优化。那么也不难想到，任何数的倍数其实都不可能是质数的！所以我们只需要筛出不是质数的，剩下的就是质数喽。

#include <iostream>
#include <string.h>
using namespace std;
const int maxN = 1e5 + 10;
bool primeArr[maxN];

int main(void) {
    int n; cin >> n;
    memset(primeArr, true, sizeof(bool) * maxN);
    primeArr[0] = false;
    primeArr[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        for (int j = 2 * i; j < n; j += i) {
            primeArr[j] = false;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (primeArr[i]) {
            cout << i << endl;
        }
    }
    return 0;
}

7.3 欧拉筛 O(n)

其实朴素筛、埃氏筛 速度已经不错了，但有些时候可能需要最好的性能。此时就需要 使用 欧拉筛，它主要是优化了埃氏筛的缺点。

埃氏筛中，有这样一种情况，会导致多筛！比如 6 = 2 * 3，那么 对于 2 来说会有 * 3 的时候，而对于 3 来说又会有*2 的时候，但其实只需要筛一次就够，如果能保证筛一次的话，时间复杂度就可以 O(n)。

• 基本观察：每个非质数（合数）都会有唯一的 最小质因子。
• 关键机制：如果我们可以确保每个合数只在它 最小质因子与对应因数相乘时才被标记为 合数，那么就只筛了一次，不会多筛。就比如说 6 只在 最小质因子 2 乘以 3 的时候，才会被标记，其余情况不会被标记。

#include <iostream>
#include <string.h>
using namespace std;
const int maxN = 1e5 + 10;
int primes[maxN]; // 升序
bool vis[maxN];

int main(void) {
    int n; cin >> n;
    memset(vis, false, sizeof(bool) * maxN); // 假设都没被标记为合数
    int pos = 0;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) // 先判断是不是合数
        {
            primes[pos++] = i; // i 是质数
            // 当前这个质数 * 其它已经确认的质数 = 合数
            for (int j = 0; j < pos && i * primes[j] <= n; ++j) {
                vis[i * primes[j]] = true; // 这个是合数
            }
        } else {
            // 当前这个合数 * 已经确认的质数（从最小的开始） = 合数
            // 但当前这个合数很可能是 某个最小质数的倍数，所以如果用它继续筛就筛多了
            // 必须判断出它是哪个最小质数的倍数
            for (int j = 0; j < pos && i * primes[j] <= n; ++j) {
                vis[i * primes[j]] = true; // 这个是合数
                if (i % primes[j] == 0) {
                    // 看下当前这个 i 是不是最小质数
                    break; // 证明不是最小质数了，可以是 primes[j] 的倍数，那么这个 primes[j] 在后续就可以帮他继续筛完
                    // 即 当前的 i 就不用去做没意义的筛了。
                }
            }
        }
    }
    for (int i = 0; i < pos; ++i) {
        cout << primes[i] << endl;
    }
    return 0;
}

八、前缀和与差分

• 前缀和：快速求某个区间中所有元素的累加和。（所以这些数肯定是要 反复使用进行累加的）。
• 差分：对多个区间进行加数，快速得到操作后的数组集合（需要学习前缀和）。

8.1 一维前缀和

• 朴素写法

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int p, q; cin >> p >> q;
    int sum = 0;
    for (int i = p; i <= q; ++i) {
        sum += arr[i];
    }
    cout << sum << endl;
    return 0;
}

• 前缀和写法

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int sum[maxN] = {0};

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    sum[1] = arr[0];
    for (int i = 2; i <= n; ++i) {
        sum[i] = sum[i - 1] + arr[i - 1];
    }
    // 1 2 3 4 5
    // 1 3 6 10 15
    for (int i = 0; i < n + 1; ++i) {
        cout << sum[i] << " ";
    }
    int p, q; cin >> p >> q;
    cout << endl;
    cout << sum[q + 1] - sum[p - 1] << endl;
    return 0;
}

8.2 二维前缀和

核心思想还是 前缀和，只不过是从 一维数组拓展到了二维矩阵。所以我们要探索有哪些变化，总结出通式，解决二维前缀和问题。

#include <iostream>
using namespace std;
const int maxN = 1005;
int arr[maxN][maxN] = {0};
int sum[maxN][maxN] = {0};

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
            cout << sum[i][j] << " ";
        }
        cout << endl;
    }
    int q; cin >> q;
    while (q--) {
        int x1, y1, x2, y2; cin >> x1 >> y1; cin >> x2 >> y2;
        cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

8.3 一维差分

原理：构建差分数组，将其当作新的原数组。然后进行前缀和操作，意外发现由差分数组还原成了真正的原数组。所以，只要我们在差分数组里进行区域内的加数操作，得到普遍规律可循，最后进行前缀和就可以得到我们的目标数组。

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN] = {0};
int d[maxN] = {0};

int main() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        d[i] = arr[i] - arr[i - 1];
    }
    while (q--) {
        int l, r, c; cin >> l >> r >> c;
        d[l] += c;
        if (r + 1 < n) {
            d[r + 1] -= c;
        }
    }
    for (int i = 1; i <= n; i++) {
        arr[i] = d[i] + arr[i - 1];
        cout << arr[i] << " ";
    }
    return 0;
}

8.4 二维差分

#include <iostream>
using namespace std;
const int maxN = 1005;
int arr[maxN][maxN] = {0};
int d[maxN][maxN] = {0}; // 差分数组
int sum[maxN][maxN] = {0}; // 前缀和数组

int main() {
    int n, m, q; cin >> n >> m >> q;
    // 输入原始数组并初始化差分数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
            // 计算差分数组
            d[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];
        }
    }
    // 处理查询
    while (q--) {
        int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
        // 更新差分数组
        d[x1][y1] += c;
        if (y2 + 1 <= m) d[x1][y2 + 1] -= c;
        if (x2 + 1 <= n) d[x2 + 1][y1] -= c;
        if (x2 + 1 <= n && y2 + 1 <= m) d[x2 + 1][y2 + 1] += c;
    }
    // 通过差分数组计算前缀和数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i][j] = d[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            cout << sum[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

九、链表、队列、栈

9.1 单链表

#include <iostream>
using namespace std;

struct Node {
    Node* next;
    int data;
};

int main() {
    Node* A = new Node();
    Node* B = new Node();
    A->data = 1;
    B->data = 2;
    A->next = B;
    B->next = NULL;
    Node* currentNode = A;
    // 1. 遍历
    // Node* currentNode = A;
    // while (currentNode != NULL) {
    //     cout << currentNode->data << endl;
    //     currentNode = currentNode->next;
    // }
    // 2. 通关下标找到目标节点
    // int pos;
    // cin >> pos;
    // for (int i = 0; i < pos; i++) {
    //     if (i == 0) {
    //         currentNode = A;
    //     } else {
    //         currentNode = currentNode->next;
    //     }
    //     if (currentNode == NULL) {
    //         break;
    //     }
    // }
    // if (currentNode == NULL) cout << A->data << endl;
    // else cout << currentNode->data << endl;
    // 3. 通过下标删除目标节点
    // int pos;
    // cin >> pos;
    // Node* preNode = A;
    // currentNode = preNode->next;
    // if (pos == 0) {
    //     A = currentNode;
    //     delete preNode;
    // } else if (pos > 0) {
    //     for (int i = 2; i <= pos; i++) {
    //         preNode = currentNode;
    //         currentNode = preNode->next;
    //         if (currentNode == NULL) {
    //             break;
    //         }
    //     }
    //     if (currentNode == NULL) {cout << "删除失败" << endl;}
    //     else {
    //         preNode->next = currentNode->next;
    //         delete currentNode;
    //     }
    // }
    // currentNode = A;
    // while (currentNode != NULL) {
    //     cout << currentNode->data << endl;
    //     currentNode = currentNode->next;
    // }
    // 4. 在下标后面插入一个节点
    int pos; cin >> pos;
    int data; cin >> data;
    for (int i = 0; i <= pos; i++) {
        if (i == 0) {
            currentNode = A;
        } else {
            currentNode = currentNode->next;
        }
        if (currentNode == NULL) {
            break;
        }
    }
    if (currentNode == NULL) cout << -1 << endl;
    else {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
    currentNode = A;
    while (currentNode != NULL) {
        cout << currentNode->data << endl;
        currentNode = currentNode->next;
    }
    return 0;
}

9.2 双链表

#include <iostream>
using namespace std;

struct Node {
    Node* pre;
    Node* next;
    int data;
};

int main() {
    Node* head = new Node();
    Node* A = new Node();
    Node* B = new Node();
    head->next = A;
    A->data = 1;
    B->data = 2;
    A->pre = head;
    A->next = B;
    B->pre = A;
    B->next = NULL;
    Node* cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    // 删除
    int pos; cin >> pos;
    int t = pos + 1; // 第 pos + 1 个
    cNode = head;
    for (int i = 1; i <= t; i++) {
        cNode = cNode->next;
        if (cNode == NULL) {
            cout << "删除失败" << endl;
            return 0;
        }
    }
    Node* preNode = cNode->pre;
    preNode->next = cNode->next;
    delete cNode;
    cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    return 0;
}

9.3 栈

#include <iostream>
using namespace std;

struct Node {
    Node* pre;
    Node* next;
    int data;
};

Node* tail = NULL;

void push(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    newNode->pre = tail;
    tail->next = newNode;
    tail = newNode;
}

int pop() {
    Node* preNode = tail->pre;
    preNode->next = NULL;
    int ret = tail->data;
    delete tail;
    tail = preNode;
    return ret;
}

int main() {
    Node* head = new Node();
    Node* A = new Node();
    Node* B = new Node();
    head->next = A;
    A->data = 1;
    B->data = 2;
    A->pre = head;
    A->next = B;
    B->pre = A;
    B->next = NULL;
    tail = B;
    Node* cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    push(3);
    push(4);
    cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    pop();
    cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    return 0;
}

9.4 队列

#include <iostream>
using namespace std;

struct Node {
    Node* pre;
    Node* next;
    int data;
};

Node* tail = NULL;

void push(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    newNode->pre = tail;
    tail->next = newNode;
    tail = newNode;
}

int pop() {
    Node* preNode = tail->pre;
    preNode->next = NULL;
    int ret = tail->data;
    delete tail;
    tail = preNode;
    return ret;
}

Node* head = new Node();

int outQue() {
    Node* firstNode = head->next;
    if (firstNode == NULL) return -1;
    head->next = firstNode->next;
    int ret = firstNode->data;
    delete firstNode;
    return ret;
}

int main() {
    Node* A = new Node();
    Node* B = new Node();
    head->next = A;
    A->data = 1;
    B->data = 2;
    A->pre = head;
    A->next = B;
    B->pre = A;
    B->next = NULL;
    tail = B;
    Node* cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    push(3);
    push(4);
    cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    outQue();
    cNode = head->next;
    while (cNode != NULL) {
        cout << cNode->data << endl;
        cNode = cNode->next;
    }
    return 0;
}

9.5 数组模拟链表、栈、队列

链表既然能够实现栈和队列，那么自然 数组就也可以实现 栈和队列，甚至可以 模拟链表的逻辑。我们来看下。

• 模拟链表 链表结构的核心就在于'链'，它可以直接找到对应的节点。那么我们可以通过 数组构建一个映射表，该数组的下标就相当于某个节点，然后存储的数据就是 链接的节点下标。这样我们就构建出了单链表的逻辑结构。

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int nodeArr[maxN];
int linkArr[maxN];

int main() {
    linkArr[0] = 1; // 0 号 指向 1 号节点
    nodeArr[1] = 1; // 1 号 节点
    nodeArr[2] = 2; // 2 号 节点
    linkArr[1] = 2; // 1 号 指向 2 号节点
    linkArr[2] = -1; // 定义 -1 是下个节点无 NULL
    int nextPos = linkArr[0];
    int cNode = nodeArr[nextPos];
    while (nextPos != -1) {
        cout << cNode << endl;
        nextPos = linkArr[cNode];
        cNode = nodeArr[nextPos];
    }
    return 0;
}

• 模拟栈

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int stack[maxN];
int tail = 0; // 当前要入栈位置

void push(int data) {
    if (tail >= maxN) {
        cout << "满了" << endl;
        return;
    }
    stack[tail++] = data;
}

int pop() {
    if (tail == 0) return -1;
    return stack[--tail];
}

int main() {
    push(1);
    push(2);
    for (int i = 0; i < tail; ++i) {
        cout << stack[i] << endl;
    }
    pop();
    for (int i = 0; i < tail; ++i) {
        cout << stack[i] << endl;
    }
    return 0;
}

• 模拟队列

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int q[maxN];
int top = 0;
int tail = -1;

void push(int x) {
    q[++tail] = x;
}

int pop() {
    return q[top++];
}

int main() {
    push(2);
    if (tail < top) {
        cout << "空的" << endl;
    }
    cout << "数量" << tail + 1 - top << endl;
    cout << pop() << endl;
    return 0;
}

• 模拟循环队列

#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int q[maxN];
int top = 0; // 头元素下标
int tail = 0; // 待插入节点的下标（即队尾的下一个下标）

bool isFull() {
    return (tail + 1) % maxN == top;
}

void push(int data) {
    if (isFull()) {
        cout << "队列满了" << endl;
        return;
    }
    q[tail] = data;
    tail = (tail + 1) % maxN;
}

int outQ() {
    if (top == tail) {
        cout << "队列空的" << endl;
        return -1;
    }
    int ret = q[top];
    top = (top + 1) % maxN;
    return ret;
}

int main() {
    push(1);
    push(2);
    cout << outQ() << endl;
    return 0;
}

十、DFS、BFS

讲 DFS 与 BFS 这就不得不说一个典故（迷宫）。

想象一下，你进入了一个巨大的迷宫，你的目标是从起点 S 找到终点 T。 迷宫的结构如下，其中 # 代表墙，不能走；. 代表路，可以走。

S . . # . . . . # . . . # . . # . . . . . . . # # . . . # . # T . . . 

现在有两个问题被提出：

• 走到终点的方案有多少种，分别都打印出来（DFS）。
• 走到终点最近的方案是什么路径，打印出来（BFS）。

10.1 DFS

DFS：深度优先搜索，被戏称为一路走到黑。随便选一条路，死磕到底，碰壁后再倒回来换条路去走。

• 你的行动方式：
  • 从起点 S 开始，开始，你标记'我已经来过这里了'。
  • 你面前有多个岔路口，你随机选一个（比如总是先向右），然后一直走下去。
  • 每到一个新地方，你都继续沿用这个规则（比如先向右），完全不管其他还没走的岔路。
  • 如果有一天你发现前面是墙或者已经走过的地方（死胡同），你就原路返回，回到上一个有未探索岔路口的地方，换另一条路继续深入。
  • 直到你在某条路的尽头发现了终点 T。
• 辅助容器：栈
  • 为了管理这种'一路到底，然后回溯'的过程，你需要另一个工具——栈。
  • 把起点 S 压入栈。
  • 只要栈不为空，就取出栈顶的那个位置（比如 B）。注意，拿的是最新的那个！
  • 检查 B 是不是终点？如果是，胜利！
  • 如果不是，就把 B 周围所有能走且没走过的邻居，按顺序压入栈。
  • 重复步骤 2。（这样，下一次就会先探索刚压进去的其中一个邻居，从而不断深入）
• 非递归版本

#include <iostream>
using namespace std;

// 我们是 节点，二维数组，所以最好是 建立 x,y
// 题目要求我们 用 x,y 下标 去确定一个节点的话，那么我们就要定义 这样的结构
typedef struct {
    int x, y;
} Node;

typedef struct {
    Node point;
    int dir; // 下次探索的方向 0 1 2 3
} SNode;

const int maxN = 105;
Node d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool vis[maxN][maxN]; // 为走过的节点打标记
Node path[maxN * maxN];
int pathLen = 0;
char arr[maxN][maxN];
SNode s[maxN * maxN];
int top = -1;

int main(void) {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
            vis[i][j] = false;
            if (arr[i][j] == 'S') {
                s[++top] = {i, j, 0};
                vis[i][j] = true;
                pathLen = 1;
                path[0] = {i, j};
            }
        }
    }
    while (top >= 0) {
        // 只有栈为空的时候，才不去探索
        SNode* cNode = &s[top];
        if (cNode->dir > 3) {
            vis[cNode->point.x][cNode->point.y] = false;
            pathLen--;
            top--;
            continue;
        }
        int nx = cNode->point.x + d[cNode->dir].x;
        int ny = cNode->point.y + d[cNode->dir].y;
        cNode->dir++;
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && arr[nx][ny] != '#') {
            vis[nx][ny] = true;
            path[pathLen++] = {nx, ny};
            if (arr[nx][ny] == 'T') {
                for (int i = 0; i < pathLen; ++i) {
                    cout << path[i].x << "," << path[i].y << " ";
                }
                cout << endl;
                vis[nx][ny] = false;
                pathLen--;
            } else {
                s[++top] = {nx, ny, 0};
            }
        }
    }
    return 0;
}

• 递归版本

#include <iostream>
using namespace std;
const int maxN = 1005;

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point p;
    int nextDir; // 下一步尝试的方向 (0~3)
} StackNode;

// 方向：上下左右
Point d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool vis[maxN][maxN]; // 是否走过了
Point path[maxN];
int pathLen = 0;
int totalPaths = 0; // 记录多少种路径方案
char arr[maxN][maxN];
int n, m;
// 5,7

void dfs(int x, int y) {
    vis[x][y] = true;
    path[pathLen++] = {x, y};
    if (arr[x][y] == 'T') {
        printf("Path %d:\n", ++totalPaths);
        for (int i = 0; i < pathLen; i++) {
            printf("(%d,%d) ", path[i].x, path[i].y);
        }
        printf("\n\n");
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + d[i].x;
        int ny = y + d[i].y;
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && arr[nx][ny] != '#') {
            // 没有访问过
            dfs(nx, ny);
            vis[nx][ny] = false;
            pathLen--;
        }
    }
}

int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }
    int startX = -1, startY = -1; // 从 -1 开始
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 'S') {
                startX = i;
                startY = j;
                break;
            }
        }
        if (startX != -1) break;
    }
    if (startX == -1) {
        printf("没有起始点\n");
        return 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            vis[i][j] = false;
    dfs(startX, startY);
    if (totalPaths == 0) {
        printf("No path found!\n");
    } else {
        printf("Total paths: %d\n", totalPaths);
    }
    return 0;
}

10.2 BFS

BFS：广度优先搜索，又称为地毯式搜索。先探索所有最近的地方（层次感），再探索更远的地方。

• 你的行动方式：
  • 从起点 S 开始，你标记'我已经来过这里了'。
  • 你站在 S，向四周（上、下、左、右）可通行的方向看，把所有能直接到达的点都记录下来。这些是你的'第一层'邻居。
  • 然后，你不再自己往前走，而是召唤出几个分身。每个分身去一个'第一层'邻居点。
  • 所有这些分身在各自的位置上，再次重复你的动作：记录他们周围还未被探索的、'第二层'的邻居点。
  • 这个过程一层一层地展开，就像，就像在水里扔下一块石头，涟漪一圈一圈地扩散出去，直到某个分身找到了终点 T。
• 辅助容器：队列
  • 为了管理这个'分层探索'的过程，你需要一个强大的工具——队列。
  • 队列的特点：先进先出 (FIFO)，就像现实生活中的排队。先进去的人先出来。
  • 如何使用：
    • 把起点 S 放进队列。
    • 只要队列不为空，就拿出队首的那个位置（比如 A）。
    • 检查 A 是不是终点？如果是，胜利！
    • 如果不是，就把 A 周围所有能走且没走过的邻居，按顺序（比如上、下、左、右）依次放入队列的末尾。
    • 重复步骤 2。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int maxN = 1005;
struct Point {
    int x;
    int y;
};

Point q[maxN];
int top = 0;
int tail = 0;

bool ifFull() {
    return (tail + 1) % maxN == top;
}

void push(Point data) {
    if (ifFull()) {
        return;
    }
    q[tail] = data;
    tail = (tail + 1) % maxN;
}

Point outQ() {
    if (top == tail) {
        cout << "队列空的" << endl;
        return {-1, -1};
    }
    Point ret = q[top];
    top = (top + 1) % maxN;
    return ret;
}

Point d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char arr[maxN][maxN];
bool vis[maxN][maxN];
Point pre[maxN][maxN]; // 记录当前节点的上一个节点

int main() {
    int n, m;
    int startX, startY;
    int endX, endY;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            vis[i][j] = false;
            if (arr[i][j] == 'S') {
                startX = i;
                startY = j;
            }
            if (arr[i][j] == 'T') {
                endX = i;
                endY = j;
            }
        }
    }
    push({startX, startY});
    vis[startX][startY] = true;
    pre[startX][startY] = {-1, -1};
    bool flag = false; // 默认没找到 T
    while (top != tail) {
        Point cNode = outQ();
        if (cNode.x == endX && cNode.y == endY) {
            flag = true;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = cNode.x + d[i].x;
            int ny = cNode.y + d[i].y;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
            vis[nx][ny] = true;
            pre[nx][ny] = cNode;
            push({nx, ny});
        }
    }
    if (!flag) {
        cout << "根本没终点" << endl;
    } else {
        vector<Point> path;
        int x = endX, y = endY;
        while (x != -1 || y != -1) {
            path.push_back({x, y});
            Point p = pre[x][y];
            x = p.x;
            y = p.y;
        }
        reverse(path.begin(), path.end());
        cout << endl;
        for (int i = 0; i < path.size(); i++) {
            cout << path[i].x << " " << path[i].y;
            if (i != path.size() - 1) cout << " -> ";
        }
    }
    return 0;
}

十一、贪心思想

贪心思想的核心是：每一步都做出当前看起来'最好'的选择，希望通过局部最优解最终达到全局最优解。

注意：贪心算法并不总能得到全局最优解，但在某些特定问题上，它是有效的，并且效率很高！

• 贪心选择性质：每一步都做当前看起来最好的选择，不考虑未来。
• 最优子结构：问题的最优解包含其子问题的最优解。
• 无后效性：一旦做出选择，就不会再改变，也不会影响之前的选择。

11.1 找零钱问题

问题：假设你有面值为 1 元、5 元、10 元 的硬币，要找给顾客 36 元，要求用最少数量的硬币。

贪心：每次都尽可能用最大面值的硬币就行了。

#include <stdio.h>

int main() {
    // 定义硬币面值（按从大到小排序）
    int coins[] = {10, 5, 1};
    int numCoins = 3; // sizeof(coins) / sizeof(coins[0]); 这个写法是计算数组元素个数的技巧写法
    int amount;
    printf("请输入要找零的金额（元）: ");
    scanf("%d", &amount);
    if (amount < 0) {
        printf("金额不能为负数！\n");
        return 1;
    }
    int totalCoins = 0;
    printf("找零方案：\n");
    for (int i = 0; i < numCoins; i++) {
        int count = amount / coins[i]; // 当前面值能用多少个
        if (count > 0) {
            printf("%d元硬币：%d枚\n", coins[i], count);
            totalCoins += count;
            amount -= coins[i] * count;
        }
    }
    printf("总共需要硬币：%d枚\n", totalCoins);
    return 0;
}

11.2 活动选择问题（区间调度）

问题：有 n 个活动，每个活动有开始时间和结束时间。你一次只能参加一个活动，如何选择最多的活动？

• 贪心：优先选择结束时间最早的活动。因为结束得早，留给后面的时间就多，能安排更多活动。

#include <stdio.h>
#include <stdlib.h>

// 定义活动结构体
typedef struct {
    int start;
    int finish;
    int id; // 活动编号（可选，用于输出原始顺序）
} Activity;

// 比较函数：用于 qsort，按结束时间升序排序
int compare(const void* a, const void* b) {
    Activity* actA = (Activity*)a;
    Activity* actB = (Activity*)b;
    return actA->finish - actB->finish;
}

int main() {
    int n;
    printf("请输入活动数量：");
    scanf("%d", &n);
    if (n <= 0) {
        printf("活动数量必须大于 0。\n");
        return 1;
    }
    Activity activities[n];
    printf("请输入每个活动的开始时间和结束时间（格式：start finish）:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &activities[i].start, &activities[i].finish);
        activities[i].id = i + 1; // 编号从 1 开始
        // 简单校验
        if (activities[i].start >= activities[i].finish) {
            printf("警告：活动%d的开始时间应小于结束时间！\n", i + 1);
        }
    }
    // 按结束时间升序排序
    qsort(activities, n, sizeof(Activity), compare);
    // 贪心选择
    printf("\n最多可参加的活动如下（按结束时间排序）:\n");
    int count = 1;
    int lastFinish = activities[0].finish;
    printf("活动%d: [%d, %d]\n", activities[0].id, activities[0].start, activities[0].finish);
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastFinish) {
            printf("活动%d: [%d, %d]\n", activities[i].id, activities[i].start, activities[i].finish);
            count++;
            lastFinish = activities[i].finish;
        }
    }
    printf("\n最多可参加 %d 个活动。\n", count);
    return 0;
}