【优先算法】专题——模拟(详细讲解)
【优先算法】专题——模拟(详细讲解)
前言
模拟算法其实就是比葫芦画瓢。
特点：思考比较简明，考察的就是我们的代码能力
模拟算法流程（一定要在演草纸上过一遍流程，不要凭空想象），然后把流程转化成代码。
一、替换所有的问号
题目链接：替换所有的问号
题目描述：
找到我们要替换的字符然后依次进行判断，我们用a~z依次尝试放在这个位置是否可以，需要保证这个字符不能和前面这个字符还有后面那个字符相等即可。(替换用a~z来替换)
当要被替换的?在最前面我们只需要判断和后面那个字符相等即可，如果被替换的?在最后面我们只需要判断和前面的字符是否相等即可。
参考代码：
class Solution {
public:
string modifyString(string s) {
int n = s.size();
for(int i = 0;i < s.size();i++)
{
if(s[i] == '?')//替换
{
for(char j = 'a';j <='z';j++)
{
if((i == 0 || s[i-1] !=j) && (i == n-1 || s[i+1] != j))
{
s[i] = j;
break;
}
}
}
}
return s;
}
};二、提莫攻击
题目链接：提莫攻击
题目描述：
如上示例1：我们在第一秒中毒了中毒时间为两秒我们在第三秒恢复，但是在第四秒的时候又中毒了中毒时间两秒，那么一共就是四秒。
如上示例2：我们在第一秒的时候受到了攻击进行中毒状态中毒时间为两秒，但是我们在第二秒的时候又被攻击了那么此时就重置了我们的中毒时间从第二秒开始到第三秒为中毒状态，一共中毒三秒
算法原理：
计算前一个和后一个时间点的差值，如果差值⼤于等于中毒时间，说明上次中毒可以持续 duration 秒，如果差值⼩于中毒时间，那么上次的中毒只能持续两者的差值。
参考代码：
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;
}
};三、Z字形变换
题目链接：Z字形变换
题目描述：
如果题目中举的例子看不懂可以看如下这个例子 ：
解法：模拟 + 找规律
第一行的特点就是第一个0然后跳到6再跳到12跳跃的间隔是一样的，可以发现公差为6我们用一个变量d视为我们的公差，这样我们就可以直接去下标为0+6的位置找到我们的g了，然后6+6就可以找到我们下标为12的m了这样我们就把第一行的字符全部找到了，因为我们后面还会用到这个公差所以我们推理一下我们计算公差的公式，公差d其实就是6-0的元素的个数那么这里个数为6a~f，我们把5往左边平移一个单位，其实就是第一列+第二列减出2个空格，d = 2 * n - 2。
第一行：第一个为0 然后0+d、0+2d.....算到0+kd(kd小于len，一直加到这个下标超过这个字符串长度才停止) k行(k为当前行数)：(k，d-k) 、(k+d，d-k+d)、(k+2d，d-k+2d) n-1行：n-1、n-1 +d 、n-1+2d....n-1 + kd
参考代码：
class Solution {
public:
string convert(string s, int numRows) {
string ret;
int d = 2 * numRows - 2,n = s.size();
//处理numRows = 1;
if(numRows == 1) return s;
//1.先处理第一行
for(int i = 0;i<n;i+=d)
{
ret += s[i];
}
//2.处理中间行
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];
}
}
//3.处理最后一行
for(int i = numRows-1;i < n;i += d)
{
ret += s[i];
}
return ret;
}
};注意：当我们的numRows等于1的时候会死循环，进第一个for循环之后因为公差为负数，0+负数还是这个负数导致死循环。
四、外观数列
题目链接：外观数列
题目描述：
1这里有1个有解释为11，然后解释11这里解释为21也就是2个1，然后21这里解释为12 11也就是说有1个2、1个1，然后解释1211这里解释为1个1、1个2、2个1解释为11 12 21以此类推
解法：模拟 + 双指针
定义一个left和right然后判断是否相等如果相等right++，当不相等的时候前面相同个数为right-left
参考代码：
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;
}
};五、数青蛙
题目链接：数青蛙
题目描述：
示例1：一只青蛙叫完之后这只青蛙接着叫，返回1因为一只青蛙可以把它叫完。
我们
示例二：一只青蛙叫完之后才可以接着继续叫，如下示例要有2只青蛙才能把蛙鸣叫完。
算法思路：
模拟⻘蛙的叫声
当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符， 有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有， 直接返回 -1 ；
当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有⻘蛙叫出来。如果有，就让 这个⻘蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞⼀个⻘蛙。
举例：c r c o a k r o a k c r o a k
借助哈希表来记录一下字符出现的情况。
第一个字符为c我们用1标记一下说明有青蛙叫了c这个字符，第二个字符为r此时我们在哈希表中查找一下看有没有c这个字符此时里面有青蛙叫了c这个字符，我们把c标记的那个1去掉然后用一个1标准r这个位置，哈希表中操作其实就是c-- r++，又碰到一个c此时又有一个青蛙过来了叫出了c这个字符用1标记一下也就是让c++，然后是o我们要去哈希表中看看有没有r这个字符此时里面有，我们让r-- o++，接着是a我们要查看哈希表里面有没有o这个字符哈希表此时有o这个字符，我们o-- a++，然后是k这个字符看哈希表中是否有a这个字符哈希表中有a这个字符，此时k++ c--，然后又是r哈希表中存在c那么此时c-- r++，然后是o哈希表里面存在r，此时o++ r--，接着是a哈希表里面存在r，然后r-- a++，接着是哈希表里面存在a，那么a--,k++(k此时等于2了)，然后继续此时为c题目要求说要最少青蛙数量当前面k已经有数的时候说明已经有青蛙叫过一次了，此时k为2说明已经有两只青蛙叫完了，此时我们碰到c的时候可以让已经叫完的青蛙来叫，我们搬出一只青蛙让它从c这个位置开始叫，当k有数的时候我们k--然后从刚刚出现的字符c开始叫。
总结：
'r' 'o' 'a' 'k'找一下前驱字符，是否存在哈希表中
- 存在：前驱个数--，当前字符++
- 不存在：返回-1
c：找最后一个字符(k是否有青蛙叫完)，是否在哈希表中存在
- 存在：最后一个字符(k--)--，当前字符++
- 当前字符++
参考代码一：
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int hash[5] = {0};
string t = "croak";
int len = t.size();
unordered_map<char,int>index;
for(int i = 0 ;i<len;i++)
{
index[t[i]] = i;
}
for(auto ch : croakOfFrogs)
{
if(ch == 'c')
{
if(hash[len-1] != 0) hash[len-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<len-1;i++)
if(hash[i] != 0)
return -1;
return hash[len-1];
}
};参考代码二：
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n = croakOfFrogs.size();
string s ="croak";
int i = 0;
int c = 0,r = 0,o = 0,a = 0,k = 0;
int ret = 0;
while(i<n)
{
if(croakOfFrogs[i] == 'c')
{
if(k == 0)
++ret;
else
--k;
c++;
}
else if(croakOfFrogs[i] == 'r')
{
c--;
r++;
}
else if(croakOfFrogs[i] == 'o')
{
--r;
++o;
}
else if(croakOfFrogs[i] == 'a')
{
--o;
++a;
}
else if(croakOfFrogs[i] == 'k')
{
--a;
++k;
}
if(c < 0 || r < 0|| o < 0 || a <0) return -1;
i++;
}
if(c != 0 || r != 0 || o != 0 || a != 0) return -1;
return ret;
}
};完
腾讯云开发者
