【优选算法篇】算法江湖中的碎玉拾光——C++模拟题全解，踏步逐章细细品味

C++ 模拟题详解：基础题解与细致分析

💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。 👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！ 🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习字符串操作和模拟题解！

前言

在算法学习中，模拟题往往以其具体的操作流程和生动的应用场景为初学者提供了宝贵的实践机会。这类题型不仅帮助我们理解代码的执行过程，还培养了我们对逻辑思维和代码组织的敏锐感。本篇文章将从一道经典的 C++ 模拟题“替换所有问号”出发，带你逐步解析如何在字符操作和条件约束中找到最佳的解决方案，帮助你打好算法学习的基础。

第一章：基础练习

1.1 替换所有的问号（easy）

题目链接：1576. 替换所有的问号

题目描述：

给定一个仅包含小写英文字母和 ? 字符的字符串 s，请将所有的 ? 转换为若干小写字母，使得最终的字符串不包含任何连续重复的字符。 注意：你不能修改非 ? 字符。题目保证除了 ? 字符之外，不存在连续重复的字符。 在完成所有转换（可能无需转换）后，返回最终的字符串。如果有多个解决方案，返回其中任何一个即可。

示例 1：

• 输入：s = "?zs"
• 输出："azs"
• 解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "zzs" 是无效的修改，因为包含连续重复的两个 'z'。

示例 2：

• 输入：s = "ubv?w"
• 输出："ubvaw"
• 解释：该示例共有 24 种解决方案，替换成 "v" 和 "w" 不符合题目要求，因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

• 1 <= s.length <= 100
• s 仅包含小写英文字母和 ? 字符

解法（模拟）

算法思路：

纯模拟。我们从前往后遍历整个字符串，当遇到 ? 时，用 a 到 z 的字符尝试替换，确保替换后的字符与相邻字符不重复。 具体步骤如下：

1. 遍历字符串：使用循环逐个检查字符串中的每个字符。
2. 替换问号：当遇到 ? 时，从 'a' 开始尝试替换，检查替换后的字符是否和前后字符重复。
3. 确认替换：如果字符与前后字符均不同，则进行替换并跳出循环，确保每个 ? 替换后都满足题目要求。
4. 返回结果：遍历完成后，返回修改后的字符串。

C++ 代码实现

class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for(int i = 0; i < n; i++) {
            if(s[i] == '?') {  // 发现问号，开始替换
                for(char ch = 'a'; ch <= 'z'; ch++) {
                    // 检查替换字符是否与前后字符冲突
                    if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1])) {
                        s[i] = ch;  // 替换并跳出内循环
                        break;
                    }
                }
            }
        }
        return s;
    }
};

易错点提示

1. 检查相邻字符：
   • 遍历时要特别注意边界条件，确保 i 在第一个或最后一个字符时，能够正确处理前后位置的检查。
2. 字符替换的范围：
   • 要从 'a' 开始尝试替换字符，一直到 'z'，确保字符替换的选择范围广泛。
3. 循环退出条件：
   • 内部循环使用 break，一旦找到合适的字符替换就退出，以减少不必要的循环操作。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是字符串的长度。每次遇到 ?，最多需要检查 26 个字符，但 n 较小时，这些检查可以在常数时间内完成。
• 空间复杂度：O(1)，仅使用常数空间来存储中间变量。

1.2 提莫攻击（easy）

题目链接：495. 提莫攻击

题目描述：

在《英雄联盟》的世界中，有一个叫 提莫 的英雄。他的攻击可以让敌方英雄 艾希（寒冰射手）进入中毒状态。 当提莫攻击艾希时，艾希的中毒状态会持续 duration 秒。 具体来说，提莫在 t 秒发起攻击，意味着艾希在时间区间 [t, t + duration - 1] 内（包含 t 和 t + duration - 1）处于中毒状态。如果提莫在之前的中毒影响结束前再次攻击，则中毒状态计时器会重置，中毒影响将在新的攻击后 duration 秒后结束。

给定一个非递减的整数数组 timeSeries，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，和一个表示中毒持续时间的整数 duration。 返回艾希处于中毒状态的总秒数。

示例 1：

• 输入：timeSeries = [1,4], duration = 2
• 输出：4
• 解释：
  • 第 1 秒，提莫攻击艾希并使其立即中毒，中毒状态持续 2 秒，即第 1 秒和第 2 秒。
  • 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
  • 艾希在第 1, 2, 4, 5 秒处于中毒状态，总中毒秒数为 4。

示例 2：

• 输入：timeSeries = [1,2], duration = 2
• 输出：3
• 解释：
  • 第 1 秒，提莫攻击艾希并使其立即中毒，中毒状态持续 2 秒，即第 1 秒和第 2 秒。
  • 第 2 秒，提莫再次攻击艾希，重置中毒计时器，中毒状态持续到第 2 秒和第 3 秒。
  • 艾希在第 1, 2, 3 秒处于中毒状态，总中毒秒数为 3。

提示：

• 1 <= timeSeries.length <= 10^4
• 0 <= timeSeries[i], duration <= 10^7
• timeSeries 按非递减顺序排列

解法（模拟 + 分情况讨论）

算法思路：

采用模拟和分情况讨论的方法，通过计算相邻两个时间点的差值，确定中毒状态的持续时间：

1. 相邻时间点差值计算：
   • 如果差值大于或等于中毒时间：说明上次中毒可以持续 duration 秒。
   • 如果差值小于中毒时间：那么上次的中毒只能持续 差值 秒（因为下一次攻击提前发生）。
2. 结果累加：循环处理每一次攻击的影响时间，最后加上最后一次攻击的 duration，即可得到总的中毒时间。

C++ 代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ret = 0;
        for(int i = 1; i < timeSeries.size(); i++) {
            int tmp = timeSeries[i] - timeSeries[i - 1];
            if(tmp >= duration) 
                ret += duration;
            else 
                ret += tmp;
        }
        return ret + duration;
    }
};

易错点提示

1. 最后一次攻击时间的处理：
   • 最后一段时间直接加上 duration，因为最后一次攻击的影响持续完整的 duration 时间。
2. 相邻攻击的差值判断：
   • 根据 tmp >= duration 和 tmp < duration 两种情况正确累加中毒时间。
3. 初始化和边界条件：
   • 确保 timeSeries 长度至少为 1；如果 timeSeries 长度为 1，直接返回 duration。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是 timeSeries 的长度，需要遍历数组一次。
• 空间复杂度：O(1)，只使用常数空间来存储结果。

1.3 N 字形变换（medium）

题目链接：6. N 字形变换

题目描述：

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。 例如，输入字符串为 "PAYPALISHIRING"，行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);

示例 1：

• 输入：s = "PAYPALISHIRING", numRows = 3
• 输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4

输出："PINALSIGYAHRPI"

解释：

P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

• 输入：s = "A", numRows = 1
• 输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、, 和 . 组成
• 1 <= numRows <= 1000

解法（模拟 + 找规律）

算法思路：

Z 字形排列的规律：字符在 numRows = 4 时的排列结构如下：

0       2row - 2     4row - 4
1     (2row - 3)   (2row - 1)   4row - 5    4row - 3
2   (2row - 4)   2row         4row - 6      4row - 2
3       2row + 1                4row - 1

不难发现，数据是以 2row - 2 为周期进行循环。每一行的字符位置都可以按特定间隔获取：

1. 第一行和最后一行形成等差数列，间隔为 2 * numRows - 2。
2. 中间行字符按两个等差数列交替出现。

C++ 代码实现

class Solution {
public:
    string convert(string s, int numRows) {
        // 处理边界情况，防止死循环
        if (numRows == 1) return s;

        string ret;
        int d = 2 * numRows - 2, n = s.size();

        // 1. 处理第一行
        for (int i = 0; i < n; i += d) {
            ret += s[i];
        }

        // 2. 处理中间行
        for (int k = 1; k < numRows - 1; k++) { // 枚举每一行
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }

        // 3. 处理最后一行
        for (int i = numRows - 1; i < n; i += d) {
            ret += s[i];
        }
        
        return ret;
    }
};

易错点提示

1. 周期 d = 2 * numRows - 2：
   • 这是 Z 字形转换的关键，表示字符在行间的周期性跳跃。
2. 中间行的交替字符：
   • 每一中间行的字符位置交替出现在两个等差数列上，位置 i = k 和 j = d - k。
3. 最后累加顺序：
   • 输出时需要按从上到下的顺序，逐行拼接。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度，每个字符被遍历和拼接一次。
• 空间复杂度：O(n)，用于存储结果字符串。

1.4 外观数列（medium）

题目链接：38. 外观数列

题目描述：

给定一个正整数 n，输出外观数列的第 n 项。 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1. 1
2. 11
3. 21
4. 1211
5. 111221

说明：

• 第 1 项是数字 1
• 第 2 项描述前一项 1，即“一个 1”，记作 "11"
• 第 3 项描述前一项 11，即“两个 1”，记作 "21"
• 第 4 项描述前一项 21，即“一个 2 一个 1”，记作 "1211"
• 第 5 项描述前一项 1211，即“一个 1 一个 2 两个 1”，记作 "111221"

例如，数字字符串 “3322251” 的描述如下图：

在这里插入图片描述

示例 1：

• 输入：n = 1
• 输出："1"

示例 2：

• 输入：n = 4
• 输出："1211"

提示：

• 1 <= n <= 30

解法（模拟）

算法思路：

「外观数列」的本质是对前一项字符串中连续相同字符的计数。每一项生成下一项的步骤如下：

1. 从第 1 项的 "1" 开始，每一项的字符串通过遍历前一项字符串生成。
2. 对于每组连续相同的字符，将字符的个数和字符本身组合成新字符串，得到下一项。

C++ 代码实现

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for (int i = 1; i < n; i++) {  // 执行 n - 1 次生成第 n 项
            string tmp;
            int len = ret.size();
            for (int left = 0, right = 0; right < len;) {
                // 计算当前字符的连续段
                while (right < len && ret[left] == ret[right]) right++;
                // 拼接字符的数量和字符本身
                tmp += to_string(right - left) + ret[left];
                left = right;  // 更新 left 到新段的开始
            }
            ret = tmp;  // 将当前项更新为 ret
        }
        return ret;
    }
};

易错点提示

1. 连续字符计数的实现：
   • 在每个字符段结束时，将计数和字符追加到 tmp 中。
2. 索引更新：
   • 遍历完一个字符段后，将 left 更新为新的字符段起点 right。
3. 结果更新：
   • ret 表示当前的结果，每次生成后更新为新的项。

时间复杂度和空间复杂度

• 时间复杂度：O(n * m)，其中 n 是调用次数，m 是字符串长度（字符串随着项数增加而增大）。
• 空间复杂度：O(m)，用于临时存储字符串。

1.5 数青蛙（medium）

题目链接：1419. 数青蛙

题目描述

给定一个字符串 croakOfFrogs，表示青蛙发出的 “croak” 叫声的组合。可以有多只青蛙同时叫，因此字符串中可能会包含多个 “croak”。要求返回完成所有叫声所需的最少青蛙数量。如果字符串不是有效的 “croak” 组合，则返回 -1。

示例：

• 输入："croakcroak"，输出：1
• 输入："crcoakroak"，输出：2
• 输入："croakcrook"，输出：-1

初始解法

我们可以使用一个大小为 128 的数组 hash（因为字符 ASCII 最大为 127），以字符 ASCII 值为索引记录每个字符的数量。遍历过程中，判断每个字符是否按照 “croak” 顺序出现。比如：

• 遇到 “c” 时，增加 hash['c'] 的计数。
• 遇到 “r” 时，确保 hash['c'] > 0，表示有足够的 “c” 来支撑"r"，再增加 hash['r'] 的计数，并减少 hash['c']。
• 同理对其他字符处理。

遍历结束后，检查各字符状态，确保所有青蛙完整发出了 “croak”。

初始代码：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int hash[128] = {0}; // 使用128大小的数组
        for (auto& ch : croakOfFrogs) {
            if (ch == 'c') {
                if (hash['k'] > 0) hash['k']--; // 复用已完成的青蛙
                hash['c']++;
            } else if (ch == 'r') {
                if (hash['c'] == 0) return -1; // 检查前序字符
                hash['c']--; hash['r']++;
            } else if (ch == 'o') {
                if (hash['r'] == 0) return -1;
                hash['r']--; hash['o']++;
            } else if (ch == 'a') {
                if (hash['o'] == 0) return -1;
                hash['o']--; hash['a']++;
            } else if (ch == 'k') {
                if (hash['a'] == 0) return -1;
                hash['a']--; hash['k']++;
            }
        }

        if(hash['c'] == 0 && hash['r'] == 0 && hash['o'] == 0 && hash['a'] == 0)
            return hash['k'];
        return -1;
    }
};

问题：这种方法的空间利用率较低，因为我们只用到 “croak” 5 个字符，但却开辟了大小为 128 的数组。

优化解法

我们可以进一步优化。因为我们只需要追踪 “croak” 这 5 个字符的状态，因此：

1. 将数组大小减少到 5：创建一个大小为 5 的数组 hash，每个位置对应 “croak” 中的字符状态。
2. 通过映射表 index：将 “croak” 中每个字符映射到 hash 数组的索引位置，直接通过索引更新字符的计数。

这样可以减少空间浪费，代码更清晰。

优化代码：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n); // 使用5个位置的数组表示 croak
        unordered_map<char, int> index; // 映射字符到数组索引

        for (int i = 0; i < n; i++)
            index[t[i]] = i; // 初始化映射关系

        for (char ch : croakOfFrogs) {
            if (ch == 'c') {
                if (hash[n - 1] > 0) hash[n - 1]--; // 若有完整的 "croak" 可复用
                hash[0]++;
            } else {
                int i = index[ch];
                if (hash[i - 1] == 0) return -1; // 若缺少前一个字符
                hash[i - 1]--;
                hash[i]++;
            }
        }

        // 检查所有青蛙是否都完成了 "croak" 叫声
        for (int i = 0; i < n - 1; i++)
            if (hash[i] != 0) return -1;

        return hash[n - 1];
    }
};

代码讲解

1. 数组 hash：我们使用大小为 5 的数组 hash，每个位置表示 “croak” 中的一个字符。hash[0] 表示“c”的数量，hash[4] 表示完整“croak”的青蛙数量。
2. 映射 index：利用 unordered_map 将 “croak” 中的字符映射到 hash 数组的索引位置。这样每次遇到某字符时，可以快速找到其在 hash 中的位置。
3. 遍历过程：
   • 遇到 “c”：表示青蛙开始叫，检查是否有复用的青蛙可用，若有则减少 hash[4]，然后增加 hash[0]。
   • 遇到其他字符：确保前一个阶段的青蛙数量足够。若不足，返回 -1。
4. 结束检查：遍历结束后，检查 hash[0] 到 hash[3] 是否为 0，确保没有青蛙停留在中间阶段。
5. 返回结果：返回 hash[4]，表示需要的最少青蛙数量。

易错点提示

1. 字符顺序检查：每只青蛙必须按照 “croak” 的顺序叫。如果某字符的前序字符计数不足，则说明顺序出错，直接返回 -1。
2. 复用条件：当一只青蛙完成 “croak” 后，可以复用它从 “c” 开始再次叫，减少总青蛙数量。
3. 末尾检查：确保所有青蛙完整叫出“croak”，防止有青蛙停留在中途。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 为字符串 croakOfFrogs 的长度。我们只需一次遍历。
• 空间复杂度：O(1)，因为 hash 数组大小固定为 5，unordered_map 只存储 5 个字符的映射关系。

写在最后

模拟题的难点在于逻辑的严谨和细节的把握，它们就像编程世界中的微小拼图，帮助我们逐渐构建完整的逻辑框架。希望通过这篇文章，你能感受到代码细节之美，获得更丰富的编程技巧。期待在未来的模拟题挑战中，你能以更加从容的姿态应对，享受算法探索带来的乐趣。感谢你的阅读，愿你在算法学习的道路上不断成长！

以上就是关于【优选算法篇】算法江湖中的碎玉拾光——C++模拟题全解，踏步逐章细细品味的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️