【算法通关】模拟：替换问号、提莫攻击、Z 字形变换、外观数列、数青蛙全解
文章目录
1. 替换所有的问号
题目链接：1576. 替换所有的问号
题目描述：
算法思路：
从前向后遍历整个字符串，当遇到？时就从字母a 开始遍历 到z，找到与？前和后不重复的即可。
算法代码：
publicStringmodifyString(String s){char[] chars = s.toCharArray();int n = chars.length;for(int i =0; i < n; i++){if(chars[i]=='?'){for(char ch ='a'; ch <='z'; ch++){if((i ==0|| ch != chars[i-1])&&(i == n-1|| ch != chars[i+1])){ chars[i]= ch;break;}}}}returnString.valueOf(chars);}2. 提莫攻击
题目链接：495. 提莫攻击
题目描述：
算法思路：
模拟题目描述+分情况讨论：计算相邻两个时间点的差值，当差值大于等于中毒时间，说明上次中毒时间可以持续 duration；如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。
算法代码：
publicintfindPoisonedDuration(int[] timeSeries,int duration){int n = timeSeries.length;int ret =0;for(int i =0; i < n -1; i++){int x = timeSeries[i+1]- timeSeries[i];if(x >= duration) ret += duration;else ret += x;}return ret += duration;}3. Z 字形变换
题目链接：6. Z 字形变换
题目描述：
算法思路：
该题的z字形是呈现一个横着的z字。可以找到其中的规律，每一个字符间以2*row-2 的公差进行变换。那么可以得到第一行和最后一行是差为2row-2的等差数列；而中间行也是为该公差的等差数列，但是多了一个数据。而中间行前两个数相加刚好为公差，可以得到 k 行刚好是（k，d-k）的两个等差数列。
算法代码：
publicStringconvert(String s,int numRows){if(numRows ==1)return s;int d =2* numRows -2, n = s.length();StringBuilder ret =newStringBuilder();for(int i =0; i < n; i += d){ ret.append(s.charAt(i));}for(int k =1; k < numRows -1; k++){for(int i = k, j = d - k; i < n || j < n; i += d, j += d){if(i < n) ret.append(s.charAt(i));if(j < n) ret.append(s.charAt(j));}}for(int k = numRows-1; k < n; k += d){ ret.append(s.charAt(k));}return ret.toString();}4. 外观数列
题目链接：38. 外观数列
题目描述：
算法思路：
模拟+双指针，依次统计字符中连续相等的字符的个数，right 移动到与left 不相等时，记录right - left 并加上left 的值，然后left 指向right 再继续这个操作即可。
算法代码：
publicStringcountAndSay(int n){String ret ="1";for(int i =1; i < n; i++){StringBuilder tmp =newStringBuilder();int len = ret.length();for(int left =0, right =0; right < len;){while(right < len && ret.charAt(left)== ret.charAt(right)) right++; tmp.append(Integer.toString(right-left)); tmp.append(ret.charAt(left)); left = right;} ret = tmp.toString();}return ret;}5. 数青蛙
题目链接：1419. 数青蛙
题目描述：
算法思路：
模拟+哈希表，使用数组代替哈希表存放蛙鸣声字符的次数，并且元素与下标进行对应，哈希表中存放元素与对应的下标；遍历字符，当遇到开头元素 c 时，判断哈希表k元素中是否有值，如果有则将k-1表示该青蛙再次鸣叫，且哈希表c+1，没有则只让c+1，当遇到其他roak时，则判断前一个元素下是否有值，没有则返回-1，有则前一个元素–，当前元素++，当遇到k时，让k进行累加，最后返回k下的值即可。
算法代码：
publicintminNumberOfFrogs(String c){char[] croakOfFrogs = c.toCharArray();String str ="croak";int n = str.length();int[] hash =newint[n];Map<Character,Integer> index =newHashMap<>();for(int i =0; i < n; i++) index.put(str.charAt(i),i);for(char ch : croakOfFrogs){if(ch == str.charAt(0)){if(hash[n-1]!=0) hash[n-1]--; hash[0]++;}else{int i = index.get(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];}
