【优选算法篇】模拟算法的艺术：在不确定性中找到解法（上篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对 C++算法 感兴趣的朋友，让我们一起进步！

1. C++ 模拟算法 详解

1.1 模拟算法的重要性

1. 解决解析难以处理的问题：许多实际问题具有高度复杂性或不确定性，无法通过常规的解析方法直接求解。模拟算法提供了一种有效的替代方案，尤其是在数学模型过于复杂、无法得到封闭解的情况下。
2. 高效处理大规模问题：模拟算法常用于处理大规模数据集或大维度问题，能够在有限时间内获得近似解。例如，在高维度优化问题中，解析方法常常无法适应，而模拟算法如模拟退火（Simulated Annealing）和蒙特卡洛方法（Monte Carlo）则能够有效地搜索解空间。
3. 适应不确定性和随机性：现实世界中的很多问题都包含不确定性和随机性（如天气预测、股市分析）。模拟算法通过引入随机性，能够有效地应对这些不确定因素。
4. 多领域应用：模拟算法广泛应用于物理学、计算机科学、经济学、工程学、金融学等多个领域，为许多跨学科问题提供了强有力的解决工具。

1.2 模拟算法的定义

模拟算法是一类通过模拟真实世界过程来解决问题的算法。它通过计算机模拟复杂系统的行为，帮助我们分析和解决那些难以通过解析方法直接求解的问题。模拟算法通常通过随机化、迭代、近似等技术，利用计算机的强大计算能力来获得问题的近似解。

1.3 模拟算法的核心思想

模拟算法的核心思想通常包括以下几个方面：

1. 随机性引导搜索：许多模拟算法利用随机数生成器引导搜索过程，以便在解空间中找到可能的最优解。通过引入随机性，模拟算法能够避免陷入局部最优解，从而更好地探索全局解空间。
2. 近似解：与精确解不同，模拟算法通常侧重于通过多次随机试验来获得问题的近似解。这种方法在实际应用中常常能够提供足够精确的答案，同时节省了计算资源和时间。
3. 逐步优化：许多模拟算法通过迭代或逐步改进的方式来优化解的质量。例如，模拟退火算法通过逐渐降低温度来优化解，模拟遗传算法则通过选择、交叉和变异等操作不断改进解。
4. 大量重复实验：模拟算法通常依赖于大量的重复实验来收集数据和趋势，从中提取有用的信息。这些实验可以通过蒙特卡洛方法等进行多次采样，得出结果的统计特性。

1.4 模拟算法的经典应用

1. 蒙特卡洛方法（Monte Carlo Method） 蒙特卡洛方法是模拟算法中最著名的一个，它通过随机采样来计算问题的近似解。经典应用包括：
   • 计算积分：对高维积分或复杂函数的积分进行估算。
   • 风险评估与金融工程：在金融领域，蒙特卡洛方法用于模拟股票价格波动、期权定价、风险管理等。
   • 物理学中的粒子模拟：通过模拟大量粒子的行为来研究物理现象，如气体分子运动、核反应等。
2. 模拟退火（Simulated Annealing） 模拟退火是一种基于物理退火过程的优化算法，通过模拟金属加热并逐渐冷却的过程来寻找全局最优解。经典应用包括：
   • 组合优化问题：如旅行商问题（TSP）、图着色问题、装配线调度问题等。
   • 机器学习中的超参数优化：用来调整模型的超参数，提升模型性能。
3. 遗传算法（Genetic Algorithm） 遗传算法是模拟自然选择和遗传机制的优化算法。通过模拟自然选择中的交叉、变异和选择过程，遗传算法能够找到复杂问题的优化解。经典应用包括：
   • 模式识别：用于特征选择、图像识别等任务。
   • 工程设计优化：如结构优化、路径规划等。
4. 粒子群优化（Particle Swarm Optimization, PSO） 粒子群优化算法模拟鸟群觅食的过程，通过多颗“粒子”在解空间中搜索最优解。应用领域包括：
   • 机器学习中的特征选择：选择对模型最有用的特征。
   • 控制系统优化：在机器人控制、航天器路径规划等领域中应用广泛。
5. 扩展卡尔曼滤波（Extended Kalman Filter, EKF） 卡尔曼滤波是一种用于线性系统的递推滤波算法，其扩展形式用于非线性系统的状态估计。广泛应用于：
   • 自动驾驶：车辆定位、路径规划等。
   • 机器人导航：通过传感器数据对机器人的位置进行实时估计。

2. 题目1：替换所有的问号

题目链接：1576. 替换所有的问号 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

1. 遍历字符串：
   • 我们通过遍历字符串，逐个检查每个字符。
   • 如果当前字符是 '?'，则需要进行替换操作。
2. 替换 '?' 字符：
   • 对于每一个 '?'，我们尝试将它替换为字母 'a' 到 'z' 中的一个字母。为了避免与相邻的字符重复，只有当候选字母与前一个字符和后一个字符都不相同时，才选择该字母进行替换。
3. 判断条件：
   • 如果 '?' 位于字符串的第一个位置（i == 0），它不需要与前一个字符比较，只需要检查它是否与后一个字符相同。
   • 如果 '?' 位于字符串的最后一个位置（i == s.size() - 1），它不需要与后一个字符比较，只需要检查它是否与前一个字符相同。
   • 对于中间的字符，我们需要同时检查它的前一个和后一个字符。
4. 返回结果：
   • 替换完所有的 '?' 字符后，返回修改后的字符串。

2.2 示例代码：

class Solution 
{
public:
    string modifyString(string s) 
    {
        // 遍历字符串
        for(int i=0; i<s.size(); i++)
        {
            // 如果当前字符是 '?'，则进行替换
            if(s[i] == '?')
            {
                // 尝试从 'a' 到 'z' 中选择一个字符
                for(char ch = 'a'; ch <= 'z'; ch++)
                {
                    // 如果当前字符可以替换 '?'，即与前后字符不相同
                    if((i == 0 || ch != s[i-1]) && (i == s.size()-1 || ch != s[i+1]))
                    {
                        s[i] = ch;  // 替换字符
                        break;  // 一旦找到合适的字符，跳出循环
                    }
                }
            }
        }
        return s;  // 返回修改后的字符串
    }
};

2.2.1 逐行分析

1. for(int i = 0; i < s.size(); i++)：
   • 遍历字符串 s 的每个字符。
2. if(s[i] == '?')：
   • 如果当前字符是 '?'，则需要进行替换操作。
3. for(char ch = 'a'; ch <= 'z'; ch++)：
   • 从字母 'a' 到 'z' 中尝试每一个字母。
4. if((i == 0 || ch != s[i-1]) && (i == s.size()-1 || ch != s[i+1]))：
   • 判断当前字母 ch 是否与相邻的字符重复：
     • i == 0：如果当前字符是字符串的第一个字符，它只需要与后一个字符不相同。
     • i == s.size() - 1：如果当前字符是字符串的最后一个字符，它只需要与前一个字符不相同。
     • 如果是中间位置，ch 需要与前后字符都不相同。
5. s[i] = ch;：
   • 找到一个合适的字母后，替换当前的 '?'。
6. break;：
   • 一旦找到合适的字母并替换，就跳出内层的 for 循环，继续处理下一个 '?'。
7. return s;：
   • 遍历结束后，返回修改后的字符串。

2.3 多种解法

2.3.1 解法 2：使用替换字符集（环状数组）

思路： 另一种优化的思路是使用一个字符集 {'a', 'b', 'c'} 来替代 '?'，只需要考虑三个字母就足够。因为只有三个字母，它们中任何一个都可以在符合条件的情况下替换 '?'。

步骤：

1. 遍历字符串，遇到 '?' 时，选择一个字母来替换。
2. 选择的字母需与前后字符不同，如果只有三个字母可以选择，按照顺序依次替换。

代码实现：

class Solution {
public:
    string modifyString(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                for (char ch : {'a', 'b', 'c'}) {  // 只用 'a', 'b', 'c'
                    if ((i == 0 || ch != s[i-1]) && (i == s.size() - 1 || ch != s[i+1])) {
                        s[i] = ch;
                        break; // 找到合适的字符后退出循环
                    }
                }
            }
        }
        return s;
    }
};

时间复杂度：

• 外层循环遍历字符串，时间复杂度为 O(n)。
• 内层循环只遍历三个字符，时间复杂度为常数 O(1)。

总体时间复杂度： O(n)。

2.3.2 解法 3：一次遍历，动态选择字符

思路： 我们可以直接在遍历的过程中动态选择合适的字符来替换 '?'，而不需要内部循环遍历所有字母。这个解法避免了重复遍历字母，减少了计算量。

步骤：

1. 遍历字符串。
2. 当遇到 '?' 时，检查其前后的字符，并选择一个与前后字符都不相同的字母进行替换。

代码实现：

class Solution {
public:
    string modifyString(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                // 判断当前 '?' 前后的字符
                char prev = (i == 0) ? 0 : s[i-1];
                char next = (i == s.size() - 1) ? 0 : s[i+1];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    // 找一个既不与前一个字符重复也不与后一个字符重复的字母
                    if (ch != prev && ch != next) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

时间复杂度：

• 外层循环遍历字符串，时间复杂度为 O(n)。
• 内层循环最多遍历26个字母，时间复杂度为常数 O(1)。

总体时间复杂度： O(n)。

2.3.3 解法 4：预先生成不重复字符的列表

思路： 通过预先生成一个不重复的字符列表，然后根据条件动态选择下一个字符。这个方法的好处是避免了在每次遇到 '?' 时都进行字母检查。

步骤：

1. 预先生成一个没有重复字符的字母表，如 {'a', 'b', 'c'}。
2. 遍历字符串，遇到 '?' 时，根据前后字符选一个合适的字母进行替换。

代码实现：

class Solution {
public:
    string modifyString(string s) {
        vector<char> available = {'a', 'b', 'c'};
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                for (char ch : available) {
                    if ((i == 0 || ch != s[i-1]) && (i == s.size()-1 || ch != s[i+1])) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

时间复杂度：

• 外层循环遍历字符串，时间复杂度为 O(n)。
• 内层循环遍历三个字符，时间复杂度为 O(1)。

总体时间复杂度： O(n)。

2.3.4 总结

这四种解法的时间复杂度和空间复杂度基本相同，都是 O(n) 和 O(1)。主要的差异在于内部选择字符的策略和细节上的实现。最重要的是，所有解法都依赖于贪心策略，确保每个 '?' 字符替换为一个与邻近字符不同的字母。

2.4 复杂度分析

2.4.1 时间复杂度

• 外层循环：遍历字符串 s，时间复杂度为 O(n)，其中 n 是字符串的长度。
• 内层循环：对于每个 '?'，我们最多尝试26个字母。因此内层循环的时间复杂度为 O(26)，即常数时间 O(1)。
• 总体时间复杂度：综合来看，时间复杂度为 O(n)，因为内层循环的次数是常数。

2.4.2 空间复杂度

• 只使用了常数的额外空间来存储字符和索引变量。因此，空间复杂度为 O(1)。

2.5 总结

该算法通过遍历字符串并尝试替换每个 '?' 字符，确保替换后的字符不与相邻字符相同。它的时间复杂度为 O(n)，空间复杂度为 O(1)，是一种高效的解决方案。

3. 题目2：提莫攻击

题目链接：495. 提莫攻击 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

1. 基本理解：
   • 每个时间点毒药释放后，持续 duration 时间。
   • 如果下一个毒药释放的时间与当前时间点的毒药释放时间的间隔小于 duration，那么毒药的持续时间会部分重叠，重叠部分不重复计算。
   • 如果间隔大于或等于 duration，则没有重叠，应该完全计算毒药的持续时间。
2. 基本步骤：
   • 遍历 timeSeries 数组中的每个时间点，计算每两个连续时间点之间的时间差。
   • 如果时间差大于等于 duration，则毒药的持续时间不会重叠，应该加上 duration。
   • 如果时间差小于 duration，则只有部分时间是新的持续时间，应该加上时间差。
   • 最后，单独计算最后一个释放毒药的持续时间，它总是 duration。

3.2 代码分析

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();  // 获取时间序列的长度
        int ret = 0;  // 结果变量，用来累加毒药的持续时间

        for (int i = 0; i < n - 1; i++) {  // 遍历时间序列，直到倒数第二个元素
            // 如果下一个释放时间与当前释放时间的间隔大于等于 duration
            if (timeSeries[i + 1] - timeSeries[i] >= duration) {
                ret += duration;  // 没有重叠，累加整个 duration
            } else {
                // 否则，间隔小于 duration，累加两次释放之间的间隔
                ret += timeSeries[i + 1] - timeSeries[i];
            }
        }

        // 最后一次释放毒药的持续时间
        ret += duration;

        return ret;
    }
};

3.2.1 关键点解析

1. 遍历 timeSeries 数组：
   • 我们需要遍历 timeSeries 中的每个时间点，除了最后一个时间点。每次释放毒药都会持续 duration 时间，除非后续释放的毒药与当前的释放时间有重叠。
2. 计算时间差：
   • 对于每一对相邻的时间点 timeSeries[i] 和 timeSeries[i + 1]，我们计算它们之间的时间差：
     • 如果时间差大于等于 duration，说明两次释放毒药没有重叠，所以当前毒药持续的时间是 duration，我们将其加到总时间中。
     • 如果时间差小于 duration，说明两次释放的毒药存在部分重叠，因此我们只能加上时间差，即毒药的持续时间为 timeSeries[i + 1] - timeSeries[i]。
3. 最后一次持续时间：
   • 最后的 ret += duration; 确保了最后一次释放的毒药持续时间被正确计算。
4. 返回结果：
   • 最终返回的 ret 就是所有毒药持续时间的总和。

3.3 多种解法

3.4.1 方法 2：贪心法

1. 基本思路：
   • 每次 Teemo 释放毒药时，如果下一次释放毒药的时间晚于当前毒药的持续时间，我们就加上 duration。
   • 如果下次释放毒药的时间点比当前毒药的持续时间更近（即它发生在当前毒药持续时间内），则只计算时间差。
2. 详细步骤：
   • 遍历 timeSeries 数组：
     • 如果当前释放和下次释放之间有足够的间隔（即时间差大于或等于 duration），则毒药持续时间是 duration。
     • 否则，毒药持续时间是两个释放点之间的时间差。
   • 最后，单独处理最后一次释放的毒药，它的持续时间一定是 duration。

代码实现：

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        int ret = 0;

        for (int i = 0; i < n - 1; i++) {
            // 如果当前释放时间和下次释放时间的间隔大于等于duration
            if (timeSeries[i + 1] - timeSeries[i] >= duration) {
                ret += duration;
            } else {
                // 如果下次释放时间早于当前毒药的持续时间，则加上间隔时间
                ret += timeSeries[i + 1] - timeSeries[i];
            }
        }

        // 最后一次释放的毒药持续duration
        if (n > 0) {
            ret += duration;
        }

        return ret;
    }
};

时间复杂度：

• 时间复杂度：O(n)，其中 n 是 timeSeries 数组的长度。我们只遍历了一次 timeSeries 数组。
• 空间复杂度：O(1)，我们只用了几个常数空间。

3.4.2 方法 3：优化模拟法 (对比方法 1)

1. 思路：
   • 实际上，在方法 1 中已经有了一个贪心策略来检查时间差，方法 2 的模拟方法会比方法 1 稍微多做一些无意义的操作（创建和更新poisoned数组）。但总体效率是相同的。
2. 对于时间重叠问题：
   • 方法 1 通过一次遍历直接判断是否有重叠部分，效率较高。
   • 方法 2 用了额外的 poisoned 数组，虽然能清晰模拟过程，但开销较大，特别是当时间序列的时间跨度很大时。

3.4.3 总结

• 方法 1 是最常用的贪心算法，它的时间复杂度是 O(n)，并且没有额外的空间开销，因此是最优解。
• 方法 2 是一种更直观的模拟方法，通过标记每个时刻是否中毒来计算毒药的持续时间，时间复杂度仍然是 O(n)，但空间复杂度可能较高，不太适合大规模的输入。
• 方法 3 与方法 1 类似，实际上方法 1 已经是最优的实现。

3.4 复杂度分析

3.4.1 时间复杂度

• 我们遍历一次 timeSeries 数组，因此时间复杂度为 O(n)，其中 n 是 timeSeries 数组的长度。
• 每次操作（时间差的计算和累加）是常数时间操作。

3.4.2 空间复杂度

• 只使用了几个常数级别的变量，空间复杂度为 O(1)。

3.5 总结

该算法通过遍历 timeSeries 数组并计算相邻时间点的时间差，确保了正确地计算每次毒药释放的持续时间。对于不重叠的部分，完全加上 duration，对于重叠部分，计算实际的时间差。最后，单独加上最后一次释放毒药的持续时间。

4. 解法总结：

1. 贪心法（推荐）：
   • 遍历 timeSeries 数组，计算每两个释放时刻之间的时间差。
   • 如果时间差大于或等于 duration，则毒药的持续时间为 duration。
   • 如果时间差小于 duration，则毒药的持续时间为时间差。
   • 最后，单独计算最后一次释放的毒药持续时间。
   • 时间复杂度：O(n)，其中 n 是 timeSeries 数组的长度。
   • 空间复杂度：O(1)，只用了常数空间。
2. 模拟法（不推荐）：
   • 创建一个布尔数组 poisoned 标记每个时刻是否中毒。
   • 对每次释放毒药，标记其持续的时间范围。
   • 最后计算中毒的总时长。
   • 时间复杂度：O(n)，但空间复杂度较高，O(m)，其中 m 是时间跨度。

总结：

• 贪心法是最优解，时间复杂度为 O(n)，且空间复杂度为 O(1)，效率高且简洁。

5. 最后

过上面几个例题，如「Teemo Attacking」问题的多种解法、毒药持续时间的计算方法，我们总结出贪心算法在处理时间重叠和区间问题中的高效应用。 贪心算法通过局部最优选择（如判断时间差、间隔计算等）来实现全局最优解，在解决连续区间、时间重叠、资源分配等问题时展现出了简洁和高效的特性。 在处理 区间重叠问题、最大化资源利用 以及 高效求解时间持续问题 等场景时，贪心算法可以显著简化问题求解的复杂度，尤其适用于 时间复杂度敏感 和 大数据规模 的应用场景。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！