算法思想之模拟

欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之模拟
发布时间：2025.4.14
隶属专栏：算法

算法介绍

模拟算法（Simulation Algorithm）是一种通过直接按照问题描述的步骤进行程序化实现的算法，强调对现实过程或逻辑规则的忠实还原。其核心思想是 “无需复杂优化，严格按规则执行”，常用于解决流程明确但实现细节繁琐的问题。

核心特点

1. 流程驱动：严格遵循问题描述的操作步骤。
2. 细节密集：需要处理大量边界条件和状态变化。
3. 直观性强：代码结构常与问题描述高度对应。

常见问题

1. 边界错误：数组越界、循环终止条件错误
2. 状态遗漏：未正确更新中间状态变量
3. 性能陷阱：大数量级时超时（需改用数学方法）

优化方向

1. 高频状态查询：使用哈希表记录关键状态
2. 大量重复计算：预计算并缓存结果
3. 空间浪费：压缩存储（如位运算）

例题

替换所有的问号

题目链接

1576. 替换所有的问号

题目描述

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

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

示例 2：

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

提示：

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

算法思路

纯模拟。从前往后遍历整个字符串，找到问号之后，就用 a ~ z 的每一个字符去尝试替换即可。

代码实现

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

提莫攻击

题目链接

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 秒，即第 2 秒和第 3 秒。
  艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries 按 非递减 顺序排列

算法思路

模拟 + 分情况讨论。
计算相邻两个时间点的差值：

• 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒；
• 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。

代码实现

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

Z 字形变换

题目链接

6. Z 字形变换

题目描述

将一个给定字符串 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

算法思路

找规律，用 row 代替行数，row = 4 时画出的 N 字形如下：

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 为一个周期进行规律变换的。将所有数替换成用周期来表示的变量：
第⼀行的数是：0, 2row - 2, 4row - 4；
第⼆行的数是：1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1；
第三行的数是：2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2；
第四行的数是：3, (2row - 2) + 3, (4row - 4) + 3。
可以观察到，第一行、第四行为差为 2row - 2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为(2n - 1, 2n)的数围绕（2row - 2）的倍数左右取值。
以此规律，我们可以写出迭代算法。

代码实现

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1)return s;int d = 2*numRows -2, n = s.size();string ret;for(int i = 0; i < n; i+=d)//处理第一行ret+=s[i];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];}for(int i = numRows-1; i < n; i += d)ret += s[i];return ret;}
};

外观数列

题目链接

38. 外观数列

题目描述

外观数列是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"

countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

输入：n = 4
输出：“1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = “1” 的行程长度编码 = “11”
countAndSay(3) = “11” 的行程长度编码 = “21”
countAndSay(4) = “21” 的行程长度编码 = “1211”

示例 2：

输入：n = 1
输出：“1”
解释：
这是基本情况。

提示：

• 1 <= n <= 30

进阶：你能迭代解决该问题吗？

算法思路

所谓外观数列，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。

代码实现

class Solution {
public:string countAndSay(int n) {string s = "1";while(--n){string ret;int left = 0, right = 0, sum = s.size();while(right < sum){while(right<sum &&s[right] == s[left])right++;ret+=to_string(right-left);ret+=s[left];left = right;}s = ret;}return s;}
};

数青蛙

题目链接

1419. 数青蛙

题目描述

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = “croakcroak”
输出：1
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = “crcoakroak”
输出：2
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 “crcoakroak”
第二只青蛙 “crcoakroak”

示例 3：

输入：croakOfFrogs = “croakcrook”
输出：-1
解释：给出的字符串不是 “croak” 的有效组合。

提示：

• 1 <= croakOfFrogs.length <= 105
• 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

算法思路

模拟青蛙的叫声。

• 当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1 ；
• 当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞一个青蛙。

代码实现

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> hash(n);// 用数组模拟hash表unordered_map<char, int> index;//字符和数组下标的映射for(int i = 0; i < n; i++)index[t[i]] = i;for(auto ch : croakOfFrogs){if(ch == 'c'){if(hash[n-1] != 0)hash[n-1]--;hash[0]++;}else{int i = index[ch];if(hash[i-1] == 0)return -1;hash[i-1]--;hash[i]++;}}for(int i = 0; i < n-1; i++){if(hash[i] != 0)return -1;}return hash[n-1];}
};

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！