模拟算法
- 1.替换所有的问号
- 2.提莫攻击
- 3.Z 字形变换
- 4.外观数列
- 5.数青蛙
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
模拟算法 —> 比葫芦画瓢
在模拟这一类题里面，题目已经告诉了这些题应该怎么做，所有我们接下来做的是把题目中的过程转换成代码解决这个问题。
这个算法特点：思路比较简单，考察的是代码能力。
这就决定了，
- 一定要模拟算法流程（一定要在演草纸上过一遍流程，注意细节！）
- 把流程转化成代码
1.替换所有的问号
题目链接：1576. 替换所有的问号
题目描述：
算法原理：
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 || s[i-1] != ch) && (i==n-1 || s[i+1] != ch))
{
s[i]=ch;
break;
}
}
}
}
return s;
}
};
2.提莫攻击
题目链接：495. 提莫攻击
题目分析：
当在t秒中毒，持续时间为 [t，t+duration-1]
算法原理：
首先我们发现一个规律
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret=0;
for(int i=1;i<timeSeries.size();++i)
{
int x=timeSeries[i]-timeSeries[i-1];
if(x>=duration) ret+=duration;
else ret+=x;
}
return ret+duration;//最后一次中毒时间也要加上
}
};
3.Z 字形变换
题目链接：6. Z 字形变换
题目分析：
给你一个字符串，它按照Z字形排列后，然后从左往右输出按照N字形排列之后的字符串。
算法原理：
解法一：模拟
题目要求怎么做就模拟一下，首先开辟一个n行，然后字符串长度的列的二维数组。这样能保证把所有字符都能放进去。
但是时间复杂度和空间复杂度都是O(len*n)
想一想能不能进行优化。
模拟题的优化方式都是在模拟的基础上找规律
解法二：找规律
上面是把字符填到数组里，现在我把下标填进去
第一行从0跳到6然后在跳到12，我们发现它的间隔是一样的，这里的间隔公差设为d，d=6。也就是说我们直接把下标0位置弄完，然后在找下标6的位置等等，就可以把第一行字符全部找完，就不用在弄一个数组然后把字符填上去了。
公差d应该怎么计算呢，我们发现 d=2*n-2
最后一行从下标n-1开始，n-1+d，n-1+2d，下标一定是要小于字符串长度的。
第一行和最后一行我们解决了，剩下就是中间行了
我们发现中间行公差其实也是6，但是如果一个一个算比如1+6=7，7+6=13，然后还要回头在来算5+6=11。我们其实可以两个下标一起计算
上面d=2*n-2有可能不是所有情况都适应，我们再举个例子
发现这个公差公式也是正确的。
但是一定要注意n=1的情况，那就只有一行，如果按照上面找的规律就会死循环，此时原本的字符串就是最终答案，因此特殊处理一下
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 i=1;i<numRows-1;++i)//枚举每一行
{
for(int j=i,k=d-i;j<n ||k<n;j+=d,k+=d)
{
if(j<n) ret+=s[j];
if(k<n) ret+=s[k];
}
}
// 3.处理最后一行
for(int i=numRows-1;i<n;i+=d)
ret+=s[i];
return ret;
}
};
4.外观数列
题目链接：38. 外观数列
题目分析：
这道题具体意思是，给你一个n返回到n的时候这个数的变化。
算法原理：
解法：模拟+双指针
class Solution {
public:
string countAndSay(int n) {
string ret="1";
for(int i=1;i<n;++i)
{
int left=0,right=0;
string tmp;
while(right<=ret.size())
{
if(ret[right] != ret[left])
{
tmp+=to_string(right-left);
tmp+=ret[left];
left=right;
}
++right;
}
ret=tmp;
}
return ret;
}
};
5.数青蛙
题目链接：1419. 数青蛙
题目分析：
给一个字符串，这个字符串是蛙鸣的组合，让找到这个字符串中蛙鸣所需最少青蛙的个数。
算法原理：
解法：模拟
如果从前往后找蛙鸣太难了，情况太复杂。
我们可以考虑如果到r前面一定要有c，到o前面一定要有r等等，我们要找一个字符的前缀。判断字符串在不在我们一般用哈希表
下面是三种情况
总结一下：
r，o，a，k
找一下前驱字符，是否在哈希表中存在
- 存在：前缀个数- -，当前字符++
- 不存在：返回-1
c 找最后一个字符，是否在哈希表中存在
3. 存在：最后一个字符- -，当前字符++
4. 不存在：当前字符++
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string str="croak";
int n=str.size();
vector<int> hash(n); //用数组来模拟哈希表
unordered_map<char,int> index; //[x,x这个字符的下标]
for(int i=0;i<n;++i)
index[str[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];
}
};
