模拟算法题我们只需要按照题目的意思一步一步走，将这些步骤转换成代码即可
1.替换所有问号
题目要求将字符串中所有的问号都改为其他字母，但是要求不能与左右两边的字母重复，返回一种结果即可。
解法：
遍历原字符串，当遍历到问号时，我们遍历26个英文字母，找到既不与前面相同也不与后面相同的字母，修改该位置，继续遍历。在遍历的过程中需要注意首元素以及尾元素，它们只需要判断相邻的一个元素即可，要避免越界访问。
处理办法：
1、得知当前位置的元素是问号后，我们可以接着三目运算符求出左右字符，如果那一侧不存在，则随便给一个字符，但不可以是字母，其不影响结果
2、已知i位置当前字符是问号，在遍历26个英文字母时进行额外判断，如果i == 0,则没有左侧元素，如果i = n-1，则没有右侧元素.if (i == 0 || prev != ch) && (i == n-1 || next != ch )
时间复杂度：O(26n),遍历数组一遍，期间还遍历了26个英文字母
空间复杂度：O(1)，没有使用额外的空间
// C++class Solution
{
public:string modifyString(string s) {for(int i=0; i<s.size(); ++i){if(s[i] == '?'){char tmp1 = i-1<0?'0':s[i-1];char tmp2 = i+1>s.size()-1?'0':s[i+1];for(char ch='a'; ch<='z'; ++ch){if(ch != tmp1 && ch != tmp2){s[i] = ch;}}}}return s;}
};# pythonclass Solution:def modifyString(self, s: str) -> str:tmp = list(s)for i in range(0,len(tmp)):if tmp[i] == '?':for ch in range(ord('a'),ord('z')+1):j = chr(ch)if (i==0 or tmp[i-1]!=j) and (i==len(tmp)-1 or tmp[i+1]!=j):tmp[i] = jbreakreturn ''.join(tmp)2.提莫攻击
题目给我们一个timeSeries数组，里面存放的是提莫普攻的时间。提莫每普攻一次，就会使敌人中毒duration秒，如果在中毒结束之前又普攻了一次，此时就会重置中毒时间。我们需要返回总的中毒时间。
解法：
遍历数组，当遍历到一个时间后，我们给其加上中毒时间，如果该时间小于等于下一次普攻的时间，就不会重置中毒，此时只需要在总中毒时间上加上duration即可；如果大于中毒时间，则说明中毒还未结束，就又普攻了，需要重置中毒时间，此时中毒的时长就是两次普攻之间的间隔时间。
需要注意最后一次普攻，最后一次普攻一定会经历一次完整的中毒。所以加上duration。
时间复杂度：O(n)，遍历数组一次
空间复杂度：O(1)，没有使用额外的空间
// C++class Solution
{
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ret = 0;for(int i=0; i<timeSeries.size(); ++i){if(i == timeSeries.size()-1 || timeSeries[i]+duration <= timeSeries[i+1]){ret +=duration;}else{ret += timeSeries[i+1]-timeSeries[i];}}return ret;}
};# Pythonclass Solution:def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:ret = 0for i in range(0,len(timeSeries)):if i == len(timeSeries)-1 or timeSeries[i]+duration <= timeSeries[i+1]:ret += durationelse:ret += timeSeries[i+1]-timeSeries[i]return ret3.Z字型变换
将已知字符串，按照给出的行数进行重新排列。从左到右从上到下的返回重新排列后的字符串。
解法一：模拟
重新排列后的字符串是numRows行，列数不确定，但列数不可能超过s的长度。所以我们开一个numRows*s.size()的二维数组，来模拟排列原字符串的过程。排列之后，遍历这个二维数组，将里面的字符存到一个字符串中即可。
时间复杂度：O(n+numRows*n)，模拟排列需要遍历一遍原字符串，排列完成还需遍历二维数组。
空间复杂度：O(numRows*n)，开了一个二维数组
// C++class Solution
{
public:string convert(string s, int numRows){if(numRows == 1) return s;vector<vector<char>> vv(numRows, vector<char>(s.size()));int x = 0, y = 0, i = 0;while (i < s.size()){if (x < numRows){if (x == 0 && isalpha(vv[x][y]) || vv[x][y] == ',' || vv[x][y] == '.'){x++;}while (x < numRows && i<s.size()){vv[x++][y] = s[i++];}}else{if (x == numRows){x = numRows - 1;}while (x > 0 && i<s.size()){vv[--x][++y] = s[i++];}}}string ret;for (int i = 0; i < numRows; i++){for (int j = 0; j < s.size(); j++){char ch = vv[i][j];if (isalpha(ch) || ch == ',' || ch == '.'){ret.push_back(ch);}}}return ret;}
};解法二：找规律
表格中填字母不好观察规律，我们填入对应的下标。我们观察第一行和最后一行每一个字符的下标间隔都是相同，我们设为d。而这个d其实就是第一行第一个和第二个元素之间的元素个数。而这个元素个数，其实就是两个数列的格子，减去空的两个格子。即d = 2*numRows-2，该示例d = 4，并且第一行和最后一行相邻元素的下标差值的确为4.
第一行和最后一行有这样的规律，我们再观察中间行：对于下面这个示例来说，前两列有三个空格，那这个d的计算公式还符合么？其实我们可以将对角线的元素补到第二列，这样依旧是符合的，得d = 6
对于中间行来说，相邻的元素下标并没有关系，其实关系存在于1，3，5和2，4，6这几个位置处。奇数列的元素下标和偶数列的元素下标的差值为d。
有了上面这些规律，我们就不必创建一个二维数组来模拟排列的过程，只需要根据规律，先将第一行的元素插入到string中，然后是中间行，接着是最后一行。 中间行的下标于行数对应，且第一个奇数和第一个偶数下标和为d，我们可以由行数得出奇数下标，接着d-奇数下标求出偶数下标。
第一行和最后一行：0 -> 0+d -> 0+d+d -> 0+d+d+d……
中间行：(行数，d-行数) -> (行数+d，d-行数+d) -> (行数+d+d，d-行数+d+d)……
时间复杂度：O(numRows*n),n为s.size()，遍历层数时会遍历s的部分元素
空间复杂度：O(1)，并没有开额外的空间
// C++class Solution
{
public:string convert(string s, int numRows){if (numRows == 1)return s;int d = 2 * numRows - 2;string ret;for (int n = 0; n < numRows; n++) // 枚举Z型变换的每一行{if (n == 0 || n == numRows - 1){int i = n;while (i < s.size()){ret += s[i];i += d;}}else{int x1 = n, x2 = d - n;while (x1 < s.size() && x2 < s.size()){ret += s[x1];ret += s[x2];x1 += d;x2 += d;}// 此时循环结束，但是有可能只是一个判断失败了，但是x1失败了，x2一定失败，所以我们只需要在额外判断一下x1即可if (x1 < s.size()){ret += s[x1];x1 += d;}}}return ret;}
};# Pythonclass Solution:def convert(self, s: str, numRows: int) -> str:if numRows == 1:return sret = []d = 2*numRows-2for n in range(0,numRows): # 枚举Z型变换的每一行if n == 0 or n == numRows-1: # 第一行和最后一行性质相同i = nwhile i<len(s):ret.append(s[i])i += delse: # 中间行x1, x2 = n, d-nwhile x1<len(s) and x2<len(s):ret.append(s[x1])ret.append(s[x2])x1 += dx2 += dif x1 < len(s):ret.append(s[x1])return ''.join(ret)4.外观数列
行程长度编码会将连续相等的子串变成个数+字符的形式，比如："1111"四个1，就会变成"41"，以此类推。
而外观数列n是对n-1进行翻译，即n-1的行程长度编码。默认外观数列1 = 1，外观数列2就是外观数列1的行程长度编码，即1->11（1个1），外观数列3就是外观数列2的行程长度编码，即11->21（两个1）……
解法：
模拟替换的过程，接着双指针遍历原字符串，找到 left != right 的位置，此时right-left就是left字符出现的次数，保存，接着left移动到right的位置继续遍历，重复该过程。对于1来说，不需要模拟，对于2来说，需要模拟1次，所以我们需要模拟n-1次。
时间复杂度：O(n*M)，n为给出的已知整数，M为所形成的最长字符串
空间复杂度：O(M)，所形成的最大字符串的大小
// C++class Solution
{
public:string countAndSay(int n) {string ret = "1";for(int i=1; i<n; i++){string tmp;int sz = ret.size();for(int left=0,right=0;right<sz;){while(right < sz && ret[left] == ret[right]){right++;}tmp += (right-left)+'0';tmp += ret[left];left = right;}ret = tmp;}return ret;}
};# Pythonclass Solution:def countAndSay(self, n: int) -> str:ret = "1"for i in range(1,n):tmp = ""left,right = 0,0while right < len(ret):while right < len(ret) and ret[left] == ret[right]:right+=1tmp += str(right-left)tmp += ret[left]left = rightret = tmpreturn ret5.数青蛙
给定一个字符串，只包含croak这五个字母。如果一个青蛙完整的叫出croak这五个字母，就算完成一次蛙叫。我们需要返回这段字符串最少需要几个青蛙可以叫出来 。
示例一：croak是一声蛙叫，接着又是一声。因为这两声之间没有交叉，所以只需要一个青蛙就可以叫出来。
示例二：先来了一个青蛙叫了cr两个字母，接着又来个一个c，此时需要一个新的青蛙来叫，接着两个青蛙一次叫出croak。因为两个叫声重叠，所以得要两个青蛙才可以叫出来。
示例三：一个青蛙先叫一次，但是叫第二声时没有完整的叫出croak所以不是完整的蛙叫，返回-1.
解法：模拟+哈希表
当我们遍历字符串遇到r字符时，我们只需要看前面是否出现c即可，如果出现了，让c--，r++；如果遇到o，则判断前面是否出现了r字符，如果出现了，r--，o++……当我们遇到k，判断是否出现了a，如果出现了，则a--，k++。k就代表了完成了蛙叫的青蛙。
但是我们需要的是最少的青蛙，所以当我们遇到c时，我们不要直接让c++，而是看看有没有k，如果有k的话，说明已经有青蛙完成叫声了，它是闲着的，所以它可以继续叫，让k--，c++。当然还存在非法叫声的情况，如果我们在遍历roak这几个字符后，发现其前面的字符没有出现，则表明这是一个非法叫声，直接返回-1即可。
当遍历完字符串后，我们还需要进行判断，如果hash表中croa不为空，则还有蛙叫没有完成，也属于非法叫声，返回-1.
写法1：我们可以写5个if-else来解决
写法2：我们可以额外使用一个哈希表，来存储对应字符的下标，因为我们模拟的操作需要判断字符的前一个字符是否出现，所以有了对应字符的下标，我们就可以不使用if-else来实现逻辑
时间复杂度：O(n)，遍历一遍字符串
空间复杂度：O(k)，k表示蛙叫字符串的长度“croak”
// C++class Solution
{
public:// 写法二：int minNumberOfFrogs(string croakOfFrogs) {string temp = "croak";int n = temp.size();vector<int> hash(n); // 0~4分别映射c r o a kunordered_map<char,int> index; // 记录对应字符在hash中的下标for(int i=0; i<n; i++)index[temp[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<hash.size()-1; i++)if(hash[i] != 0) return -1; return hash[4];}// 写法一：if-elseint _minNumberOfFrogs(string croakOfFrogs) {int hash[5] = {0};// 0~4分别映射c r o a kfor(auto ch : croakOfFrogs){int flag = 0;if(ch == 'c'){flag = 1;if(hash[4] != 0) hash[4]--;hash[0]++;}else if(ch == 'r' && hash[0]){hash[1]++;hash[0]--;flag = 1;}else if(ch == 'o' && hash[1]){hash[2]++;hash[1]--;flag = 1;}else if(ch == 'a' && hash[2]){hash[3]++;hash[2]--;flag = 1;}else if(ch == 'k' && hash[3]){hash[4]++;hash[3]--;flag = 1;}if(flag == 0) return -1;}// 如果遍历完字符串，除k之外的其他字符仍出现了// 说明青蛙并没有完整的叫出声，返回-1if(hash[0]+hash[1]+hash[2]+hash[3]) return -1;return hash[4];}
};# Pythonclass Solution:def minNumberOfFrogs(self, croakOfFrogs: str) -> int:temp = "croak"n = len(temp)hash = [0]*n # 0~4 分别映射c r o a kindex = {} # 记录对应字符在哈希表中下标for i in range(0,n):index[temp[i]] = ifor e in croakOfFrogs:if e == 'c':if hash[n-1] != 0:hash[n-1] -= 1hash[0] += 1else:i = index[e]if hash[i-1]:hash[i-1] -= 1hash[i] += 1else:return -1for i in range(0,n-1):if hash[i] != 0:return -1return hash[n-1]
