【算法】模拟
个人主页 ： zxctscl 如有转载请先通知
前言
模拟算法就是根据题目所给的照葫芦画瓢。 考察的是代码能力。 步骤：1.模拟算法流程（一定得自己先过一遍流程） 2.把流程转化为代码
1. 1576. 替换所有的问号
1.1 分析
题目的意思很显而易见，遍历一遍字符串如果是？，就找一个小写字母来替换它，而它的前面一个字符和它不相同，它后面一个字符和它也不能相同。得处理一下边界情况，如果?在开始位置，就不用比较它前面位置，比较后面那个位置就行。同样在结尾位置的话，就比较前面的一个字符相不相等就行。
1.2 代码
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;
}
};2. 495. 提莫攻击
2.1 分析
当前这个位置减去前面一个位置的差，如果大于等于中毒时间，那么就全部加上中毒时间；如果差小于中毒时间，那么就是加上这个差值。得注意最后一个值没有判断，最后的值还得再加上一个中毒时间才行。
2.2 代码
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int n=timeSeries.size();
int ret=0;
for(int i=1;i<n;i++)
{
int t=timeSeries[i]-timeSeries[i-1];
if(t>=duration)
{
ret+=duration;
}
else ret+=t;
}
return ret+duration;
}
};3. 6. Z 字形变换
3.1 分析
一、题目解析 按题目所述，像下面图片这样的就是Z字型。
二、算法原理 要想得到最后为Z字型输出的字符串，可以直接开一个矩阵直接先把字符一个一个放进去再一行一行输出。 但还可以用另外一个方式，就是找规律。
举个例子：把字符的下标都写到矩阵里面，就发现了规律。 第一行每间隔2n-2就出现一次，为了方便描述，就把间隔叫做公差d=2n-2,第一行只需要输出每次个d个数的字符就可以。 最后一行和第一行一样，也是间隔d个字符数。 来看中间几行，1和5到11和13中间间隔的也是d个数，那么直接一次性输出两个就行。
3.2 代码
class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1)return s;
string ret;
int d=2*numRows-2;
int 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. 38. 外观数列
4.1 分析
模拟题目的意思 找到连续相同的字符解释一下，可以利用双指针来进行，如果两个指针指向的位置字符相同就一直走，不一样就停下来，中间元素的个数就是指针的差值；然后让左边指针指向右边指针的位置，再重复上面的操作就可以了。
4.2 代码
class Solution {
public:
string countAndSay(int n) {
string ret="1";
for(int i=1;i<n;i++)
{
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;
}
ret=tmp;
}
return ret;
}
};5. 1419. 数青蛙
5.1 分析
模拟 用一个哈希表时刻记录每一次字符出现的情况。如果青蛙叫了c时候，那么就用1记录一下有一个青蛙叫了c字符;遍历到r的时候看看前面有没有青蛙叫了c,有就让这个青蛙继续叫r,在哈希表了让c减减，r加加就行。当又遇到一个c时候，表示又有一个青蛙过来，然后继续遍历到o的时候，要看看哈希表前面有没有青蛙叫过r，有的话r减减，o加加，继续往后重复直到k。 但是题目要求青蛙数目最少，这里k中有数的时候，此时又有c时候，就从k里面搬一个青蛙来从c开始叫，k减减，c加加，重复上面过程。k里面的数存的就刚好是结果。 但是如果除了k里面还有非0元素，那么就返回-1。
如果在在哈希表中，在r位置之前没有c那么就返回-1：
总结，都得找前驱字符，如果前驱字符有，那么前驱字符减减，当前字符加加；没有就返回-1。 最后一个字符看看它是不是在哈希表里面存在，存在就是最后一个字符减减，当前字符加加；不存在就当前字符加加。
5.2 代码
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
string t = "croak";
int n = t.size();
vector<int> hash(n); // ⽤数组来模拟哈希表
unordered_map<char, int> index; //[x, x这个字符对应的下标]
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];
}
};腾讯云开发者
