【优选算法篇】从蒙特卡洛到模拟退火：探秘模拟算法的不同面貌（下篇）

熬夜学编程的小王

发布于 2024-12-24 10:21:07

5260

须知

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

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

引言：通过上篇文章带大家简单了解“位运算算法”，小试牛刀。接下来将让大家感受一下位运算在解题的妙处。

位运算在计算机内存中的重要性体现在以下几个方面：

高效性：位运算直接操作二进制位，速度极快，通常比常规的算术运算（如加减乘除）要快，适用于性能要求高的场景。
内存节省：位运算能有效地处理多个布尔值（如状态标志、开关等）并将它们压缩到一个字节或更小的存储单元中，从而节省内存空间，尤其适用于大规模数据处理。
低级操作：位运算可以直接操作计算机内存的底层数据结构，如位图、位域等，在实现诸如哈希表、图像处理、网络协议等高效算法时不可或缺。
简洁性：许多常见问题（如判断奇偶、交换变量、清除最低有效位、位图操作等）通过位运算可以用简洁的代码解决，增强代码的可读性和维护性。

总结： 位运算在计算机内存中扮演着至关重要的角色，它以其高效、节省内存和低级操作的优势，广泛应用于性能优化、算法设计和系统开发等多个领域。

"模拟算法：从基础到高级场景的全面解析"

1. C++ 模拟算法进阶详解

1.1 什么是模拟？

模拟（Simulation）是指通过数学模型或计算机程序模拟现实世界中的系统或过程，以便研究、分析和预测其行为。模拟通常用于解决无法直接实验或操作的情况，或是当直接实验的成本过高、危险或不可行时。

模拟的核心概念是通过近似或简化真实世界的复杂性，使得我们能够理解和预测系统的行为。模拟不仅可以用于科学研究，还广泛应用于工程、经济、军事、医学等领域。

1.2 经典应用

飞行模拟：飞行模拟器广泛应用于航空训练，帮助飞行员在没有实际飞行的情况下进行操作训练。飞行模拟器能够模拟不同的飞行环境、气候条件和紧急情况，提供安全且高效的训练方式。
汽车碰撞模拟：汽车行业常用模拟技术来测试车辆在碰撞时的表现。通过模拟碰撞过程，工程师可以评估车辆的安全性并改进设计，减少伤害风险。
天气预测：气象学家利用模拟技术，结合历史数据和气候模型，预测天气变化。天气模拟不仅能帮助预报日常天气，还能对极端天气事件进行预测，如台风、暴雨等。
战争模拟与军事训练：模拟在军事训练中具有重要作用。通过模拟战斗场景、战术决策和敌对行动，军队可以在不实际投入战争的情况下进行演练、分析战略和提高指挥官的决策能力。
经济模型模拟：经济学家使用计算机模拟来预测市场、金融系统或宏观经济政策的结果。例如，模拟股市、货币政策或财政政策的影响，以便为政府和企业提供决策支持。
医学模拟：医学领域中，通过模拟手术、药物反应或患者病情，医生能够提前进行练习，减少实际操作中的风险。模拟还用于医学影像的诊断，如CT扫描、MRI模拟等。
制造与产品设计：在制造业，模拟技术被用于产品设计和生产过程优化。例如，使用计算机辅助设计（CAD）软件模拟产品在生产中的表现，减少设计错误和生产浪费。

总结

模拟通过创建现实世界的模型，使我们能够在不实际实验的情况下，分析系统的行为、预测结果和优化决策。其应用跨越了多个领域，尤其在高风险、高成本或难以实验的场景中，模拟技术提供了有效的解决方案。

2. 题目1：Z字形变换

题目链接：6. Z 字形变换 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

解题思路:

特殊情况：如果 numRows 小于 2，意味着我们不需要“Z字形”排列，只需要返回原始字符串。
行数定义：创建一个包含 numRows 个字符串的容器 rows，用于存储每一行的字符。
遍历字符串：用一个指针 i 来指示当前字符应放入哪一行。遍历字符串时：
- 当 i == 0 或 i == numRows - 1 时，改变方向，即斜线的上下方向反转。
- flag 控制行指针的增减，当 flag == 1 时，i 增加，表示从上到下放置字符；当 flag == -1 时，i 减小，表示从下到上放置字符。
拼接结果：遍历所有行的字符并拼接起来，最终得到转换后的字符串。

2.2 代码实现：

class Solution {
public:
    string convert(string s, int numRows) {
        // 特殊情况处理：如果 numRows < 2，不需要变换
        if (numRows < 2)
            return s;

        // 创建一个vector，用于保存每一行的字符串
        vector<string> rows(numRows);

        // 记录当前行数和方向（flag控制行数的增加或减少）
        int i = 0, flag = -1;

        // 遍历字符串s，将字符按Z字形分布到rows中
        for (char c : s) {
            rows[i].push_back(c);
            
            // 如果i在第一行或者最后一行，改变方向
            if (i == 0 || i == numRows - 1)
                flag = -flag;
            
            // 更新i的值
            i += flag;
        }

        // 拼接所有行中的字符，形成结果字符串
        string res;
        for (const string &row : rows)
            res += row;

        return res;
    }
};

2.2.1 详细解析:

创建一个容器 rows：
- 这个容器包含 numRows 个字符串，用于存储每一行的字符。根据 numRows 的不同，每一行存储的字符数量不同。
遍历字符串 s：
- 使用一个变量 i 表示当前字符应该被放入的行。我们首先将 i 设置为 0，表示从第 1 行开始。
- 使用一个标志变量 flag 来表示方向，当 i == 0 或 i == numRows - 1 时，我们会反转 flag 的值，这决定了下一个字符应该放在上行还是下行。
处理 Z 字形：
- 字符依次放入每一行，但并不是简单的逐行从上到下排列，而是交替从上往下放置，再从下往上放置，形成Z字形排列。
拼接每一行：
- 最终，将所有的行拼接成一个结果字符串返回。

2.3 多种解法

2.3.1 解法 2：模拟法（按位置模拟）

这种解法的关键在于理解每个字符在Z字形排列中的具体位置。通过计算每个字符的垂直位置和水平位置，可以直接确定每个字符放入的位置。

首先，确定字符在Z字形排列中属于哪一行。
然后，根据Z字形的规律计算字符的水平位置。

具体实现：

在这种解法中，我们模拟一个二维的网格。首先按顺序将字符填入网格的每一行，再通过这种方式生成结果字符串。

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;  // 特殊情况，只有一行，直接返回原字符串
        
        int n = s.size();
        vector<string> rows(min(numRows, n));  // 最多有n行，最少有1行
        int currentRow = 0;
        bool goingDown = false;
        
        for (int i = 0; i < n; ++i) {
            rows[currentRow] += s[i];
            // 如果当前行是最上面或最下面的行，改变方向
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            // 更新当前行的索引
            currentRow += goingDown ? 1 : -1;
        }
        
        string result;
        for (const string& row : rows) {
            result += row;  // 将每行拼接成最终结果
        }
        
        return result;
    }
};

时间复杂度：O(n)

与上一种方法相同，时间复杂度为O(n)，因为我们遍历一次字符串。

空间复杂度：O(n)

需要一个额外的 vector<string> 来存储每行的字符。

2.3.2 解法 3：按每个周期计算字符的位置

这是一种更数学化的解法，我们不需要模拟行列，而是直接通过周期计算字符应该放在哪一行。

周期：Z字形的排列方式可以看成是一个周期，每个周期的长度是 (numRows - 1) * 2。
在一个周期中，第一个字符放在第一行，第二个字符放在第二行，一直到最后一行，然后再从最后一行回到第二行，依此类推。
通过这种方式，我们可以计算出每个字符的行位置。

具体实现：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || numRows >= s.size()) return s; // 特殊情况
        
        string result;
        int cycleLength = 2 * numRows - 2;  // 每个周期的长度
        
        for (int row = 0; row < numRows; ++row) {
            for (int j = 0; j + row < s.size(); j += cycleLength) {
                result += s[j + row];  // 竖直方向
                // 处理斜线部分（在每个周期的中间）
                if (row != 0 && row != numRows - 1 && j + cycleLength - row < s.size()) {
                    result += s[j + cycleLength - row];  // 斜线方向
                }
            }
        }
        
        return result;
    }
};

时间复杂度：O(n)

通过直接计算每个字符的位置，不需要重复扫描字符串，因此时间复杂度为O(n)。

空间复杂度：O(n)

与前两种方法一样，我们需要O(n)的额外空间来存储结果字符串。

2.3.3 总结

模拟法（逐行模拟）是最直观的方法，通过遍历字符串并动态管理每一行的字符位置来实现Z字形排列。
按周期计算法是一种更加优化的数学方法，不需要显式地模拟二维网格，而是直接通过周期规律推算字符的位置，适用于更大的输入数据。
这三种方法的时间复杂度均为O(n)，空间复杂度均为O(n)，但不同方法适用于不同的场景和理解深度。

2.4 算法时间复杂度：

时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们遍历了一遍字符串，并在每次迭代时将字符添加到相应的行。
空间复杂度：O(n)，用于存储每行字符的 rows 数组，最多需要存储整个字符串的字符。

2.5 总结：

该算法通过模拟Z字形的行列排布，利用简单的行指针控制和方向标志，可以高效地将字符串按Z字形转换。

3. 题目2：外观数列

题目链接：38. 外观数列 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

初始化：
- 初始时，第一个数字为 "1"，即 ret = "1"。
生成报数序列：
- 从第2项开始，依次通过描述前一项来生成下一项。
- 对于每一项，将连续的相同字符分组，描述这些字符的个数和字符值，生成新的字符串。
- 通过一个内部循环遍历当前字符串，统计每个字符的连续重复次数，并生成新的描述字符串。
描述规则：
- 从当前字符串 ret 中取出一组连续的相同字符，统计其数量（例如，"111" 说明出现了 3 个字符 1），然后将其描述为 3 个字符 1，即 "31"。
- 对于整个字符串，逐个字符地进行这个描述，直到字符串的所有字符都被描述完。
迭代：
- 重复以上步骤 n-1 次，每次生成新的字符串 ret。

3.2 代码实现解析：

class Solution 
{
public:
    string countAndSay(int n) 
    {
        string ret = "1";  // 初始化第一个元素

        // 生成第2到第n项
        for (int i = 1; i < n; i++) {
            string tmp;  // 存储新的字符串
            int len = ret.size();
            
            // 遍历当前字符串
            for (int left = 0, right = 0; right < len;) {
                // 统计当前字符的连续数量
                while (ret[left] == ret[right]) right++;
                
                // 将描述的字符和数量添加到tmp中
                tmp += to_string(right - left) + ret[left];
                
                // 更新left和right，跳到下一组连续字符
                left = right;
            }
            ret = tmp;  // 更新当前字符串
        }
        
        return ret;  // 返回最终的第n项
    }
};

3.2.1 详细解析：

初始化：
- 初始时，ret = "1"，这是报数序列的第一个项。
生成报数序列：
- 外部循环 for (int i = 1; i < n; i++) 迭代 n-1 次，每次根据前一项生成当前项。
- 在每次循环中，初始化一个空字符串 tmp 来存储新的描述结果。
内部循环：
- 内部循环 for (int left = 0, right = 0; right < len; ) 用于遍历当前字符串 ret，通过两个指针 left 和 right 来统计相同字符的连续长度。
- 内部的 while (ret[left] == ret[right]) right++ 用来扩展 right，直到字符不相同为止，这样就能够计算出相同字符的个数（即 right - left）。
- 然后，将该数字和字符（例如 "31" 表示连续 3 个字符 1）加入到 tmp 中。
更新：
- 一旦当前组的字符计数和描述完成，就更新 left 为 right，即跳到下一个新的字符组。
返回结果：
- 最终，ret 就包含了第 n 项的报数序列，返回该结果。

3.3 多种解法

3.3.1 解法2：递归法

递归法的思路是将第 n 项转换为一个递归问题。首先定义递归函数 generate(n)，它的任务是根据输入的 n 返回第 n 项。可以通过递归的方式，逐步向下计算，直到计算到第1项为止。

核心思想：

对于每一项，递归地计算上一项的描述。
基本情况是第1项是 "1"。

class Solution 
{
public:
    string countAndSay(int n) 
    {
        if (n == 1) return "1"; // 基本情况
        string prev = countAndSay(n - 1);  // 递归计算第 n-1 项
        string result = "";
        int len = prev.size();
        
        for (int i = 0; i < len;) {
            int count = 1;
            while (i + 1 < len && prev[i] == prev[i + 1]) {
                i++;
                count++;
            }
            result += to_string(count) + prev[i];
            i++;
        }
        
        return result;
    }
};

时间复杂度：

时间复杂度：O(K * n)，其中 K 是第 n 项的长度，n 是项的编号。与模拟法类似，递归过程也会根据字符串的长度进行递归调用。
空间复杂度：O(K)，主要由递归栈的深度和生成字符串的空间构成。

3.3.2 解法3：迭代法（优化的模拟法）

虽然模拟法是最直观的方法，但有时我们可以通过更加优化的方式，减少不必要的操作和内存分配。比如，在每次生成新的字符串时，直接修改原始字符串而不是生成新字符串，从而减少内存的使用。

class Solution 
{
public:
    string countAndSay(int n) 
    {
        string result = "1";
        
        for (int i = 1; i < n; i++) {
            string temp = "";
            int len = result.size();
            for (int j = 0; j < len;) {
                int count = 1;
                while (j + 1 < len && result[j] == result[j + 1]) {
                    j++;
                    count++;
                }
                temp += to_string(count) + result[j];
                j++;
            }
            result = temp;
        }
        
        return result;
    }
};

时间复杂度：

时间复杂度：O(K * n)，与模拟法和递归法相同。每次生成当前项的时间与该项的长度成正比。
空间复杂度：O(K)，其中 K 是第 n 项的长度。

3.3.3 解法4：数学法（直接计算）

数学法通过推导出每一项的规律，直接构造每一项。虽然直接用数学方法进行描述看似简便，但由于报数序列的生成遵循一定的模式，依然无法避免对字符串的逐个字符操作。因此，这种方法不常见。

class Solution {
public:
    string countAndSay(int n) {
        vector<string> arr = 
        {
/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* "","1","11","21","1211","111221","312211","13112221","1113213211","31131211131221","13211311123113112211","11131221133112132113212221","3113112221232112111312211312113211","1321132132111213122112311311222113111221131221","11131221131211131231121113112221121321132132211331222113112211","311311222113111231131112132112311321322112111312211312111322212311322113212221","132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211","11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221","31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211","1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221","11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211","311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221","132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211","111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221","3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211","132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221","1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211","31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221","13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211","11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221","3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211"
*/
        };
        return arr[n];        
    }
};

3.3.4 总结：

模拟法（逐项描述）：通过遍历每一项并描述相同字符的个数生成下一项，直观但效率较低。
递归法：通过递归计算上一项的描述，直观且简洁，但可能会遇到递归深度限制问题。
优化的迭代法：对模拟法进行了优化，减少了多次内存分配，性能较好。
数学法：虽然存在，但不常见，因为直接计算规律较为复杂，且仍需要遍历字符串。

3.4 复杂度分析

时间复杂度：

时间复杂度：O(K * n)，其中 n 是输入的项数，K 是生成第 n 项所需的字符串长度。具体来说，K 与 n 有关，第 n 项的长度在理论上呈指数增长。
- 每次生成新项的时间复杂度与当前项的长度成正比，因此对于每次迭代，处理的时间复杂度是当前项的长度。
- 总体时间复杂度是 O(K * n)，其中 K 随着 n 的增加而增长。
空间复杂度：O(K)，其中 K 是第 n 项的长度。每次迭代中，tmp 和 ret 都是长度为 K 的字符串，因此空间复杂度为 O(K)。

3.5 总结：

该算法通过每次描述前一项来生成新的项，使用双指针（left 和 right）来计算相同字符的连续数量，并生成新的描述字符串。每次生成新的项时，复杂度会根据当前项的长度增加，因此随着 n 的增加，算法的时间复杂度和空间复杂度呈现一定的增长。

4. 题目3：数青蛙

题目链接：1419. 数青蛙 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

状态模拟：
- 每个青蛙的发音过程是按顺序进行的：'c' -> 'r' -> 'o' -> 'a' -> 'k'。
- 通过一个数组 hash 来记录当前正在发出每个字符的青蛙数量。这个数组有五个元素，分别代表 'c'、'r'、'o'、'a' 和 'k'。
字符顺序控制：
- 我们首先要确保每个字符是按照正确的顺序出现的。例如，'r' 只能在 'c' 之后出现，'o' 只能在 'r' 之后出现，依此类推。
- 当我们遍历字符串 croakOfFrogs 时，我们需要对每个字符进行处理。如果遇到 'c'，说明这是新一轮青蛙开始发音的开始，因此我们增加 'c' 的数量；如果遇到其他字符，如 'r'，则必须确保对应的前一个字符已经发音过（即之前的 'c' 必须已经出现过），如果没有，则返回 -1。
最终判断：
- 在遍历完成之后，我们检查 hash 数组。如果 hash[i] 中有未被处理完的青蛙（例如，'c' 还没有完全发音），则返回 -1。
- 最终返回 hash[n-1]，即 'k' 的数量，表示完整的“croak”序列的个数。

4.2 代码实现：

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n, 0); // 用数组来模拟哈希表，记录每个字符的青蛙数量
        unordered_map<char, int> index; // 字符对应的索引
        for(int i = 0; i < n; i++) 
            index[t[i]] = i; // 初始化字符到索引的映射
        
        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                // 如果当前是 'c'，且 'k' 还有未发完的（即已经有一个完整的"croak"），
                // 则说明需要重新开始新的一轮 'croak'
                if(hash[n - 1] != 0) 
                    hash[n - 1]--; // 表示有 'k' 完成，应该减少这个字符的计数
                hash[0]++; // 增加一个新的 'c'，开始新一轮
            }
            else
            {
                int i = index[ch]; // 找到当前字符的索引
                if(hash[i - 1] == 0) 
                    return -1; // 如果前一个字符的青蛙还没发出，说明不能继续发出当前字符
                hash[i - 1]--; // 前一个字符已经处理，减少它的计数
                hash[i]++; // 当前字符计数加1
            }
        }
        
        // 检查是否所有 'croak' 都是有效的
        for(int i = 0; i < n - 1; i++)
            if(hash[i] != 0)
                return -1; // 如果有中途未发完的青蛙，则返回 -1
        
        return hash[n - 1]; // 返回最后一个字符 'k' 的数量，即为完整 "croak" 的个数
    }
};

4.2.1 算法解析：

字符映射：
- unordered_map<char, int> index 用于记录字符 'c'、'r'、'o'、'a'、'k' 在字符串 "croak" 中的索引位置。通过该映射，可以快速查找每个字符在“croak”中的位置。
遍历字符串：
- 我们遍历输入的字符串 croakOfFrogs，对于每个字符执行以下操作：
  - 遇到 'c'：如果当前有未完成的 'k'，即之前的“croak”已经完成，减少 'k' 的数量，然后新增一个 'c' 来开始新的青蛙。
  - 遇到其他字符（'r'、'o'、'a'、'k'）：我们检查前一个字符是否已经处理过（例如，'r' 必须在 'c' 之后，'o' 必须在 'r' 之后，依此类推）。如果前一个字符的数量为 0，说明当前字符不能被处理，返回 -1。
最终验证：
- 遍历结束后，检查 hash 数组。如果某个字符的数量不为零，说明有青蛙没有完成报数，返回 -1。
- 最终返回 'k' 的数量，它代表了完整“croak”序列的个数。

4.3 多种解法

4.3.1 解法2：计数法

这个解法的思路是通过维护五个字符的计数来直接计算最少需要的青蛙数量。通过统计每个字符出现的次数，确保它们能按正确顺序发音。

核心思路：

使用一个 hash 数组记录每个字符的数量，分别是 'c'、'r'、'o'、'a'、'k' 的计数。
需要保证每个字符在正确的顺序出现（例如，'r' 必须在 'c' 后面，'o' 必须在 'r' 后面，依此类推）。
通过检查字符顺序，及时更新计数，并找出需要的最少青蛙数量。

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        vector<int> count(5, 0); // 记录五个字符的计数
        unordered_map<char, int> charToIndex{{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};
        int frogs = 0; // 当前最少青蛙数量
        
        for (char c : croakOfFrogs)
        {
            int idx = charToIndex[c];
            
            if (idx == 0) 
                count[0]++; // 'c' 表示新一轮青蛙开始
            else 
            {
                if (count[idx - 1] == 0) 
                    return -1; // 如果前一个字符没有青蛙在发音，则返回 -1
                count[idx - 1]--;
                count[idx]++;
            }
            
            // 更新最少的青蛙数
            frogs = max(frogs, count[4]); // 'k' 的数量就是完成的青蛙数量
        }
        
        // 确保所有青蛙都发完 'k'
        for (int i = 0; i < 4; ++i)
            if (count[i] != 0) 
                return -1;
        
        return frogs; // 返回最少的青蛙数量
    }
};

时间复杂度：

时间复杂度：O(N)，其中 N 是字符串 croakOfFrogs 的长度。
空间复杂度：O(1)，因为我们使用了一个固定大小的 count 数组，空间复杂度是常数。

4.3.2 解法3：队列模拟法

通过队列来模拟每只青蛙发出“croak”时的状态。队列中的每个元素表示一个正在发出声音的青蛙的状态（即当前青蛙发出字符的位置）。

核心思路：

用队列来表示每个青蛙正在发出的字符。
每次从队列中取出一个青蛙，更新它当前的发音状态。
如果一个青蛙完成了“croak”，将其从队列中移除。

代码实现：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        // 定义字符对应的顺序
        unordered_map<char, int> charOrder = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};
        
        // 初始化计数器，记录每个字符当前有多少青蛙在发出
        vector<int> count(5, 0);
        
        // 队列模拟
        queue<int> q; // 用队列存储当前正在发出字符的青蛙
        
        int frogCount = 0; // 用来记录青蛙的数量
        
        for (char c : croakOfFrogs) {
            int index = charOrder[c]; // 获取当前字符的顺序

            // 如果是 'c'，表示开始新的一轮，直接加到队列中
            if (index == 0) {
                q.push(index); 
                count[index]++; // 新的青蛙开始发音
            } else {
                // 对于非 'c'，需要检查前一个字符是否已经发音过
                if (q.empty() || count[index - 1] == 0) {
                    return -1; // 如果前一个字符没有青蛙在发音，则无法继续
                }

                // 前一个字符发音完毕，当前字符也开始发音
                count[index - 1]--;
                count[index]++;
                q.push(index);
            }

            // 更新最少青蛙数量
            frogCount = max(frogCount, (int)q.size());
        }

        // 检查是否所有青蛙都发完了 'k'，即每个青蛙必须完全发出 "croak"
        for (int i = 0; i < 4; i++) {
            if (count[i] != 0) {
                return -1; // 如果某个字符没有发完，返回 -1
            }
        }

        return frogCount;
    }
};

4.3.3 总结：

模拟法：通过模拟“青蛙”发音的过程，逐个字符地记录青蛙的状态，确保字符按顺序发音，最终计算最少青蛙数。
计数法：维护一个计数数组，直接统计每个字符的数量，确保字符顺序和数量的正确性。
队列模拟法：通过队列模拟每只青蛙发出声音的过程，逐步更新每个青蛙的状态。

4.4 复杂度分析

时间复杂度：O(N)，其中 N 是输入字符串 croakOfFrogs 的长度。我们只遍历一次字符串，并在每次处理字符时执行常数时间的操作（查找、更新计数等）。
空间复杂度：O(1)，因为 hash 数组的大小固定为 5（表示字符 'c'、'r'、'o'、'a'、'k'），且 index 哈希表也仅包含 5 个字符的映射，因此空间复杂度是常数。

4.5 总结：

这个问题的关键是通过模拟“青蛙”发音的过程，确保字符按正确顺序出现。使用 hash 数组来模拟五个字符的数量状态，并通过检查前一个字符是否发音完成来保证正确的顺序。最终返回的是青蛙同时发出完整“croak”序列的最小数量。

5. 总结

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-19，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历