算法练习——模拟题

前言：模拟题的特点在于没有什么固定的技巧，完全考验自己的代码能力，因此有助于提升自己的代码水平。如果说一定有什么技巧的话，那就是有的模拟题能够通过找规律来简化算法。

一：替换所有问号

题目要求：

解题思路：

思路：首先遍历字符串s找寻字符 '?'；找到后，将'a'拷贝给该位置并循环++，直到中间字母和左右字母均不相同。

细节：左端点和右端点需要单独考虑

实现代码：

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

分析：if((i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1])); 该串代码

一个条件涵盖三种情况：

①：左端点 i == 0; ch != s[i+1];

②：右端点 i == n-1;ch !=s[i-1];

③：中间点 ch !=s[i-1];ch != s[i+1];

学无止境 :-(

二：提莫攻击

题目要求：

解题思路：

思路：

定义一个变量total，用于记录总共的中毒时间。

当攻击间隔 >= 中毒时间，total+=d;

当攻击间隔 <   中毒时间，total+=(攻击间隔的时间);

最后返回时，total+=d，因为最后一次的中毒时间一定是吃满的。

实现代码：

    int findPoisonedDuration(vector<int>& timeSeries, int duration) {int n = timeSeries.size();int total = 0;for(int i = 0; i < n-1; i++){int gap = timeSeries[i+1] - timeSeries[i];if(gap >= duration){total+=duration;}else{total += gap;}}return total+duration;}

三：Z字形变换

题目要求：

解题思路：

思路：这道题就是模拟题中典型的通过找规律来简化代码，以下通过下标来找寻规律。

实现代码：

    string convert(string s, int numRows) {if(numRows == 1) return s;int n = s.size();int gap = numRows*2 - 2;int gap1 = gap;int gap2 = 0;string tmp;for(int i = 1; i <= numRows; i++){int j = i-1;while((i == 1 || i == numRows) && j < n){tmp+=s[j];j+=gap; }while(i > 1 && i < numRows && j < n){tmp += s[j];j += gap1;if(j < n){tmp += s[j];j += gap2;}}gap1 -= 2;gap2 += 2;}return tmp;}

四：外观数列

题目要求：

解题思路：

分析：本题的难点(对编者我而言)在于把题目看懂

除了1，对于其他数字而言，下一个数字是对上一个数字的解释

即：

countAndSay(1) = '1';  

countAndSay(2) = "1" 的行程长度编码 = "11"       解释：一个1；

countAndSay(3) = "11" 的行程长度编码 = "21"     解释：一个2，一个1

countAndSay(4) = "21" 的行程长度编码 = "1211" 解释：一个1，一个2，两个1， 

最后输出n对应的行程长度编码。

思路：

定义一个变量 string s；

外循环遍历1~n，内循环遍历s，通过双指针法(pre cur)记录每个数字出现的次数，将数字以及其对应出现的个数分别记录到 string tmp中，当该次循环结束时，将 tmp 赋值给 s ，同时tmp清空tmp，用于记录下次循环的行程长度编码。

实现代码：

    string countAndSay(int n) {string s("1");for(int i = 1; i < n; i++){int pre = 0;int cur = 0;string tmp;while(cur < s.size()){int count = 0;while(cur < s.size() && s[cur] == s[pre]){count++;cur++;}tmp += to_string(count) + s[pre];pre = cur;}s = tmp;tmp.clear();}return s;}

to_string:将其他数据类型转换成string型

五：数青蛙

题目要求：

解题思路：

分析：

        每一只青蛙都必须叫出完整的一声 "croak"，但是可能存在示例2这样的情况，一只青蛙没叫完，另一只青蛙叫了。

        示例3不是有效的蛙声组合。因为一声完整的蛙声组合是 "croak"，也就是说o的前面一定有一个字符'r'，而示例3当连续两个o中，第一个o已经和前面一个r组成了一对，而第二个o前面没有r了，因此不符合蛙声("croak")的字符组合

       

思路：

👉：定义一个 string s; 用于保存蛙声“croak”，

👉：定义一个 unordered_map<char,int> haxi 让字母与下标建立映射关系，

注：此时 int index = haxi[字符] 就可以找到字符对应的下标

👉：定义一个 vector<int> tmp(s.size()) 下标从0开始到4，依次对应 c ~ k 五个字符以及其对应出现的个数

通过上述定义，就得到了如图所示的映射关系：

外循环遍历字符串croak0fFrogs

当遍历到除‘c’以外的其他字符时：判断 tmp中，前一个字符是否大于0

若大于0则，tmp[index]++; tmp[index-1]--;

若等于0则，说明当前字符串不是有效组合直接返回-1

循环结束时，此时 字符k的个数即为当前青蛙个数

当遍历到字符c时情况比较特殊:

①：如果k=0，说明这是某只青蛙第一次叫，tmp[index]++

②：如果k!=0，说明这可能是某只青蛙第二次叫，因此tmp[haxi[k]]--,tmp[index]++;

当上述循环结束时，要判断tmp中，除k以外是否存在其他字符，若存在，则返回-1。

实现代码：

        string s = "croak";int n = s.size();vector<int> tmp(n);unordered_map<char,int> haxi;for(int i = 0; i < n; i++){haxi[s[i]] = i; //建立哈希表中的映射关系}for(auto w : croakOfFrogs){int index = haxi[w];if(w == 'c'){if(tmp[n-1] > 0){tmp[n-1]--;  }tmp[0]++;}else{if(tmp[index-1] > 0){tmp[index-1]--;tmp[index]++;}else{return -1;}}}for(int i = 0; i < n-1; i++){if(tmp[i] > 0){return -1;}}return tmp[n-1];}

注：博主尚未学习haxi表，这道题是haxi算法的第一次浅尝试，通过哈希表建立字符与下标之间的映射关系，再通过vector<int> 统计个数。不同字符→对应下标→对应个数。