C++优选算法六 模拟
一、模拟
模拟算法是一种基本的算法思想.
1、定义
模拟算法是指根据题目提供的信息，将该题目的解决过程模拟出来，从而得到最终的结果。这种算法不能称为特定的模板，它需要根据题目的具体要求进行编程模拟。
2、特点
- 灵活性：模拟算法不像一些经典算法那样有固定的模板，它需要根据题目的意思进行灵活的模拟。
- 直观性：由于模拟算法是模拟题目的解决过程，因此它比较直观，易于理解和实现。
- 适用性：模拟算法适用于各种需要模拟现实世界过程、系统或现象的场景，如物理仿真、生物仿真等。
二、示例题目
1.替换所有的问号. - 力扣（LeetCode）
给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
注意：你 不能 修改非 '?' 字符。
题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：
输入：s = "?zs" 输出："azs" 解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2：
输入：s = "ubv?w" 输出："ubvaw" 解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
解法(模拟):
算法思路:
纯模拟。从前往后遍历整个字符串，找到问号之后，就用a~z的每一个字符去尝试替换即可。
class Solution {
public:
string modifyString(string s)
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='?')
{
for(int j=0;j<26;j++)
{
char ch='a'+j;
if(i==0)
{
if(ch!=s[i+1])
{
s[i]=ch;
break;
}
continue;
}
if(i==s.size()-1)
{
if(ch!=s[i-1])
{
s[i]=ch;
break;
}
continue;
}
if(ch!=s[i-1]&&ch!=s[i+1])
{
s[i]=ch;
break;
}
}
}
}
return s;
}
};2.提莫攻击. - 力扣（LeetCode）
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续 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 。
解法(模拟+分情况讨论)
算法思路:
模拟+分情况讨论。
计算相邻两个时间点的差值:
- 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒;
- 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。
class Solution { public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int ret=0; for(int i=0;i<timeSeries.size()-1;i++) { if(timeSeries[i+1]-timeSeries[i]>=duration) ret+=duration; else ret+=timeSeries[i+1]-timeSeries[i]; } return ret+duration; } };3.Z字形变换. - 力扣（LeetCode）
将一个给定字符串 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"
解法(模拟+找规律)
算法思路:
找规律，用 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;
string ret;
int d=2*numRows-2,n=s.size();
//先处理第一行
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;
}
};4.外观数列. - 力扣（LeetCode）
「外观数列」是一个数位字符串序列，由递归公式定义：
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"
解释：
这是基本情况。
解法(模拟+双指针)
算法思路:
所谓「外观数列」，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。
class Solution {
public:
string countAndSay(int n)
{
vector<string> vv(n);
vv[0]='1';
for(int i=1;i<n;i++)
{
string str;
int left=0,right=0;
while(right<vv[i-1].size())
{
if(vv[i-1][right]==vv[i-1][left])
right++;
else
{
int ret=right-left;
str += to_string(ret);
str+=vv[i-1][left];
left=right;
}
}
int ret=right-left;
str += to_string(ret);
str+=vv[i-1][left];
vv[i]=str;
}
return vv[n-1];
}
};5.数青蛙. - 力扣（LeetCode）
给你一个字符串 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" 的有效组合。
解法(模拟+分情况讨论)
算法思路:
模拟青蛙的叫声。
- 当遇到'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每一个字符对应的前驱字符。有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符;如果没有，直接返回 -1;
- 当遇到 'c’'这个字符的时候，我们去看看 'k'这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 'c' 这个字符;如果没有的话，就重新搞一个青蛙。
class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { unordered_map<char,int> index;//[x,i]x这个字符对应的下标 string str="croak"; int n=str.size(); vector<int> hash(n);//用数组模拟哈希表 for(int i=0;i<n;i++) { index[str[i]]=i; } for(char 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]; } };