模拟 算法
目录
题目一——1576. 替换所有的问号 - 力扣（LeetCode）
模拟算法
模拟算法就是按照葫芦画瓢，题目通常就告诉你怎么做了，你就照做即可。
它的特点就是思路简单。它考的就是我们的代码能力。
所以我们做这种题目的时候，就要先在草稿纸上面先推演一遍我们的算法流程
99%的模拟题的优化方式都是找规律
题目一——1576. 替换所有的问号 - 力扣（LeetCode）
这题很简单，我们只需从前往后扫，扫到一个?就更改它，只要保证更改后的字符和左右相邻的字符不同即可
class Solution {
public:
string modifyString(string s) {
// 遍历输入字符串s的每个字符
for(int i=0;i<s.length();i++)
{
// 如果当前字符是'?'
if(s[i]=='?')
{
// 遍历所有小写字母（'a'到'z'）
for(int ch='a';ch<='z';ch++)
{
// 检查当前字符ch是否满足条件：
// 如果它是第一个字符或者前一个字符不是ch，
// 并且它是最后一个字符或者后一个字符不是ch
if((i==0||s[i-1]!=ch)&&(i==s.length()-1||s[i+1]!=ch))
{
// 如果满足条件，将当前位置的'?'替换为ch
s[i]=ch;
// 替换后跳出内层循环，因为只需要找到一个满足条件的字符即可
break;
}
}
}
}
// 返回修改后的字符串
return s;
}
};
题目二——495. 提莫攻击 - 力扣（LeetCode）
我们取俩个连续的数组元素，然后作它们的差值
如果这个差值x>=d的话，那么我们的中毒时间是要全加上的，即ret+=d
如果这个差值x<d的话，那么我们的中毒时间，就变成了ret+=x;
注意最后一个元素
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret=0;
for(int n=0;n<timeSeries.size()-1;n++)
{
int x=timeSeries[n+1]-timeSeries[n];
if(x>=duration)
{
ret+=duration;
}
else
{
ret+=x;
}
}
ret+=duration;//最后一次需要完全加上
return ret;
}
};
题目三——6. Z 字形变换 - 力扣（LeetCode）
其实Z字形就是下面这个
n等于几，就是从上往下几个！！
所以这个题目的思路就应该是先将源字符串排列成倒Z字形。
然后我们再进行逐行读取
这个看起来好像很简单
如果说要模拟，我们就得创建一个矩阵，行数是numRows，那列数是字符串的长度m。
这样子肯定是够的
首先我们先让y=0，然后让x++，直到numRows-1;
接着我们是要往右上方移动，也就是x-1,y+1，直到x=0的时候
这个时候我们再重复上面的步骤就好了
但是大家有没有发现这个算法的空间复杂度太高了，我们得对其进行优化
99%的模拟题的优化方式都是找规律
我们列出下面这个图像
有没有发现规律啊？
将所有数替换成用周期来表示的变量：
- 第一行的数是：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）的倍数左右取值。
我们将2row-2设置为d。
- 第一行：0，d，2d
- 第二行：1，d-1，d+1，2d-1，2d+1
- 第三行：2，d-2，d+2，2d-2，2d+2
- 第四行：3，d+3，2d+3
以此规律，我们可以写出迭代算法。
class Solution
{
public:
string convert(string s, int numRows)
{
// 处理边界情况：如果只有一行，则无需转换，直接返回原字符串
if (numRows == 1) return s;
string ret; // 存储转换后的字符串
int d = 2 * numRows - 2; // 一个完整的Z字形周期的长度（包含竖直和斜向的字符数）
int n = s.size(); // 原字符串的长度
// 1. 先处理第一行（竖直向下的字符）
// 由于Z字形的特性，第一行的字符在原字符串中的索引是每隔d个位置出现的
for (int i = 0; i < n; i += d)
{
ret += s[i]; // 将第一行的字符添加到结果字符串中
}
// 2. 处理中间行（既有竖直向下的字符，也有斜向上的字符）
// 枚举每一行（不包括第一行和最后一行），k表示当前处理的行号（从1开始计数）
for (int k = 1; k < numRows - 1; k++)
{
// i表示当前行竖直向下的字符在原字符串中的索引
// j表示当前行斜向上的字符在原字符串中的索引（通过周期长度d计算得到）
for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
{
// 如果竖直向下的字符索引i在字符串范围内，则添加到结果字符串中
if (i < n) ret += s[i];
// 如果斜向上的字符索引j在字符串范围内，则添加到结果字符串中
// 注意：由于j的初始值是d-k（即第一组斜向上字符的索引），
// 因此当j小于n时，才需要添加到结果字符串中，避免越界
if (j < n) ret += s[j];
}
}
// 3. 处理最后一行（竖直向下的字符）
// 最后一行的字符在原字符串中的索引也是每隔d个位置出现的，
// 但由于是从numRows-1开始计数，因此需要单独处理
for (int i = numRows - 1; i < n; i += d)
{
ret += s[i]; // 将最后一行的字符添加到结果字符串中
}
return ret; // 返回转换后的字符串
}
};
题目四——38. 外观数列 - 力扣（LeetCode）
我们重新解读一下题目
问题描述
这个问题要求我们生成一个特殊的字符串序列，这个序列被称为“外观数列”。这个数列的每一项都是根据前一项来生成的，而生成的方式是通过对前一项进行“行程长度编码”（Run-Length Encoding, RLE）。
行程长度编码（RLE）
行程长度编码是一种简单的字符串压缩方法。它的工作原理是这样的：
- 当我们遇到一个字符串时，我们会查看字符串中的连续相同字符。
- 对于每一组连续相同的字符，我们记录这个字符以及它出现的次数。
- 然后，我们用“字符出现的次数”加上“这个字符本身”来替换这一组连续相同的字符。
例如，对于字符串 "3322251"：
- "33" 可以被替换为 "23"（因为有两个3）。
- "222" 可以被替换为 "32"（因为有三个2）。
- "5" 保持不变，因为它只出现了一次，所以我们可以用 "15" 来表示它（虽然通常在实际应用中，单个字符可能不会被压缩，但为了这个题目的目的，我们假设所有字符都会被这样处理）。
- "1" 同样保持不变，用 "11" 来表示。
所以，字符串 "3322251" 经过行程长度编码后变成了 "23321511"。
外观数列的生成
现在，让我们来看如何生成外观数列：
- 外观数列的第一项是 "1"。
- 对于 n > 1 的情况，第 n 项是第 n-1 项的外观数列进行行程长度编码后的结果。
示例
- 当 n = 1 时，输出是 "1"。
- 当 n = 2 时，第一项 "1" 的行程长度编码是 "11"（因为有一个1）。
- 当 n = 3 时，第二项 "11" 的行程长度编码是 "21"（因为有两个1）。
- 当 n = 4 时，第三项 "21" 的行程长度编码是 "1211"（因为有一个2和一个1，然后又一个1）。
任务
给定一个整数 n，你的任务是返回外观数列的第 n 个元素。
希望这个解释能够帮助你更好地理解这个问题！
我们很快就能写出下面这个代码
class Solution {
public:
std::string countAndSay(int n) {
// 基本情况：当 n 为 1 时，直接返回 "1"
if (n == 1) {
return "1";
}
// 递归调用 countAndSay 函数来获取前一项的外观数列
std::string prev = countAndSay(n - 1);
// 初始化一个空字符串 result，用于存储编码后的结果
std::string result;
// 初始化计数器 count 为 1，用于记录当前字符的连续出现次数
int count = 1;
// 对前一项 prev 进行行程长度编码
// 从第二个字符开始遍历，因为我们需要与前一个字符进行比较
for (int i = 1; i < prev.length(); ++i) {
// 如果当前字符与前一个字符相同，则增加计数器 count
if (prev[i] == prev[i - 1]) {
++count;
} else {
// 如果不同，则将 count 和前一个字符拼接到 result 中
// 并重置 count 为 1，准备记录下一组连续字符的计数
result += std::to_string(count) + prev[i - 1];
count = 1;
}
}
// 处理最后一组字符（因为循环中不会处理最后一个字符的计数）
// 将 count 和 prev 的最后一个字符拼接到 result 中
result += std::to_string(count) + prev.back();
// 返回编码后的字符串 result
return result;
}
};
我们还有另外一种解法
class Solution
{
public:
string countAndSay(int n)
{
// 初始化返回字符串为外观数列的第一项 "1"
string ret = "1";
// 使用 for 循环从第二项开始生成，直到第 n 项
// 因为第一项已经初始化为 "1"，所以循环 n-1 次
for(int i = 1; i < n; i++)
{
// 临时字符串 tmp 用于存储当前项的行程长度编码结果
string tmp;
// 获取当前项（即上一次循环后的 ret）的长度
int len = ret.size();
// 使用双指针 left 和 right 来遍历当前项，进行行程长度编码
for(int left = 0, right = 0; right < len; )
{
// 移动 right 指针，直到找到与 left 指针不同字符的位置
while(right < len && ret[left] == ret[right]) right++;
// 将 left 到 right-1 之间相同字符的数量和字符本身拼接到 tmp 中
// 注意：这里 right - left 是相同字符的数量，ret[left] 是字符本身
tmp += to_string(right - left) + ret[left];
// 移动 left 指针到 right 的位置，为下一次循环做准备
left = right;
}
// 更新 ret 为当前项的行程长度编码结果，即 tmp
ret = tmp;
}
// 返回第 n 项的外观数列
return ret;
}
};
题目五——1419. 数青蛙 - 力扣（LeetCode）
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
// 定义青蛙叫声的顺序字符串
string t = "croak";
int n = t.size(); // 获取叫声顺序的长度
// 使用数组来模拟哈希表，记录每个叫声字符当前同时在叫的青蛙数量
// 数组下标对应叫声字符在 "croak" 中的位置，数组值对应数量
vector<int> hash(n);
// 使用哈希表来快速查找每个叫声字符在 "croak" 中的下标
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'（即是否有青蛙已经结束叫声但还未被计数）
// 如果有，则将其从计数中减去（相当于将其计入当前开始叫的青蛙中）
// 注意：这里假设同时不会有超过一个青蛙结束叫声但还未被计数的情况
// 因为如果这样，输入字符串就是无效的（会有返回 -1 的情况处理）
if(hash[n - 1] != 0) hash[n - 1]--;
// 增加当前开始叫的青蛙数量（对应 'c'）
hash[0]++;
}
else // 如果当前叫声不是 'c'
{
// 获取当前叫声字符在 "croak" 中的下标
int i = index[ch];
// 检查前一个叫声字符是否有青蛙在同时叫（即是否有青蛙在按顺序叫到这个字符的前一个字符）
if(hash[i - 1] == 0) return -1; // 如果没有，说明输入字符串无效，返回 -1
// 将前一个叫声字符的青蛙数量减一（表示有一个青蛙叫到了当前字符）
// 并增加当前叫声字符的青蛙数量（表示有一个青蛙开始叫这个字符）
hash[i - 1]--;
hash[i]++;
}
}
// 遍历哈希表，检查除了最后一个叫声字符 'k' 之外，其他叫声字符是否还有青蛙在同时叫
// 如果有，说明输入字符串无效（有青蛙的叫声没有完整结束），返回 -1
for(int i = 0; i < n - 1; i++)
if(hash[i] != 0)
return -1;
// 返回同时叫 'k' 的青蛙数量，即最少需要的青蛙数量
// 因为每个青蛙都会按顺序叫到 'k'，所以最后叫 'k' 的青蛙数量就是最少需要的青蛙数量
return hash[n - 1];
}
}; 
原文地址：https://blog.csdn.net/2301_80224556/article/details/143989441
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！