算法思想总结：模拟算法

一、模拟算法的总结

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& timeSeries, int duration) { //x=b-a x>d ret+=d x<==d ret+=x int ret=0;//记录返回时间 int n=timeSeries.size(); for(int i=1;iduration) ret+=duration;  else ret+=x; } 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; //先搞第一行 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]; } 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;left=right){//每组都要更新left while(right<len&&ret[right]==ret[left]) ++right; //此时right指向的是下一组 temp+=to_string(right-left)+ret[left]; } //走到这temp就是下一组 赋值给ret ret=temp; } return ret; }};

六、数青蛙

. - 力扣（LeetCode）数青蛙

 写法1： 两个哈希表  一个存储字符和下标的映射关系，另一个用数组模拟哈希表存字符出现的次数。

class Solution {public: int minNumberOfFrogs(string croakOfFrogs) { string t=\"croak\"; unordered_map index;//存映射关系 for(int i=0;i<5;++i) index[t[i]]=i; int hash[5]={};//用来存储字符信息 for(auto&ch:croakOfFrogs)//开始研究字符串 if(ch==\'c\'){ if(hash[4]) --hash[4]; ++hash[0];  }  else{ int i=index[ch]; if(hash[i-1]==0) return -1; ++hash[i]; --hash[i-1]; } for(int i=0;i<4;++i) if(hash[i]) return -1;//可能最后会少几个字母 return hash[4]; }};

写法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 freq;//统计各个数字出现的次数 vector freq_count;//统计各个频率的出现次数};