相关题解
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提莫攻击
算法思路：
模拟 + 分情况讨论。
计算相邻两个时间点的差值：
- 若差值大于等于中毒时间，说明上次中毒可以持续 duration 秒；
- 若差值小于中毒时间，说明此时发生了中毒叠加，那么上次的中毒只能持续两者的差值。
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。
首末行规律相同，中间行规律相同。
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]; } };
