算法思想总结：模拟算法_算法模拟法总结

一、模拟算法的总结

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;//统计各个频率的出现次数
};