本篇总结的是模拟算法
模拟算法的实现原理很简单，就是依据题意实现题意的目的即可，考察的是你能不能实现题目题意的代码能力
没有很明显的算法思路，就是根据题意完成目标即可
优化
任何算法都是会有一定的优化空间的，那么在所有模拟的题型中，大多数的题目都是通过找规律来解决问题的，通过找规律可以避免掉很多繁琐的步骤
正如前面的算法原理所说，模拟的算法就是实现题目意思，以此题为例，和题目意思相同，就是替换所有问号即可
class Solution
{
public:
string modifyString(string s)
{
int n=s.size();
if(n==1)
{
return "a";
}
if(s[0]=='?')
{
for(int i='a';i<='z';i++)
{
if(i!=s[1])
{
s[0]=i;
break;
}
}
}
if(s[n-1]=='?')
{
for(int i='a';i<='z';i++)
{
if(i!=s[n-2])
{
s[n-1]=i;
break;
}
}
}
for(int i=0;i<n;i++)
{
if(s[i]=='?')
{
for(int j='a';j<='z';j++)
{
if(j!=s[i-1] && j!=s[i+1])
{
s[i]=j;
break;
}
}
}
}
return s;
}
};
题意也相当简单，直接根据题意模拟即可~
class Solution
{
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
int sum=0;
for(int i=0;i<timeSeries.size()-1;i++)
{
if(timeSeries[i]+duration<=timeSeries[i+1])
{
sum+=duration;
}
else
{
sum+=timeSeries[i+1]-timeSeries[i];
}
}
sum+=duration;
return sum;
}
};
这里展示的是直接使用模拟算法的情况下，可以通过这样的方法进行解决
对于此题来说，还可以通过找规律的方法解决
class Solution
{
public:
string convert(string s, int numRows)
{
int p=1000;
string ans;
vector<vector<char>> v(numRows, vector <char>(p));
int k = 0;
int i = 0;
while (k < s.size())
{
for (int j = 0; j < numRows && k < s.size(); j++)
{
v[j][i] = s[k++];
}
for (int m = numRows - 2; m > 0 && k < s.size(); m--)
{
v[m][++i] = s[k++];
}
i++;
}
for (int i = 0; i < numRows; i++)
{
for (int j = 0; j < p; j++)
{
if (v[i][j] != 0)
{
ans.push_back(v[i][j]);
}
}
}
return ans;
}
};
找规律
如果按下标的形式进行填充，此时再进行观察就会发现是相对容易的
第一行和最后一行每次需要找的数其实是有固定的公差的，而中间部分也有固定规律，因此在写返回的字符串的时候，就可以使用这个原理，分成三部分，先填第一行，再填中间部分，再填最后一行，这样三个模块都填写完毕后字符串也就形成了
此题也是很经典的模拟题，直接根据题意总结即可，强行模拟就可通过，借助一个双指针可以更方便的寻找规律
class Solution
{
public:
string countAndSay(int n)
{
string ret="1";
for(int i=1;i<n;i++)
{
int left=0,right=0;
int count=0;
string tmp;
while(right<ret.size())
{
while(ret[right]==ret[left])
{
right++;
}
count=right-left;
tmp+=count+'0';
tmp+=ret[left];
left=right;
}
ret=tmp;
}
return ret;
}
};
模拟算法和前面相比，实际上不需要过多的算法思维，只需要强行根据题意写出代码即可，但是需要一定的代码能力，如果有代码能力，原照原根据题意进行复刻即可，总体来说还是相对简单的一套算法