跳转至

3、基础算法简介

一、模拟法

概念：

​ 模拟法是一种编程方法，主要是对题目描述的过程进行模拟，直接用程序去模拟题目所描述的过程。模拟法通常用于解决一些涉及到复杂流程，而又无法使用数学方法直接求解的问题。

相关算法：排序、查找、数学运算等

​ 模拟法不依赖于特定的算法，它主要是对题目描述的过程进行模拟，所以可能会涉及到各种不同的算法，如排序、查找、数学运算等。

相关示例：约瑟夫环

​ 约瑟夫环问题就是一个典型的模拟法例子，题目描述了一个过程，我们可以直接用程序去模拟这个过程，得到问题的解。

具体代码：

​ 下面是使用C++实现的约瑟夫环问题的模拟法解法：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <vector>
using namespace std;

int josephus(int n, int m) {
    vector<int> circle(n);
    for (int i = 0; i < n; ++i) {
        circle[i] = i;
    }
    int curr = 0;
    while (circle.size() > 1) {
        curr = (curr + m - 1) % circle.size();
        circle.erase(circle.begin() + curr);
    }
    return circle[0];
}

​ 在这个代码中，我们首先创建了一个表示环的数组，然后我们开始循环，每次都将第m个元素移除，直到只剩下一个元素，这个元素就是问题的解。

二、枚举法

概念：

​ 枚举法是一种解决问题的基本方法，它将问题的所有可能的解都一一列举出来，然后选择出满足条件的解。这种方法简单易用，但是在问题规模较大时，可能会因为解的数量过多而不可行。

相关算法：全排列、组合、子集

​ 全排列、组合和子集问题都可以使用枚举法来解决，我们可以枚举出所有的排列、组合或子集，然后选择出满足条件的解。

相关示例：全排列问题

​ 例如，在全排列问题中，我们希望找出一个集合的所有排列。这个问题就可以使用枚举法解决，我们可以枚举出所有的排列，然后选择出满足条件的解。

具体代码：

​ 下面是使用C++实现的全排列的枚举法代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

void printPermutations(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    do {
        for (int num : nums) {
            cout << num << ' ';
        }
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end()));
}

​ 在这个代码中，我们首先将集合中的元素排序，然后使用STL中的next_permutation函数来枚举所有的排列。我们每次都打印出当前的排列，直到所有的排列都被枚举完。

三、尺取法

概念：

​ 尺取法是一种解决连续子序列问题的有效方法。尺取法可以在线性时间复杂度内解决一类特定的连续子序列问题，这类问题通常可以被描述为"寻找一个连续子序列，使得子序列满足特定的条件"。

相关算法：尺取法的步骤

​ 尺取法的基本步骤是使用两个指针，一个指针用于指示子序列的开始，另一个指针用于指示子序列的结束。首先，将结束指针向右移动，直到子序列满足条件，然后，将开始指针向右移动，缩小子序列的范围，直到子序列不再满足条件。通过这种方式，我们可以在线性时间复杂度内找到所有满足条件的子序列。

相关示例：寻找和大于等于S的最小子序列

​ 例如，给定一个正整数数组[2, 3, 1, 2, 4, 3]和一个正整数S=7，满足和大于等于S的最小子序列是[4,3]。

具体代码：

​ 下面是使用C++实现的尺取法的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <climits>
using namespace std;

int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }
    int ans = INT_MAX;
    int start = 0;
    int end = 0;
    int sum = 0;
    while (end < n) {
        sum += nums[end];
        while (sum >= s) {
            ans = min(ans, end - start + 1);
            sum -= nums[start];
            start++;
        }
        end++;
    }
    return (ans != INT_MAX) ? ans : 0;
}

​ 在这个代码中，我们首先初始化两个指针start和end，以及一个用于记录子序列和的变量sum。然后，我们在while循环中，首先将end指向的元素加到sum中，然后，如果sum大于等于s，我们就将start指向的元素从sum中减去，并将start向右移动。最后，我们返回最小的满足条件的子序列的长度。

四、二分法

概念：

​ 二分法（Binary Search）是一种在有序数组中查找特定元素的搜索算法。二分查找的思想是在有序数组中，取中间元素进行比较，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果查找的元素不在数组中，则结束查找。

相关算法：二分搜索

​ 二分搜索的核心思想是分治，每次都能将问题的规模减半。这种思想也适用于其他一些可以通过分治策略来解决的问题，例如在计算机科学中的很多问题，如搜索算法、数学问题等。

相关示例：在有序数组中查找特定元素

​ 例如，给定一个有序数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，我们要查找的元素是7。

具体代码：

​ 下面是使用C++实现的二分查找的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // 如果找不到目标元素，返回-1
}

​ 在这个代码中，我们首先定义两个指针，分别指向数组的开始和结束。然后，我们在while循环中，计算中间元素的索引，然后比较中间元素和目标元素。如果中间元素等于目标元素，我们返回中间元素的索引。如果中间元素小于目标元素，我们更新左指针。如果中间元素大于目标元素，我们更新右指针。最后，如果在数组中找不到目标元素，我们返回-1。

五、三分法

概念：

​ 三分法是一种用于求解单峰（在某个区间内单调增加后单调减少，或者单调减少后单调增加）函数极值问题的方法。三分法的主要思想是在待求解的区间选取两个内部点，通过比较这两个内部点的函数值来缩小求解的区间。

相关算法：求解单峰函数的极值

​ 首先，找到问题的单峰性质，然后选择区间内的两个点，通过比较这两个点的函数值，去掉不可能包含极值的那一部分区间，然后在剩下的区间中继续这个操作，直到区间的长度小于预设的精度，此时，区间中的任何一个点都可以作为极值点。

相关示例：求解单峰函数的极值

​ 例如，寻找函数f(x) = -(x-2)^2 在区间[1, 3]中的最大值。

具体代码：

​ 下面是使用C++实现的三分法的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cmath>
using namespace std;

double func(double x) {
    return -(x - 2) * (x - 2);  // 目标函数
}

double ternarySearch(double l, double r) {
    double eps = 1e-10;  // 设置精度
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = func(m1);   // 计算第一个点的函数值
        double f2 = func(m2);   // 计算第二个点的函数值
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return func(l);  // 返回极值点的函数值
}

​ 在这个代码中，我们首先定义了一个表示目标函数的函数func。然后我们在ternarySearch函数中，通过不断缩小搜索的区间，最终找到极值点的函数值。注意这里的eps是预设的精度，表示我们可以接受的最大误差。

六、倍增法

概念：

​ 倍增法是一种常用的求解离散对数问题或者求解某种具有递推性质问题的算法，这种方法的核心思想是“折半”。倍增法是通过不断地将问题规模对半分割，从而将复杂度由O(n)优化至O(log n)，进而提高算法效率。

相关算法：求解离散对数问题、求解最近公共祖先(LCA)问题等

​ 在求解离散对数问题中，我们可以预处理出所有可能的答案，然后通过倍增的方式快速查找到答案。在求解最近公共祖先问题中，我们可以预处理出每个节点向上走2^k步所到达的节点，然后通过倍增的方式快速查找到公共祖先。

相关示例：求解最近公共祖先(LCA)问题

​ 例如，在一棵有根树中，节点u的父节点为p[u]，我们希望求出节点u向上走2^k步所到达的节点。

具体代码：

​ 下面是使用C++实现的倍增法的代码：

C++
 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
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 1e5+7; // 树的最大节点数
const int MAXLOG = 20; // 对于节点数1e5级别的树，高度不超过20
vector<int> parent(MAXN); // parent[i]表示节点i的父节点
vector<vector<int>> anc(MAXN, vector<int>(MAXLOG, 0)); // anc[i][j]表示节点i向上走2^j步所到达的节点

void preprocessing(int n) {
    for (int i = 1; i <= n; ++i) {
        anc[i][0] = parent[i];
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int query(int u, int k) {
    for (int i = 0; i < MAXLOG; ++i) {
        if ((k >> i) & 1) {
            u = anc[u][i];
        }
    }
    return u;
}

​ 在这个代码中，我们首先预处理出anc数组，然后在query函数中，我们通过观察k的二进制表示，快速找出u向上走k步所到达的节点。

七、ST算法

概念：

​ ST算法（Sparse Table算法），也称稀疏表算法，是一种用于处理区间查询问题的算法。ST算法主要用于处理一类特殊的问题，即查询区间内的最值问题，对于这类问题，ST算法具有线性的预处理时间复杂度和常数的查询时间复杂度。

相关算法：求解区间最值问题

​ 在ST算法中，我们首先进行预处理，计算出所有可能的区间的最值，然后在查询时，我们可以直接返回预处理中得到的结果。预处理的过程中使用了动态规划的思想。

相关示例：查询区间最大值

​ 例如，给定一个数组[1, 4, 6, 2, 7, 3, 5]，我们希望能够快速查询任意区间的最大值。

具体代码：

​ 下面是使用C++实现的ST算法的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 1e5+7; // 数组的最大长度
const int MAXLOG = 20; // 对于长度为1e5的数组，log不超过20
vector<vector<int>> st(MAXN, vector<int>(MAXLOG, 0)); // st[i][j]表示从i开始长度为2^j的区间的最大值

void preprocessing(const vector<int>& nums, int n) {
    for (int i = 0; i < n; ++i) {
        st[i][0] = nums[i];
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 0; i + (1 << j) - 1 < n; ++i) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

​ 在这个代码中，我们首先预处理出st数组，然后在query函数中，我们通过查找两个可能覆盖查询区间的区间，然后返回两个区间的最大值。

八、前缀和与差分

概念：

​ 前缀和是一种常用的预处理方法，可以高效地处理区间求和问题。在前缀和数组中，每个位置的元素都是原始数组在该位置及其之前所有元素的和。具有前缀和数组后，原数组中任意区间的和就可以通过两次操作即可得到。

​ 差分则是与前缀和相反的操作，可以用来处理对原数组区间的修改问题。差分的核心思想是记录每个元素和它前一个元素的差值，通过这个差值的数组，可以快速地进行区间的增加操作。

相关算法：处理区间求和问题、处理区间修改问题

​ 前缀和算法可以用来处理区间求和问题，差分算法可以用来处理区间修改问题。

相关示例：求区间和、对区间内所有元素增加一个常数

​ 例如，我们有一个数组[1, 2, 3, 4, 5]，我们希望快速求出区间[2, 4]的和，或者将区间[2, 4]内的所有元素增加2。

具体代码：

​ 下面是使用C++实现的前缀和与差分的代码：

C++
 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
#include <vector>
using namespace std;

vector<int> prefixSum(vector<int>& nums) {
    vector<int> sum(nums.size() + 1, 0);
    for (int i = 1; i <= nums.size(); ++i) {
        sum[i] = sum[i - 1] + nums[i - 1];
    }
    return sum;
}

int rangeSum(vector<int>& sum, int i, int j) {
    return sum[j + 1] - sum[i];
}

vector<int> difference(vector<int>& nums) {
    vector<int> diff(nums.size(), 0);
    diff[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        diff[i] = nums[i] - nums[i - 1];
    }
    return diff;
}

void rangeAdd(vector<int>& diff, int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.size()) {
        diff[j + 1] -= val;
    }
}

​ 在这个代码中，我们首先计算前缀和数组，然后提供了一个函数可以快速求出区间和。然后我们计算差分数组，并提供了一个函数可以快速对区间内的所有元素进行增加操作。

九、递推

概念：

​ 递推是一种基于前一项或前几项结果推导出后一项的思想。递推算法是一种简洁高效的算法，适合解决具有明显递推性质的问题。

相关算法：斐波那契数列、等差数列、等比数列

​ 这些都是递推的经典案例。例如，在斐波那契数列中，每一个数都是前两个数的和，这就构成了一个明显的递推关系；等差数列和等比数列也都具有明显的递推性质。

相关示例：斐波那契数列

​ 斐波那契数列是递推的一个典型例子。每个斐波那契数都是前两个斐波那契数的和，我们可以通过递推的方式来求解斐波那契数列。

具体代码：

​ 下面是使用C++实现的斐波那契数列的递推代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
using namespace std;

vector<int> fib(int n) {
    vector<int> f(n + 1, 0);
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f;
}

​ 在这个代码中，我们首先创建一个长度为n + 1的数组f，然后初始化f[0]和f[1]。然后，我们通过循环，每次都将f[i]设置为f[i - 1]和f[i - 2]的和，这样就实现了递推。最后，我们返回f数组，这个数组中的每一个元素都是对应的斐波那契数。

十、递归

概念：

​ 递归是一种解决问题的方法，它把一个问题分解为更小的子问题，直到这些子问题可以直接求解。然后通过子问题的解来构建原问题的解。递归方法特别适合处理数据的嵌套结构。

相关算法：深度优先搜索（DFS）、快速排序、归并排序

​ 深度优先搜索、快速排序和归并排序都是递归的典型应用，它们都是通过递归将问题分解为更小的子问题，然后通过子问题的解来解决原问题。

相关示例：斐波那契数列

​ 斐波那契数列就是一个典型的递归问题。每一个斐波那契数都是前两个斐波那契数的和，我们可以通过递归的方法来求解斐波那契数列。

具体代码：

​ 下面是使用C++实现的斐波那契数列的递归代码：

C++
1
2
3
4
5
6
int fib(int n) {
    if (n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

​ 在这个代码中，我们首先判断n的值。如果n小于等于1，那么斐波那契数就是n本身。否则，斐波那契数就是前两个斐波那契数的和，我们可以通过递归调用来求解。

十一、分治法

概念：

​ 分治法是一种解决问题的重要方法，其主要思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等。

相关算法：快速排序、归并排序、二分搜索、大整数乘法

​ 这些算法都采用了分治法的思想，将问题分解为相似的子问题，然后分别解决子问题，最后将子问题的解合并得到原问题的解。

相关示例：归并排序

​ 例如，在归并排序中，我们首先将待排序的数组分成两部分，然后对这两部分分别进行归并排序，最后将排序好的两部分进行合并。

具体代码：

​ 下面是使用C++实现的归并排序的代码：

C++
 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
#include <vector>
#include <algorithm>
using namespace std;

void merge(vector<int>& nums, int low, int mid, int high) {
    vector<int> temp(high - low + 1);
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= high) {
        temp[k++] = nums[j++];
    }
    for (i = low, k = 0; i <= high; ) {
        nums[i++] = temp[k++];
    }
}

void mergeSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
}

void mergeSort(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
}

​ 在这个代码中，我们首先实现了一个merge函数，用于将两个有序数组合并成一个有序数组。然后我们实现了一个mergeSort函数，用于对一个数组进行归并排序。

十二、搜索

概念：

​ 在计算机科学中，搜索是一种找出满足一定条件的元素或路径的方法。搜索可以在各种数据结构中进行，如数组、图、树等。搜索算法大致可分为两类：无信息搜索和有信息搜索。无信息搜索，如深度优先搜索和广度优先搜索，不考虑搜索的方向；有信息搜索，如A*搜索、启发式搜索，会根据条件选择最有可能的方向。

相关算法：深度优先搜索(DFS)、广度优先搜索(BFS)、A*搜索、Dijkstra算法、回溯算法

​ 这些算法都是在特定的数据结构中进行搜索的方法。例如，深度优先搜索和广度优先搜索通常用于在图或树中搜索；A*搜索和Dijkstra算法则是用于寻找图中的最短路径；回溯算法是一种通过探索所有可能的候选解来找出所有解的算法，适用于约束满足问题。

相关示例：寻找迷宫的出路

​ 在迷宫问题中，我们需要找到从起点到终点的路径。这个问题可以通过深度优先搜索或广度优先搜索来解决。

具体代码：

​ 下面是使用C++实现的深度优先搜索的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0)
        return;

    grid[i][j] = 0;

    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

​ 在这个代码中，我们定义了一个深度优先搜索的函数。这个函数首先判断当前的位置是否在网格内，以及这个位置是否可达。如果不在网格内或者不可达，那么我们就返回。否则，我们将这个位置标记为已访问，然后对这个位置的上下左右四个方向进行深度优先搜索。

十三、深度优先搜索

概念：

​ 深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这个策略是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

相关算法：图的遍历、回溯算法、拓扑排序

​ 这些都是深度优先搜索的应用。例如，图的遍历可以使用深度优先搜索；回溯算法是一种通过探索所有可能的候选解来找出所有解的算法，是深度优先搜索的一种；拓扑排序是对有向无环图的顶点的一种排序，也可以用深度优先搜索实现。

相关示例：迷宫问题

​ 在迷宫问题中，我们需要找到从起点到终点的路径。这个问题可以通过深度优先搜索来解决。

具体代码：

​ 下面是使用C++实现的深度优先搜索的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0)
        return;

    grid[i][j] = 0;

    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

​ 在这个代码中，我们定义了一个深度优先搜索的函数。这个函数首先判断当前的位置是否在网格内，以及这个位置是否可达。如果不在网格内或者不可达，那么我们就返回。否则，我们将这个位置标记为已访问，然后对这个位置的上下左右四个方向进行深度优先搜索。

十四、广度优先搜索

概念：

​ 广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。这个策略是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法结束。广泛应用在路径查找或图的连通性等问题上。

相关算法：图的遍历、最短路径算法、网络流最大流

​ 这些都是广度优先搜索的应用。例如，图的遍历可以使用广度优先搜索；最短路径算法中的Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等都会使用到广度优先搜索；网络流最大流问题也常常会用到广度优先搜索。

相关示例：找出图中的最短路径

​ 在找出图中的最短路径问题中，我们需要找到从起点到终点的最短路径。这个问题可以通过广度优先搜索来解决。

具体代码：

​ 下面是使用C++实现的广度优先搜索的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>
#include <vector>
using namespace std;

void bfs(vector<vector<int>>& grid, int start, int end) {
    queue<int> q;
    vector<bool> visited(grid.size(), false);

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int i = 0; i < grid[v].size(); ++i) {
            if (!visited[i] && grid[v][i] != 0) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

​ 在这个代码中，我们首先创建一个队列q和一个标记是否已经访问的数组visited。然后，我们将起始节点加入队列，并标记为已经访问。然后我们开始循环，每次都将队首元素出队，并遍历这个元素的所有邻居，如果邻居没有被访问过，并且它们之间有边，那么我们就将这个邻居加入队列，并标记为已经访问。这样我们就可以通过广度优先搜索遍历所有的节点。

十五、A*搜索

概念：

​ A 搜索是一种用于路径查找和图形遍历的算法。它的特点是利用启发式方法，为每个节点赋予预期的成本，从而提高搜索效率。A搜索是由最优先搜索算法和Dijkstra算法改进得来的。

相关算法：路径查找、地图导航、游戏AI

​ 这些都是A 搜索的应用。例如，路径查找问题中，我们需要找到从起点到终点的最短路径，这就可以使用A 搜索；在地图导航中，我们需要找到从一个地方到另一个地方的最短路径，也可以使用A 搜索；在游戏AI中，我们需要计算机角色能够找到从当前位置到目标位置的最优路径，这同样可以使用A 搜索。

相关示例：路径查找

​ 在路径查找问题中，我们需要找到从起点到终点的最短路径。这个问题可以通过A*搜索来解决。

具体代码：C++代码

下面是使用C++实现的A*搜索的代码：

C++
 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 <vector>
#include <queue>
#include <cmath>
using namespace std;

class Node {
public:
    int x, y;
    float g, h, f;
    Node(int x, int y): x(x), y(y), g(0), h(0), f(0) {}
};

// 这个比较函数用于优先队列，将f值最小的节点放在队列的前面
class Compare {
public:
    bool operator() (Node* a, Node* b) {
        return a->f > b->f;
    }
};

// 使用曼哈顿距离作为启发函数
float heuristic(Node* a, Node* b) {
    return abs(a->x - b->x) + abs(a->y - b->y);
}

// A*搜索函数
void AStarSearch(Node* start, Node* end) {
    priority_queue<Node*, vector<Node*>, Compare> openList;
    start->g = 0;
    start->h = heuristic(start, end);
    start->f = start->g + start->h;

    openList.push(start);
    // 此处省略其他部分的实现，包括从openList中选择f值最小的节点，将其相邻节点加入openList，以及更新g、h、f值等
}

​ 在这个代码中，我们首先定义了一个Node类，用于表示图中的节点。然后我们定义了一个比较函数，用于将f值最小的节点放在优先队列的前面。接着我们定义了一个启发函数，用于计算两个节点之间的预期成本。最后我们定义了A*搜索函数，这个函数将起始节点加入优先队列，然后开始循环，每次都从优先队列中取出f值最小的节点，然后更新这个节点的相邻节点的g值、h值和f值，并将这些相邻节点加入优先队列。这样我们就可以找到从起始节点到目标节点的最短路径。

十六、双向广度优先搜索

概念：

​ 双向广度优先搜索（Bidirectional Breadth-First Search，简称Bi-BFS）是广度优先搜索的变种，它同时从起始节点和目标节点开始搜索，当两个搜索的交集不为空时，搜索结束。双向广度优先搜索一般用于求解最短路径问题，相比于传统的从一端开始的广度优先搜索，它能够大大减少搜索的空间，提高效率。

相关算法：最短路径、图的遍历

​ 在最短路径问题中，我们需要找到从起点到终点的最短路径，这个问题可以通过双向广度优先搜索来解决。在图的遍历中，我们可以同时从起点和终点开始遍历，当两次遍历相遇时，遍历结束。

相关示例：最短路径

​ 在最短路径问题中，我们需要找到从起点到终点的最短路径。这个问题可以通过双向广度优先搜索来解决。

具体代码：

​ 下面是使用C++实现的双向广度优先搜索的代码：

C++
 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
#include <vector>
#include <queue>
using namespace std;

void bidirectionalBfs(vector<vector<int>>& graph, int start, int end) {
    vector<int> dist1(graph.size(), -1);
    vector<int> dist2(graph.size(), -1);
    queue<int> q1, q2;

    q1.push(start);
    dist1[start] = 0;
    q2.push(end);
    dist2[end] = 0;

    while (!q1.empty() || !q2.empty()) {
        if (!q1.empty()) {
            int node = q1.front();
            q1.pop();
            for (int neighbor : graph[node]) {
                if (dist1[neighbor] == -1) {
                    dist1[neighbor] = dist1[node] + 1;
                    q1.push(neighbor);
                }
            }
        }
        if (!q2.empty()) {
            int node = q2.front();
            q2.pop();
            for (int neighbor : graph[node]) {
                if (dist2[neighbor] == -1) {
                    dist2[neighbor] = dist2[node] + 1;
                    q2.push(neighbor);
                }
            }
        }
    }
    // 此处省略了检查两个搜索是否相交的代码
}

​ 在这个代码中，我们首先创建了两个队列和两个距离数组，然后我们将起点和终点分别加入到两个队列中，并将它们的距离设置为0。然后我们开始循环，每次都将队列中的队首元素出队，并将这个元素的所有邻居的距离加1，并将这些邻居加入队列。我们同时进行这个操作，直到两个搜索相交。

十七、动态规划

概念：

​ 动态规划（Dynamic Programming，简称DP）是一种用于求解多阶段决策问题的优化方法。它将原问题拆解为若干个子问题，然后保存子问题的解，避免重复计算。动态规划适用于有重叠子问题和最优子结构性质的问题。

相关算法：背包问题、最长公共子序列、最长上升子序列

​ 这些都是动态规划的典型应用。例如，背包问题中，我们需要决定每种物品的取舍；在最长公共子序列问题中，我们需要找出两个序列的最长公共子序列；在最长上升子序列问题中，我们需要在一个无序的整数数组中找到一个子序列，使得这个子序列是升序的，并且长度最长。

相关示例：斐波那契数列

​ 斐波那契数列是动态规划的一个简单例子。每个斐波那契数是前两个斐波那契数的和，我们可以用动态规划的方式来避免重复计算。

具体代码：

​ 下面是使用C++实现的斐波那契数列的动态规划代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
using namespace std;
vector<int> dp(1000, 0);

int fib(int n) {
    if (n <= 1)
        return n;
    if (dp[n] != 0)
        return dp[n];
    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

​ 在这个代码中，我们首先创建一个全局的dp数组来保存子问题的解。在计算斐波那契数的函数中，我们首先检查dp数组中是否已经保存了当前的斐波那契数。如果已经保存了，那么我们就直接返回这个值；否则，我们就计算这个斐波那契数，并保存到dp数组中，然后返回这个值。

十八、贪心法

概念：

​ 贪心法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。

相关算法：区间调度、Dijkstra算法、霍夫曼编码

​ 这些算法都是贪心法的典型应用，它们在每一步都选择最优的解，从而得到全局最优的解。

相关示例：找零问题

​ 例如，在找零问题中，我们有1分、5分、10分、25分、1美元等几种面值的硬币，我们希望用最少的硬币找给客人指定金额的零钱。这个问题就可以用贪心法解决，我们每次都选择面值最大的硬币，直到找齐全部的零钱。

具体代码：

​ 下面是使用C++实现的找零问题的贪心算法：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <vector>
#include <algorithm>
using namespace std;

vector<int> coinChange(int amount, vector<int>& coins) {
    vector<int> result;
    sort(coins.rbegin(), coins.rend());
    for (int i = 0; i < coins.size(); ++i) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            result.push_back(coins[i]);
        }
    }
    return result;
}

​ 在这个代码中，我们首先将硬币按照面值从大到小排序，然后我们依次从面值最大的硬币开始，每次都尽可能多的使用当前面值的硬币，直到无法继续使用为止，然后我们继续下一种面值的硬币，直到找齐全部的零钱。

十九、离散化

概念：

​ 离散化是一种数据预处理技术，主要用于处理数值范围过大、不连续或者无法直接处理的问题。其主要思想是将数据从原本的数值映射到一个连续的、较小的区间内，从而简化问题。

相关算法：将数据映射到一个连续的区间

​ 离散化的具体方法因问题而异，一种常见的方法是先将所有出现过的数值进行排序，然后将排序后的序列中不同的数值依次映射到从1开始的自然数。

相关示例：处理坐标压缩问题

​ 例如，有一个二维平面的点集，每个点的坐标可能很大，我们可以通过离散化，将这些点的坐标映射到一个较小的区间，从而简化问题。

具体代码：

​ 下面是使用C++实现的离散化的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector<int> discretization(vector<int>& nums) {
    vector<int> sortedNums(nums);
    sort(sortedNums.begin(), sortedNums.end());
    sortedNums.erase(unique(sortedNums.begin(), sortedNums.end()), sortedNums.end());

    map<int, int> numToDiscrete;
    for (int i = 0; i < sortedNums.size(); ++i) {
        numToDiscrete[sortedNums[i]] = i + 1;
    }

    vector<int> discreteNums(nums.size());
    for (int i = 0; i < nums.size(); ++i) {
        discreteNums[i] = numToDiscrete[nums[i]];
    }
    return discreteNums;
}

​ 在这个代码中，我们首先将所有出现过的数值进行排序，并去重，然后将排序后的序列中不同的数值依次映射到从1开始的自然数。

二十、拟阵

概念：

​ 拟阵(Matroid)是一种数学结构，用于描述一类满足交换性和扩展性的集合系统。它有两个基本的性质：一是如果A是这个系统的一个独立集，B是这个系统的一个独立集且|B|>|A|，那么一定存在一个元素x∈B−A，使得A∪{x}仍然是一个独立集；二是所有大小相等的最大独立集的大小相同。

相关算法：贪心算法

​ 拟阵的一个重要性质是它能够支持贪心算法。在拟阵中，如果我们每次选择当前最优的元素添加到独立集中，那么我们最终得到的一定是最大的独立集。

相关示例：最小生成树

​ 在最小生成树的问题中，我们可以把所有的边看作一个集合，一个无环连通子图看作一个独立集。这样，这个问题就形成了一个拟阵，我们可以用贪心算法求解最小生成树。

具体代码：

​ 注意，拟阵是一种数学概念，它描述的是一类问题的性质，而不是具体的算法或数据结构。因此，我们并不能直接提供一个拟阵的C++实现。但是，我们可以给出一个使用拟阵性质的最小生成树的Kruskal算法的实现：

C++
 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
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

vector<int> parent;
vector<int> rank;

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

int kruskal(vector<Edge> & edges, int n) {
    int cost = 0;
    sort(edges.begin(), edges.end());

    parent.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; i++)
        make_set(i);

    for (Edge e : edges) {
        if (find_set(e.u) != find_set(e.v)) {
            cost += e.weight;
            union_sets(e.u, e.v);
        }
    }

    return cost;
}

​ 在这个代码中，我们首先定义了一个表示边的结构体，然后我们定义了一个并查集，用于快速查询和合并两个节点是否在同一个连通分量中。最后，我们实现了Kruskal算法，首先我们将所有的边按照权重排序，然后我们遍历所有的边，如果一条边的两个节点不在同一个连通分量中，那么我们就将这条边加入到最小生成树中。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用