1.基础算法

[[ACM技能树]]

1.1 构造

• 定义：
  • 构造算法，顾名思义，是指直接构造出问题的一个解决方案的方法。 这类算法通常适用于那些有明确解决方案或者解的结构可以直接描述的问题。 与暴力搜索或试错法不同，构造算法往往需要对问题有更深的理解和分析，通过逻辑或数学方法直接构造出答案。
• 特点
  1. 直接性：算法直接构建解决方案，而不是通过搜索或枚举所有可能的解。
  2. 逐步构建：解决方案是通过一系列步骤逐步构建的，每一步都向最终目标迈进。
  3. 可行性：每一步构建都是可行的，并且能够保证最终结果的正确性。
• 应用场景
  • 字符串操作：如字符串反转、回文检查、子串替换等。
  • 数据结构操作：如链表反转、栈和队列的实现等。
  • 几何问题：如构建凸包、计算几何图形的属性等。
  • 图问题：如构建图的遍历路径、拓扑排序等
• 示例：字符串反转
  • 假设我们需要反转一个字符串。这是一个典型的构造问题，因为我们可以通过直接操作字符来构建反转后的字符串。
• 题解：

def reverse_string(s):
    reversed_s = ""  # 创建一个空字符串来存储反转后的结果
    for char in s:
        reversed_s = char + reversed_s  # 将每个字符添加到结果字符串的前面
    return reversed_s

# 测试
input_string = "Hello, World!"
print("Reversed string:", reverse_string(input_string))

1.2 枚举

• 定义
  • 枚举算法，也称为穷举算法，是一种通过尝试所有可能的候选解来寻找问题的解的方法。这种算法的关键在于系统地列出所有可能的情况，并检查每一个候选解是否满足问题的条件。如果找到满足条件的解，算法就可以停止搜索。
  • 枚举算法通常适用于解空间较小，可以通过有限的步骤穷尽所有可能性的问题。随着解空间的增大，枚举算法可能会变得非常耗时，因此在实际应用中，通常会配合一些剪枝技巧来减少不必要的搜索。
• 特点
  1. 系统性：算法需要系统地遍历所有可能的解。
  2. 完备性：如果问题的解存在，枚举算法一定能找到一个解。
  3. 剪枝：为了提高效率，通常会在搜索过程中使用剪枝技术，排除那些明显不会得到解的搜索分支。
• 应用场景
  • 排列问题：比如找出一个数的所有因数。
  • 组合问题：比如找出所有满足特定条件的数字组合。
  • 子集问题：比如找出一个集合的所有非空子集。
  • 划分问题：比如将一个集合分成两个子集，使得两个子集中元素的和相等。

• 示例：找出所有满足条件的组合
  • 假设我们有一个集合 {1, 2, 3, 4}，我们想找出所有元素和为5的组合。
• 题解

def find_combinations(nums, target, cur=[]):
    results = []
    cur_sum = sum(cur)
    
    for i in range(len(nums)):
        if cur_sum + nums[i] > target:
            continue
        if cur_sum + nums[i] == target:
            results.append(cur + [nums[i]])
        else:
            results.extend(find_combinations(nums[i:], target, cur + [nums[i]]))
    
    return results

# 测试
nums = [1, 2, 3, 4]
target_sum = 5
print(find_combinations(nums, target_sum))

1.3 模拟

• 定义
  • 模拟算法，它通过模拟现实世界的操作过程来解决问题。这种算法的核心思想是将问题分解成一系列可控制的步骤，然后通过编程语言来模拟这些步骤的执行过程。模拟算法特别适用于那些难以用数学公式直接求解的问题，比如交通模拟、天气预测等。
  • 假设我们需要模拟掷骰子的过程。骰子有六个面，每个面的概率都是相等的。我们可以使用C++的随机数生成器来模拟这个过程。
• 步骤
  1. 确定模拟的步骤：在开始编写代码之前，首先需要明确模拟过程中需要执行的步骤。这通常涉及到对问题进行详细的分析，确定每一步的具体操作。
  2. 设计数据结构：模拟过程中需要存储和操作的数据需要通过合适的数据结构来管理。常见的数据结构包括数组、链表、队列、栈等。
  3. 编写模拟代码：根据确定的步骤和数据结构，编写代码来模拟整个过程。这通常涉及到循环和条件判断的使用。
• 示例
  • 模拟了一个简单的猜拳游戏：

#include <iostream>
#include <cstdlib>
#include <ctime>

// 函数声明，用于生成随机的猜拳选项
int generateRandomChoice();

int main() {
    srand(time(0)); // 初始化随机数种子
    int userChoice = generateRandomChoice();
    int computerChoice = generateRandomChoice();
    
    std::cout << "你出了: " << userChoice << std::endl;
    std::cout << "电脑出了: " << computerChoice << std::endl;
    
    // 判断胜负
    if (userChoice == computerChoice) {
        std::cout << "平局！" << std::endl;
    } else if ((userChoice == 1 && computerChoice == 2) ||
               (userChoice == 2 && computerChoice == 3) ||
               (userChoice == 3 && computerChoice == 1)) {
        std::cout << "你赢了！" << std::endl;
    } else {
        std::cout << "你输了！" << std::endl;
    }
    
    return 0;
}

// 生成随机的猜拳选项（1: 石头，2: 剪刀，3: 布）
int generateRandomChoice() {
    return rand() % 3 + 1;
}

1.4 贪心

• 定义
  • 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，希望导致结果是全局最好或最优的算法策略。贪心算法不保证会得到最优解，但在某些情况下它可以产生最优解，并且它的优点是简单、直观且易于实现。
• 特点
  1. 局部最优：在每一步都做出当前看起来最好的选择，而不考虑子问题的解如何影响未来的状态。
  2. 贪心选择性质：总是做出一个选择，这个选择在当前状态下最好，而不管未来的可能结果。
  3. 可行性：每一个贪心选择都是可行的，并且可以实施。
• 应用场景：
  • 哈夫曼编码：用于数据压缩，通过贪心算法为字符分配最优编码。
  • 最小生成树：如Kruskal算法和Prim算法，通过连接权值最小的边来构建一棵树，覆盖所有顶点。
  • 图的最短路径：Dijkstra算法在每一步选择最小的边进行松弛操作。
  • 任务调度：选择具有最早截止日期的任务优先执行。
  • 硬币找零：选择最大面额的硬币进行找零。

• 贪心算法的示例：活动选择问题
  • 假设有一组活动，每个活动都有一个开始时间和结束时间，我们要选择尽可能多的互不重叠的活动。我们可以按照活动的结束时间对活动进行排序，然后贪心地选择结束时间最早的活动，接着选择下一个不与之重叠的结束时间最早的活动。

• 题解

#include <iostream>
#include <vector>
#include <algorithm>

// 定义活动结构体
struct Activity {
    int start;
    int finish;
};

// 按结束时间排序的比较函数
bool activityCompare(Activity s1, Activity s2) {
    return s1.finish < s2.finish;
}

// 贪心算法选择最大数量的不重叠活动
int selectActivities(std::vector<Activity>& activities) {
    // 按结束时间对活动进行排序
    std::sort(activities.begin(), activities.end(), activityCompare);
    
    int count = 1; // 第一个活动总是被选中
    int lastFinishTime = activities[0].finish;
    
    for (int i = 1; i < activities.size(); i++) {
        // 如果下一个活动的开始时间大于或等于最后一个活动的结束时间
        if (activities[i].start >= lastFinishTime) {
            count++;          // 选择这个活动
            lastFinishTime = activities[i].finish; // 更新最后结束时间
        }
    }
    
    return count;
}

int main() {
    std::vector<Activity> activities = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
    int result = selectActivities(activities);
    std::cout << "最大数量的不重叠活动是: " << result << std::endl;
    return 0;
}

1.5 分治

• 定义
  • 分治算法（Divide and Conquer）是一种解决问题的策略，其基本思想是将一个难以直接解决的大问题分解（Divide）成若干个规模较小且易于解决的子问题。递归地解决这些子问题（Conquer），然后将子问题的解合并（Combine）起来，最终得到原问题的解。分治算法在解决复杂问题时非常有效，尤其是那些可以分解为相似子问题的问题。
• 特点
  • 递归：分治算法通常使用递归实现，每个递归调用处理一个子问题。
  • 重复性：子问题往往是原问题的较小版本，利用相同的算法解决。
  • 独立性：子问题之间相互独立，一个子问题的解决不影响其他子问题。
  • 局部性：分治算法通常将问题分解为可以并行处理的子问题，有利于并行计算。

• 应用场景
  • 排序算法（如归并排序和快速排序）、二分搜索、最大子数组和、矩阵乘法的Strassen算法等。
• 分治算法的示例：归并排序
  归并排序是一种典型的分治算法，其基本步骤如下：
  1. 分解：将数组分成两半。
  2. 解决：递归地对两半分别进行归并排序。
  3. 合并：将两个已排序的半部分合并成一个排序好的完整数组。

#include <iostream>
#include <vector>

// 合并两个子数组的函数
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    std::vector<int> L(n1), R(n2);

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组回原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝L的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 拷贝R的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();

    mergeSort(arr, 0, n - 1);

    std::cout << "Sorted array: \n";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}

1.6 递归

• 递归算法是一种在算法设计中常用的方法，它涉及函数自己调用自己的过程。递归算法通常包含两个主要部分：
  1. 基本情况（Base Case）：这是递归调用停止的条件。如果没有基本情况，递归将无限进行下去，导致栈溢出错误。
  2. 递归情况（Recursive Case）：这是函数调用自己的情况，每次调用都应该将问题规模缩小，并且逐渐接近基本情况。
• 递归算法的特点：
  • 简洁性：递归算法的代码通常比迭代算法更简洁，更接近问题的数学定义。
  • 重复性：递归算法中的每个递归调用本质上都是原问题的简化版本。
  • 记忆化：为了避免重复计算，递归算法常常结合记忆化技术（即存储已计算结果）来提高效率。

• 递归算法的示例：斐波那契数列
  • 斐波那契数列是一个经典的递归问题，其中每个数字是前两个数字的和（F(n) = F(n-1) + F(n-2)），基本情况是 F(0) = 0 和 F(1) = 1。

• 题解：

#include <iostream>

// 斐波那契数列的递归函数
int fibonacci(int n) {
    if (n <= 1) {
        return n; // 基本情况
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归情况
    }
}

int main() {
    int n = 10;
    std::cout << "斐波那契数列的第 " << n << " 项是: " << fibonacci(n) << std::endl;
    return 0;
}

• 注意事项：
  1. 栈溢出：如果递归深度太深，可能会导致栈溢出。为了避免这个问题，可以增加基本情况，减少递归深度，或者使用尾递归优化。
  2. 效率问题：递归算法可能会重复计算相同的子问题，这会导致效率低下。为了解决这个问题，可以使用记忆化技术来存储已经计算过的结果。
  3. 可读性：虽然递归代码通常更简洁，但有时它可能难以理解，特别是对于不习惯递归思维的程序员。