一、模拟算法的总结
1、本质：比葫芦画瓢
2、特点：思路较简单，根据题目要求即可，代码量和细节较多
3、解决方法：
（1） 模拟算法流程，在草稿纸上进行演算
（2） 认真审题，考虑细节问题和边界情况
（3） 一步步将流程转化为代码
二、替换所有的问号
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; } };
三、提莫攻击
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字形变换
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; } };
五、外观数列
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; } };
六、数青蛙
写法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]; } };
七、频率跟踪器
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;//统计各个频率的出现次数 };
