![[LC优选算法#13] 模拟 | 替换所有的问号 | 提莫攻击 | Z字形变换](images/page-header-bg.jpg)
![[LC优选算法#13] 模拟 | 替换所有的问号 | 提莫攻击 | Z字形变换](http://pic.xiahunao.cn/yaotu/[LC优选算法#13] 模拟 | 替换所有的问号 | 提莫攻击 | Z字形变换)
顾名思义模拟就是比着葫芦画瓢即跟着题目的意思写代码思路较为简单。解决这类题的步骤为模拟算法流程画图和分析很重要一定要过一遍流程再写把流程转化为代码1. 替换所有的问号替换所有的问号解题思路模拟O(N) 从前往后遍历整个字符串遇到问号后尝试用a~z的每一个字符替换即可。注意点需要对首尾字符分类讨论因为首尾字符的两侧并不是都有字符不分类会越界访问。classSolution{public:stringmodifyString(string s){intns.size();for(inti0;in;i){if(s[i]?){for(charcha;chz;ch){//分类讨论if((i0||s[i-1]!ch)(in-1||s[i1]!ch)){s[i]ch;break;}}}}returns;}};2. 提莫攻击提莫攻击解题思路模拟 分类讨论计算相邻两个时间点的差值如果差值大于等于duration则说明实际中毒时间就是durantion。如果差值小于duration则中毒时间为差值。注意点特别留意变量的初始化和最后一次攻击的情况因为利用差值计算sum总时间时不会将最后一次攻击的时间计入因此要将sum初始化为duration。classSolution{public:intfindPoisonedDuration(vectorinttimeSeries,intduration){intsumduration;//最后一次intntimeSeries.size();for(inti1;in;i){if(timeSeries[i]-timeSeries[i-1]duration){sumduration;}else{sumtimeSeries[i]-timeSeries[i-1];}}returnsum;}};3. Z字形变换Z字形变换解题思路模拟填数最直接的解法就是模拟填入数据的过程按顺序一个个放入新的二维数组中再遍历数组得到新的字符串。时空复杂度均为O(s.size() * N)。模拟 找规律对于矩阵填数这类型的题我们都可以通过找规律来优化时空复杂度。首先用row表示行数找出填入数据对应下标的规律可以发现数据是以2*row-2为一个周期进行规律变换的以第四行为例可将所有数的下标用周期表示如上图。所以我们可以根据规律令d为2*row-2直接拼凑出需要返回的字符串classSolution{public:stringconvert(string s,intnumRows){intd2*(numRows-1);intns.size();string ret;if(numRows1)returns;//第一行for(inti0;in;id){rets[i];}//中间行for(intk1;knumRows-1;k){for(intik,jd-k;in||jn;id,jd){if(in){rets[i];}if(jn){rets[j];}}}//末尾行for(intinumRows-1;in;id){rets[i];}returnret;}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~
