** 博主名称**迷途之人不知返 个人专栏: 《C语言》、《数据结构》、《C》、《Linux》️ Gitee仓库: 《C语言》、《数据结构》、《C》、《Linux》/ 算法专栏: 《算法精选集》模拟1 ··· 替换所有的问号2 ··· 提莫攻击3 ··· Z 字形变换4 ··· 外观数列4.1、题目理解4.2、原理分析4.3、代码演示5 ··· 数青蛙5.1、题目理解5.2、原理总结5.3、代码实现模拟的思想就是依葫芦画瓢即题目叫你做什么你就做什么。但是直接模拟有些情况下可能不是最优的解法。这时我们往往可以找规律。1 ··· 替换所有的问号替换所有的问号题目的要求有两个替换“?”成小写字母替换后的小写字母不能与相邻小写字母重复此时我们就可以遍历字符串s遇到“?”就开始替换不过我们要注意边界条件即串首与串尾classSolution{public:stringmodifyString(string s){intns.size();for(inti0;in;i)if(s[i]?)for(charcha;chz;ch){if((i0||ch!s[i-1])(in-1||ch!s[i1])){s[i]ch;break;}}returns;}};代码中if ((i 0 || ch ! s[i - 1]) (i n - 1 || ch ! s[i 1]))处理的就很巧妙如果i 0如果ch命中了ch ! s[i 1]那么就替换然后break寻找下一个“?”如果没命中ch就继续判断。如果i n - 1如果ch命中了ch ! s[i - 1]那么就替换然后break如果没命中ch就继续判断。其余的情况就可以判断ch与当前位置的左右两边是否相同。2 ··· 提莫攻击提莫攻击对于这道题我们来找一个规律假设有相邻两个攻击的时间点[a, b]差值为x b - a如果x duration说明在这两次攻击之间中毒效果持续了duration如果x duration说明在这两次攻击之间中毒效果只持续了x然后在时间点b时中毒效果的剩余持续时间又会刷新成duration。知道了这个规律那么我们就可以直接遍历timeSeries进行上面的处理得出中毒效果的总时间classSolution{public:intfindPoisonedDuration(vectorinttimeSeries,intduration){intret0;for(inti1;itimeSeries.size();i){intxtimeSeries[i]-timeSeries[i-1];ret(xduration)?duration:x;}returnretduration;// 最后的中毒时间是持续 duration 的要加上}};3 ··· Z 字形变换Z 字形变换对于这道题我们当然可以直接进行模拟即创建一个矩阵然后按要求填写矩阵最后按顺序做出要返回的字符串但是这样做时间复杂度和空间复杂度就太大了。对于“模拟”的题型要想优化我们可以来找规律。还是用上面的例子。我们把字符下标填进矩阵里对于第0行我们可以发现字符下标的规律是等差数列大胆猜想设相邻的公差为d那么有d 2 * numRows - 2那么我们就可以从i 0开始遍历原字符串每次 d 写入字符直到越界。同理。对于第numRows - 1行相邻也是相差d我们可以从i numRows - 1开始遍历原字符串每次 d 写入字符直到越界。对于中间行k行(1 k numRows - 1)从最左侧开始每相邻两个下标加和为k n*d (n 0, 1, 2, ...)我们就可以对每一行创建i j表示相邻的两个下标i k, j d - k开始遍历原字符串每次 d 只要i j其中一个没有越界都可以继续遍历写入的时候要判断是否越界。class Solution{public:stringconvert(string s,intnumRows){// numRows 1 的时候不用处理直接返回// 而且如果向下处理计算得出 d 0 处理第1行就会陷入死循环// 所以我们另外处理if(1numRows)returns;string ret;intd2*numRows-2,ns.size();// 1. 处理第1行for(inti0;in;id)rets[i];// 2. 处理第2行for(intk1;knumRows-1;k)for(intik,jd-k;in||jn;id,jd){if(in)rets[i];if(jn)rets[j];}// 3. 处理第3行for(intinumRows-1;in;id)rets[i];returnret;}};4 ··· 外观数列外观数列4.1、题目理解首先来理解“行程长度编码”。例如这里有一组源码进行编码3有3个编码33意为“3个3”5有2个编码25意为“2个5”4有4个编码446有1个编码167有2个编码278有1个编码18编码完成后结果其次来分析外观数组。当 n 1 外观数组定义为[1]当 n 2 对 n 1 时的外观数组做行程长度编码结果为[1, 1]当 n 3 对 n 2 时的外观数组做行程长度编码结果为[2, 1]当 n 4 对 n 3 时的外观数组做行程长度编码结果为[1, 2, 1, 1]当 n 5 对 n 4 时的外观数组做行程长度编码结果为[1, 1, 1, 2, 2, 1]当 n 6 对 n 5 时的外观数组做行程长度编码结果为[3, 1, 2, 2, 1, 1]……4.2、原理分析这道题的核心思路其实就是“模拟”即对上一个外观数组进行行程长度编码将编码结果作为新数组覆盖上一个外观数组。那么当务之急就是如何用编程语言完成行程长度编码的过程。我们随便创建一个数组做示范。我们可以采用双指针的策略right向前走遇到与left相同的数继续向前遇到与left不同的数停止。此时left指向的数就是要写入的数这样的数一共有right - left个。我们就可以写入字符串left来到right的位置right继续向前。重复操作直到right越界。(接下来的就不画了自己画吧)4.3、代码演示classSolution{public:stringcountAndSay(intn){string ret1;for(inti1;in;i)// n 1的情况做好了所以我们只需做n - 1次编码操作{string tmp;// 临时string变量存储每一次编码的结果intlenret.size();// 记录i - 1时外观数组的长度for(intleft0,right0;rightlen;){while(rightlenret[right]ret[left])right;tmpto_string(right-left)ret[left];// to_string()保证数字转换成字符串leftright;}rettmp;}returnret;}};5 ··· 数青蛙数青蛙5.1、题目理解比如我们有这样一个序列前面10个字符需要2个青蛙才能完整地叫出每一个“croak”但是对于最后一个“croak”由于之前已经有青蛙叫完了所以这个“croak”只需要由前面2个青蛙的其中1个交出来就可以。所以对于这个序列最少需要2只青蛙。5.2、原理总结我们另外建立一个存“croak”的哈希表。然后遍历给出序列做如下操作如果遇到c看哈希表里是否存在k如果存在k-- c如果不存在直接c如果遇到r o a k中的其中一个看前一个字符是否存在(比如遇到r就看c存在与否遇到a就看o存在与否)如果存在前--此如果不存在说明不能叫出正确的序列return -1遍历完成后我们还要检查哈希表如果有k之前的字符存在也说明不能叫出正确的序列return -1。(当然如果你还记得这道题的思路不妨蒙起上文自己举例遍历一遍然后自己做一个像上面一样的总结)5.3、代码实现我们当然可以写很多个if else但是那样不通用。(如果题目把固定的“croak”设置为可变的string变量传递进来呢)我们来实现一个通用的做法。首先是哈希表的制作(用数组模拟哈希表)这样定义哈希表我们就可以对当前字符字符映射到vector下标下标自减找到前一个字符就可以以一个通用的方法找到当前字符的前一个字符就不需要设计那么多if条件了。classSolution{public:intminNumberOfFrogs(string croakOfFrogs){string soundcroak;intlensound.size();// 1. 制作哈希表vectorinthash(len);unordered_mapchar,intindex;for(inti0;ilen;i)index[sound[i]]i;// 2. 遍历原序列按总结填表for(autoch:croakOfFrogs){if(sound[0]ch){// if (hash[map[sound[len - 1]]] ! 0) hash[map[sound[len - 1]]]--;// hash[map[ch]];if(hash[len-1]!0)hash[len-1]--;hash[0];}else{// if (hash[map[ch] - 1] 0) return -1;// else// {// hash[map[ch] - 1]--;// hash[map[ch]];// }intiindex[ch];if(hash[i-1]0)return-1;hash[i-1]--;hash[i];}}// 3. 填完表后检查是否还有除最后字符外的其它字符存在for(inti0;ilen-1;i)if(hash[i]!0)return-1;returnhash[len-1];// 返回最后字符出现的次数}};(保留了本人一开始尝试写代码的痕迹。可以对比学习老师写代码的思路)实际上对于可变的sound(不仅仅是“croak”)那么原理总结中c就是sound的首字符k就是sound的尾字符其它字符都是sound的中间字符