算法模拟法解题实战

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