一、模拟算法的总结
1、本质：比葫芦画瓢
2、特点：思路较简单，根据题目要求即可，代码量和细节较多
3、解决方法：
（1） 模拟算法流程，在草稿纸上进行演算
（2） 认真审题，考虑细节问题和边界情况
（3） 一步步将流程转化为代码
二、替换所有的问号
. - 力扣（LeetCode）替换所有的问号
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;
}
};三、提莫攻击
. - 力扣（LeetCode）提莫攻击
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 temp=timeSeries[i]-timeSeries[i-1];
//如果后一次的中毒时间没有被覆盖，就是+duration 覆盖了就是+temp
if(temp>=duration) ret+=duration; else ret+=temp;
}
return ret+duration;//最后还有一次持续时间！！
}
};四、Z字形变换
. - 力扣（LeetCode）Z字形变换
class Solution {
public:
string convert(string s, int numRows)
{
if(numRows==1) return s;//处理边界情况
string ret;
int n=s.size(),d=2*numRows-2;//d是公差
//先处理第一行
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;i+=d,j+=d)
{
ret+=s[i];
if(j<n) ret+=s[j];//可能i没越界但是j越界了
}
//处理最后一行;i+=d) ret+=s[i];
for(int i=numRows-1;i<n;i+=d) ret+=s[i];
return ret;
}
};五、外观数列
. - 力扣（LeetCode）外观数列
class Solution {
public:
string countAndSay(int n)
{
string ret("1");//基准样例
for(int i=1;i<n;++i)
{
string temp;//每次都要更新
int len=ret.size();
//定义双指针 从前往后遍历相同的区域
for(int left=0,right=0;right<len;)
{
while(right<len&&ret[left]==ret[right]) ++right;//相等就一直走
//找到该区域了，就temp加上这块区域
temp+=to_string(right-left)+ret[left];
left=right;//更新left;
}
ret=temp;//找完后，更新即可
}
return ret;
}
};六、数青蛙
. - 力扣（LeetCode）数青蛙
写法1： 两个哈希表 一个存储字符和下标的映射关系，另一个用数组模拟哈希表存字符出现的次数。
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs)
{
//对于roak来说，判断前驱字符是否在哈希表中
//在就--前驱 ++当前 不在 返回1
//对于c来说，要判断k是否在哈希表中，如果在就--k然后++c 如果不在就直接++c
string t="croak";
int n=t.size();
int hash[5]={0};//存储字符信息
unordered_map<char,int> index;//用来建立字符和下标的映射关系
for(int i=0;i<n;++i) index[t[i]]=i;//建立t字符串各字符和下标映射关系
for(auto ch:croakOfFrogs)//开始研究
{
if(ch=='c')
{
if(hash[n-1]!=0) --hash[n-1];
++hash[index[ch]];
}
else
{
int i=index[ch];
if(hash[i-1]==0) return -1;
++hash[i];
--hash[i-1];
}
}
for(int i=0;i<n-1;++i) if(hash[i]!=0) return -1;//最后还要再检查一次
return hash[n-1];
}
};写法2：只用一个数组模拟的哈希表，手动去控制字符和下标的映射关系（用switch语句）
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs)
{
//对于roak来说，判断前驱字符是否在哈希表中
//在就--前驱 ++当前 不在 返回1
//对于c来说，要判断k是否在哈希表中，如果在就--k然后++c 如果不在就直接++c
int hash[5]={0};//0 1 2 3 4 分别对应c r o a k
int n=croakOfFrogs.size();
for(int i=0;i<n;++i)
{
switch(croakOfFrogs[i])
{
case 'c':
if(hash[4]) --hash[4];
++hash[0];
break;
case 'r':
if(hash[0])
{
--hash[0];
++hash[1];
}
else return -1;
break;
case 'o':
if(hash[1])
{
--hash[1];
++hash[2];
}
else return -1;
break;
case 'a':
if(hash[2])
{
--hash[2];
++hash[3];
}
else return -1;
break;
case 'k':
if(hash[3])
{
--hash[3];
++hash[4];
}
else return -1;
break;
}
}
//检查一下hash的前面是否都为0
for(int i=0;i<4;++i) if(hash[i]) return -1;
return hash[4];
}
};七、频率跟踪器
. - 力扣（LeetCode）频率跟踪器
class FrequencyTracker {
public:
FrequencyTracker() :freq(N),freq_count(N){}
void add(int number)
{
--freq_count[freq[number]];//该数字原先次数的频率减少
++freq[number];//该数字次数增加
++freq_count[freq[number]];//该数字对应次数的频率增加（更新）
}
void deleteOne(int number)
{
if(freq[number]==0) return;//可能没出现过
//如果出现过，数字次数减少，原来频率要减少，先有频率要增加
--freq_count[freq[number]];//该数字原先次数的频率减少
--freq[number];//该数字次数减少
++freq_count[freq[number]];//该数字对应次数的频率增加（更新）
}
bool hasFrequency(int frequency) {return freq_count[frequency];}
private:
static const int N=100001;
vector<int> freq;//统计各个数字出现的次数
vector<int> freq_count;//统计各个频率的出现次数
};
