优选算法——模拟

👇作者其它专栏

《数据结构与算法》《算法》《C++起始之路》

相关题解

1.1替换所有的问号

算法思路：

模拟。从前往后遍历整个字符串，找到问号后，用a~z的每一个字符取尝试替换即可。

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; } };

2.2提莫攻击

算法思路：

模拟+分情况讨论。

计算相邻两个时间点的差值：

        i.若差值大于等于中毒时间，说明上次中毒可以持续duration秒；

        ii.若差值小于中毒时间，说明此时发生了中毒叠加，那么上次的中毒只能持续两者的差值。

class Solution { public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int ret=0; for(int i=1;i<timeSeries.size();i++){ int x=timeSeries[i]-timeSeries[i-1]; if(x<=duration) ret+=x; else ret+=duration; } //别忘记，最后一次的中毒也需要加上一个duration return ret+duration; } };

2.3Z 字形变换

算法思路（模拟+找思路）：

找规律，用row代替行数，row=4时画出的N字形如下：

可以发现，数据是以2row-2为一个周期进行规律变换的。将所有数替换成用周期来表示的变量：

第一行的数是：0，2row-2，4row-4；

第一行的数是：1，（2row-2）-1，（2row-2）+1，（4row-4）-1，（4row-4）+1；

第一行的数是：2，（2row-2）-2，（2row-2）+2，（4row-4）-2，（4row-4）+2；

第一行的数是：3，（2row-2）+3，（4row-4）+3。

第一行、第四行差为2row-2的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为（2n-1，2n）的数围绕（2row-2）的倍数左右取值。

即首末行规律相同，中间行规律相同。

class Solution { public: string convert(string s, int numRows) { //处理边界情况 if(numRows==1) return s; string ret; int d=2*numRows-2,n=s.size(); //1.处理第一行 for(int i=0;i<n;i+=d) ret+=s[i]; //2.处理中间行 for(int i=1;i<numRows-1;i++){//中间的每一行 for(int j=i,k=d-i;j<n||k<n;j+=d,k+=d){ if(j<n) ret+=s[j]; if(k<n) ret+=s[k]; } } //3.处理最后一行 for(int i=numRows-1;i<n;i+=d){ ret+=s[i]; } return ret; } };

2.4外观数列

算法思路：

【外观数列】，就是依次统计字符串中连续且相同的字符的个数。

class Solution { public: string countAndSay(int n) { string s("1"); n--;//循环n-1次 while(n--){ string tmp; int left=0,right=0,len=s.size(); while(right<len){ while(s[left]==s[right]&&right<len) right++; tmp+=to_string(right-left)+s[left]; left=right; } s=tmp; } return s; } };

2.5数青蛙

算法思路：

模拟青蛙叫声，两种情况：

●只有连续的发出叫声才算成功。当遇到'r''o''a''k'这四个字符时，我们要去查看每个字符对应的前驱字符，有没有青蛙交出来。若有青蛙叫出来，那就让这个青蛙接下来喊出这个字符；若没有，返回-1；

●因为要返回青蛙的最小个数，即同一青蛙可能叫多次。当遇到'c'字符时，我们需要查看'k'字符有没有青蛙叫出来，若有就让此青蛙继续去叫'c'；若没有，就重新添加青蛙。

class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string s="croak"; int n=s.size(); vector<int> hash(n);//数组模拟哈希表 unordered_map<char,int> index;//[x,x]表示这个字符的下标 for(int i=0;i<n;i++) index[s[i]]=i; for(auto ch:croakOfFrogs){ if(ch=='c'){ if(hash[n-1]>0) hash[n-1]--; hash[0]++; } else{ int i=index[ch]; if(hash[i-1]==0) return -1; hash[i-1]--;hash[i]++; } } for(int i=0;i<n-1;i++){ if(hash[i]!=0) return -1; } return hash[n-1]; } };