1. 枚举法
   枚举法是一种基本的问题解决策略，它尝试所有可能的情况以找到解决方案。这种方法通常用于问题规模较小且可以接受一定时间复杂度的情况。

例子：找出三个数中最大的数

#include <iostream>
using namespace std;int findMax(int a, int b, int c) {return max(a, max(b, c));
}int main() {int x, y, z;cin >> x >> y >> z;cout << "最大值是: " << findMax(x, y, z) << endl;return 0;
}

2. 模拟法
   模拟法是指按照实际过程或规则进行模拟以解决问题的方法。例如模拟交通信号灯的变化。

例子：简单的交通灯控制

#include <iostream>
#include <thread>
#include <chrono>void trafficLight() {string lights[] = {"红", "绿", "黄"};for (auto &light : lights) {cout << "当前灯为：" << light << endl;this_thread::sleep_for(chrono::seconds(5)); // 假设每个状态持续5秒}
}int main() {while (true) {trafficLight();}return 0;
}

3. 递推算法
   递推算法基于前几个元素的结果来计算后续元素，最著名的例子是斐波那契数列。

例子：计算斐波那契数列第n项

#include <iostream>
using namespace std;long long fibonacci(int n) {if (n <= 1) return n;long long prev = 0, curr = 1, next;for (int i = 2; i <= n; ++i) {next = prev + curr;prev = curr;curr = next;}return curr;
}int main() {int n;cin >> n;cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;return 0;
}

4. 排序算法 - 冒泡排序
   冒泡排序通过重复地遍历列表，比较相邻元素并根据需要交换它们的位置，直到没有更多的交换为止。

例子：对整数数组进行排序

#include <iostream>
using namespace std;void bubbleSort(int arr[], int n) {bool swapped;for (int i = 0; i < n-1; i++) {swapped = false;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);swapped = true;}}// 如果内循环中没有发生任何交换，则数组已经有序if (!swapped)break;}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr)/sizeof(arr[0]);bubbleSort(arr, n);cout << "Sorted array: \n";for (int i=0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

5. 排序算法 - 插入排序
   插入排序是一种简单直观的排序算法，它的工作原理是将未排序元素依次插入到已排序部分的正确位置。

例子：对整数数组进行插入排序

#include <iostream>
using namespace std;// 插入排序函数
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 将 arr[i] 插入到已排序序列 arr[0..i-1] 的正确位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);cout << "Sorted array: ";for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

在 insertionSort 函数中，对于未排序部分的每个元素 arr[i]，将其与已排序部分的元素进行比较，并将其插入到正确位置。我们将 arr[i] 的值存储在 key 中，然后将比 key 大的元素向右移动，直到找到 key 的正确位置。

6. 排序算法 - 选择排序
   选择排序的基本思想是在未排序部分中找到最小元素，并将其放到已排序部分的末尾。

例子：对整数数组进行选择排序

#include <iostream>
using namespace std;// 选择排序函数
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int min_index = i;// 找到未排序部分的最小元素的索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index])min_index = j;}// 交换最小元素和当前元素swap(arr[i], arr[min_index]);}
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);cout << "Sorted array: ";for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

在 selectionSort 函数中，对于每个 i，我们遍历未排序部分（从 i+1 到 n-1）找到最小元素的索引 min_index，然后将该元素与 arr[i] 交换位置。

7. 归并排序
   归并排序是一种分治算法，将数组分成两半，对每一半进行排序，然后将排序好的两半合并在一起。

例子：对整数数组进行归并排序

#include <iostream>
using namespace std;// 合并两个已排序的子数组
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];// 复制数据到辅助数组for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;// 合并 L 和 R 到 arr[l..r]while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}// 复制 L 中剩余元素while (i < n1)arr[k++] = L[i++];// 复制 R 中剩余元素while (j < n2)arr[k++] = R[j++];
}// 归并排序函数
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}
}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1);cout << "Sorted array: ";for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

mergeSort 函数将数组分成两半，分别对左右两部分递归调用 mergeSort 函数进行排序，然后调用 merge 函数将排序好的两部分合并起来。

8. 快速排序
   快速排序也是一种分治算法，通过选取一个基准元素，将数组分成两部分，一部分的元素都小于等于基准元素，另一部分的元素都大于基准元素。

例子：对整数数组进行快速排序

#include <iostream>
using namespace std;// 划分函数
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] <= pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return (i + 1);
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);cout << "Sorted array: ";for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

quickSort 函数通过 partition 函数将数组划分为两部分，小于等于基准的元素在左边，大于基准的元素在右边，然后对左右两部分分别递归调用 quickSort 函数进行排序。

9. 二分查找
   二分查找是一种在有序数组中查找目标元素的高效算法，通过将搜索范围减半来提高查找效率。

例子：在有序整数数组中查找元素

#include <iostream>
using namespace std;// 二分查找函数
int binarySearch(int arr[], int l, int r, int target) {while (l <= r) {int mid = l + (r - l) / 2;if (arr[mid] == target)return mid;if (arr[mid] < target)l = mid + 1;elser = mid - 1;}return -1;
}int main() {int arr[] = {2, 3, 4, 10, 40};int n = sizeof(arr) / sizeof(arr[0]);int target = 10;int result = binarySearch(arr, 0, n - 1, target);if (result == -1)cout << "元素未找到" << endl;elsecout << "元素在索引 " << result << " 处" << endl;return 0;
}

binarySearch 函数不断将数组分为两半，根据中间元素与目标元素的大小关系更新左右边界，直到找到目标元素或搜索范围为空。

10. 贪心算法
    贪心算法在每一步都做出当前最优的选择，而不考虑全局最优。

例子：找零问题，使用最少的硬币数量找零

#include <iostream>
#include <vector>
using namespace std;vector<int> coinChange(vector<int>& coins, int amount) {vector<int> result(coins.size(), 0);for (int i = coins.size() - 1; i >= 0; i--) {result[i] = amount / coins[i];amount %= coins[i];}return result;
}int main() {vector<int> coins = {25, 10, 5, 1};int amount = 42;vector<int> change = coinChange(coins, amount);for (int i = 0; i < change.size(); i++) {cout << "硬币 " << coins[i] << " 的数量: " << change[i] << endl;}return 0;
}

在 coinChange 函数中，从最大面额的硬币开始，尽可能多地使用该硬币，直到无法使用，然后考虑下一个面额较小的硬币。

11. 分治算法
    分治算法将一个大问题分解为多个相同或相似的子问题，解决子问题，然后将子问题的结果合并得到最终结果。

例子：计算数组的最大子数组和

#include <iostream>
#include <limits>
using namespace std;// 求跨越中点的最大子数组和
int maxCrossingSum(int arr[], int l, int m, int r) {int sum = 0;int left_sum = numeric_limits<int>::min();for (int i = m; i >= l; i--) {sum += arr[i];if (sum > left_sum)left_sum = sum;}sum = 0;int right_sum = numeric_limits<int>::min();for (int i = m + 1; i <= r; i++) {sum += arr[i];if (sum > right_sum)right_sum = sum;}return left_sum + right_sum;
}// 求最大子数组和
int maxSubArraySum(int arr[], int l, int r) {if (l == r)return arr[l];int m = (l + r) / 2;return max(max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, r)), maxCrossingSum(arr, l, m, r));
}int main() {int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};int n = sizeof(arr) / sizeof(arr[0]);int max_sum = maxSubArraySum(arr, 0, n - 1);cout << "最大子数组和: " << max_sum << endl;return 0;
}

maxSubArraySum 函数将数组分成左右两部分，分别计算左右两部分的最大子数组和及跨越中点的最大子数组和，然后取最大值。

12. 深度优先搜索算法（DFS）
    深度优先搜索是一种遍历或搜索树或图的算法，尽可能深地搜索每个分支。

例子：使用 DFS 遍历图

#include <iostream>
#include <vector>
using namespace std;void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {visited[node] = true;cout << node << " ";for (int neighbor : graph[node]) {if (!visited[neighbor])dfs(neighbor, graph, visited);}
}int main() {vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};vector<bool> visited(6, false);dfs(0, graph, visited);return 0;
}

dfs 函数从起始节点开始，递归地访问未访问过的邻居节点。

13. 宽度优先搜索算法（BFS）
    宽度优先搜索是一种逐层遍历图的算法，先访问距离起始节点近的节点。

例子：使用 BFS 遍历图

#include <iostream>
#include <vector>
#include <queue>
using namespace std;void bfs(int start, vector<vector<int>>& graph) {vector<bool> visited(graph.size(), false);queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int node = q.front();q.pop();cout << node << " ";for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};bfs(0, graph);return 0;
}

bfs 函数使用队列存储待访问节点，先将起始节点入队，然后循环取出队首节点并将其未访问的邻居节点入队。

14. 二叉树的搜索算法
    包括前序、中序、后序遍历等，以下是前序遍历的例子。

例子：二叉树的前序遍历

#include <iostream>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 前序遍历函数
void preorderTraversal(TreeNode* root) {if (root == NULL) return;cout << root->val << " ";preorderTraversal(root->left);preorderTraversal(root->right);
}int main() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);preorderTraversal(root);return 0;
}

preorderTraversal 函数先访问根节点，然后递归访问左子树和右子树。

15. 简单动态规划（一维动态规划、简单背包问题）
    动态规划保存子问题的解，避免重复计算。

例子：简单的0/1背包问题

#include <iostream>
#include <vector>
using namespace std;int knapSack(int W, vector<int>& wt, vector<int>& val, int n) {vector<int> dp(W + 1, 0);for (int i = 0; i < n; i++) {for (int w = W; w >= wt[i]; w--) {dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);}}return dp[W];
}int main() {vector<int> wt = {10, 20, 30};vector<int> val = {60, 100, 120};int W = 50;int n = wt.size();cout << knapSack(W, wt, val, n) << endl;return 0;
}

knapSack 函数使用一维数组 dp 存储子问题的最优解，通过更新 dp[w] 的值表示背包容量为 w 时的最大价值。

16. 复杂动态规划（二维动态规划、动态规划最值优化）
    复杂动态规划使用二维状态或优化技巧。

例子：最长公共子序列（LCS）

#include <iostream>
#include <string>
#include <vector>
using namespace std;int lcs(string X, string Y) {int m = X.length();int n = Y.length();vector<vector<int>> L(m + 1, vector<int>(n + 1));for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0)L[i][j] = 0;else if (X[i - 1] == Y[j - 1])L[i][j] = L[i - 1][j - 1] + 1;elseL[i][j] = max(L[i - 1][j], L[i][j - 1]);}}return L[m][n];
}int main() {string X = "AGGTAB";string Y = "GXTXAYB";cout << "LCS 的长度是 " << lcs(X, Y) << endl;return 0;
}

lcs 函数使用二维数组 L 存储子问题的最优解，根据字符是否相等更新 L[i][j] 的值。

17. 图的泛洪算法（flood fill）
    图的泛洪算法用于处理图或图像中的连通区域问题。

例子：图像的泛洪填充

#include <iostream>
#include <vector>
using namespace std;void floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {int oldColor = image[sr][sc];if (oldColor == newColor) return;int rows = image.size();int cols = image[0].size();if (sr < 0 || sr >= rows || sc < 0 || sc >= cols) return;image[sr][sc] = newColor;if (sr > 0 && image[sr - 1][sc] == oldColor)floodFill(image, sr - 1, sc, newColor);if (sr < rows - 1 && image[sr + 1][sc] == oldColor)floodFill(image, sr + 1, sc, newColor);if (sc > 0 && image[sr][sc - 1] == oldColor)floodFill(image, sr, sc - 1, newColor);if (sc < cols - 1 && image[sr][sc + 1] == oldColor)floodFill(image, sr, sc + 1, newColor);
}int main() {vector<vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};int sr = 1, sc = 1, newColor = 2;floodFill(image, sr, sc, newColor);for (auto& row : image) {for (int pixel : row)cout << pixel << " ";cout << endl;}return 0;
}

floodFill 函数从起始位置开始，将颜色为 oldColor 的相邻像素更新为 newColor，并递归地对相邻像素进行填充。

18. kruskal 算法、prim 算法
    kruskal 算法和 prim 算法用于求解最小生成树问题。

例子：kruskal 算法

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;// 邻接表表示图，存储边的权值
typedef pair<int, int> iPair;
vector<vector<iPair>> adj;// Dijkstra 算法
void dijkstra(int V, int src) {// 优先队列存储节点和距离，最小堆priority_queue<iPair, vector<iPair>, greater<iPair>> pq;// 存储距离源点的最短距离vector<int> dist(V, numeric_limits<int>::max());// 源点到自身的距离为 0pq.push(make_pair(0, src));dist[src] = 0;while (!pq.empty()) {int u = pq.top().second;pq.pop();for (auto &neighbor : adj[u]) {int v = neighbor.first;int weight = neighbor.second;if (dist[v] > dist[u] + weight) {dist[v] = dist[u] + weight;pq.push(make_pair(dist[v], v));}}}// 输出从源点到各个节点的最短距离for (int i = 0; i < V; ++i) {cout << src << " 到 " << i << " 的最短距离: " << dist[i] << endl;}
}int main() {int V = 5;  // 节点数量adj.resize(V);// 添加边到邻接表adj[0].push_back(make_pair(1, 9));adj[0].push_back(make_pair(2, 6));adj[1].push_back(make_pair(2, 5));adj[1].push_back(make_pair(3, 2));adj[2].push_back(make_pair(3, 4));adj[2].push_back(make_pair(4, 7));adj[3].push_back(make_pair(4, 3));int src = 0;  // 源点dijkstra(V, src);return 0;
}

Floyd 算法

#include <iostream>
#include <vector>
#include <limits>
using namespace std;// Floyd 算法
void floyd(vector<vector<int>>& graph) {int V = graph.size();// 存储最短距离vector<vector<int>> dist(V, vector<int>(V));for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {dist[i][j] = graph[i][j];}}for (int k = 0; k < V; ++k) {for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {if (dist[i][k]!= numeric_limits<int>::max() && dist[k][j]!= numeric_limits<int>::max() && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}// 输出最短距离矩阵for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {if (dist[i][j] == numeric_limits<int>::max()) {cout << "INF ";} else {cout << dist[i][j] << " ";}}cout << endl;}
}int main() {int V = 4;  // 节点数量vector<vector<int>> graph = {{0, 5, numeric_limits<int>::max(), 10},{numeric_limits<int>::max(), 0, 3, numeric_limits<int>::max()},{numeric_limits<int>::max(), numeric_limits<int>::max(), 0, 1},{numeric_limits<int>::max(), numeric_limits<int>::max(), numeric_limits<int>::max(), 0}};floyd(graph);return 0;
}