目录
- 一、什么是模拟
- 二、模拟算法的特点和技巧
- 三、模拟OJ题
- 3.1、替换所有的问号
- 3.2、提莫攻击
- 3.3、N字形变换
- 3.4、外观数列
- 3.5、数青蛙
一、什么是模拟
模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能,可以用语言来模拟那个功能,模拟成功也就相应地表示编程成功。
二、模拟算法的特点和技巧
特点:
-
代码量大
-
操作多
-
思路复杂
-
较为复杂的模拟题出错后难定位错误
技巧:
-
在动手写代码之前,在草纸上尽可能地写好要实现的流程.
-
在代码中,尽量把每个部分模块化,写成函数、结构体或类
-
对于一些可能重复用到的概念,可以统一转化,方便处理:如,某题给你"YY-MM-DD 时:分" 把它抽取到一个函数,处理成秒,会减少概念混淆
-
调试时分块调试。模块化的好处就是可以方便的单独调某一部分
-
写代码的时候一定要思路清晰,不要想到什么写什么,要按照落在纸上的步骤写
三、模拟OJ题
3.1、替换所有的问号
1576. 替换所有的问号
算法思路
纯模拟。从前往后遍历整个字符串,找到问号之后,就⽤ a ~ z 的每⼀个字符去尝试替换即可。
算法代码
class Solution {
public:string modifyString(string s) {for(int i = 0; i<s.size(); i++)//遍历每一个字符{if(s[i] == '?'){for(char ch = 'a'; ch <= 'z'; ch++)//a ~ z都试试{if(i == 0 && ch != s[i+1]) //头位置是'?',不能和后一个相等s[i] = ch;else if(i == s.size()-1 && ch != s[i-1])//尾位置是'?' ,不能和前一个相等s[i] = ch;else if(ch != s[i+1] && ch != s[i-1]) //中间情况, 不能和两边相等s[i] = ch;}}}return s;}
};
3.2、提莫攻击
495. 提莫攻击
算法思路
模拟 + 分情况讨论。
计算相邻两个时间点的差值:
-
i. 如果差值 ⼤于等于 中毒时间,说明上次中毒可以持续 duration 秒;
-
ii. 如果差值 ⼩于 中毒时间,那么上次的中毒只能持续两者的差值。
算法代码
class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans = 0;for(int i = 0; i<timeSeries.size(); i++) //遍历每一个中毒time,计算差值与duration比较{// 如果差值 ⼤于等于 中毒时间,说明上次中毒可以持续 duration 秒,if(i + 1 < timeSeries.size() && timeSeries[i+1] - timeSeries[i] >= duration)ans+=duration;//如果差值 ⼩于 中毒时间,那么上次的中毒只能持续两者的差值//因为中毒中不完,到下个时间就会重置,这轮中毒时间就是两者的差值if(i + 1 < timeSeries.size() && timeSeries[i+1] - timeSeries[i] < duration)ans+=timeSeries[i+1] - timeSeries[i];}ans+=duration; //最后还需要加一个duration,因为最后一次攻击的中毒时间可以全部中毒完return ans;}
};
3.3、N字形变换
Z 字形变换
- 对于前面的 3 行的 示例1 , 它的字符数分布是这样的
- 对于前面的 4 行的 示例2 , 它的字符数分布是这样的:
- 那么对于 n 行的字符数分布是这样的:
如上图所示,我们可以发现:
公差为 2n - 2
-
当前行 curRow 为 0 时 ,下标变化是 0 -> 0+d -> 0+2d -> … ->0+kd;
-
当前行 curRow 为 n-1 时 ,下标变化是n-1 -> n-1+d -> n-1+2d -> … ->n-1+kd;
-
当前行 curRow 为 k 时 ,下标变化是( k , d-k ) -> ( k+d , d-k+d ) -> ( k+ 2d, d-k+2d ) -> …
算法代码
class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;int d = 2 * numRows - 2; //公差d = 2n-1string ret;for(int i = 0; i<s.size(); i+=d) //当前行 curRow 为 0 ret += s[i];for(int k = 1; k<numRows-1; k++) //当前行 curRow 为 k{//( k , d-k ) -> ( k+d , d-k+d ) -> ( k+ 2d, d-k+2d ) -> .....for(int i = k ,j = d - k; i < s.size() || j < s.size(); i+=d,j+=d){if(i < s.size()) ret+=s[i];if(j < s.size()) ret+=s[j];}}for(int i = numRows-1; i<s.size(); i+=d) //当前行 curRow 为 n-1ret+=s[i];return ret;}
};
3.4、外观数列
38. 外观数列
算法思路
所谓「外观数列」,其实只是依次统计字符串中连续且相同的字符的个数。依照题意,依次模拟即可。
算法代码
class Solution {
public:string countAndSay(int n) {string ret = "1" ; //countAndSay(1) = "1"for(int i = 1; i<n; i++)//循环n-1次{string tmp; //用tmp暂存,进行替换int left = 0 ,right = 0;while(right < ret.size()) //right出ret,双指针结束{while(ret[right] == ret[left]) right++; //到不相等的那个数结束//然后加上有几个这个数 right - left,再加上这个数本身tmp+= to_string(right-left);tmp+= ret[left];left = right;//更新left位置,进行下一次双指针}ret = tmp; //更新ret,进行下一次循环}return ret;}
};
3.5、数青蛙
1419. 数青蛙
算法思路
将青蛙分成 5 种:
- 刚才发出了 c 的声音。
- 刚才发出了 r 的声音。
- 刚才发出了 o 的声音。
- 刚才发出了 a 的声音。
- 刚才发出了 k 的声音。
遍历 croakOfFrogs,例如当前遍历到 r,那么就看看有没有青蛙刚才发出了 c 的声音,如果有,那么让它接着发出 r 的声音。换句话说,我们需要消耗一个 c,产生一个 r。
所以我们使用一个哈希表(数组)hash 来维护这 5 种青蛙的个数,并分类讨论:
-
遍历到 c 时,看看有没有青蛙刚才发出了 k 的声音,如果有,那么复用这只青蛙,让它接着发出 c 的声音,即 hash[‘k’]-- 和 hash[‘c’]++;如果没有这种青蛙,那么新产生一只青蛙发出 c 的声音,即 hash[‘c’]++。
-
遍历到 r , o,a,k ,找到该字母在 croak 的上一个字母的 hash 值,如果 hash 值大于 0,那么将其减一,同时当前字母的 hash 值加一;如果上一个字母的 hash 值等于 0,那么就返回 −1。
-
遍历结束后,所有青蛙必须在最后发出 k 的声音。如果有青蛙在最后发出的声音不是 k(也就是 cnt 值大于 0),那么返回 −1,否则返回 hash[k]。
算法代码
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";vector<int> hash(t.size()); //[0,4]对应crock ,各个个数unordered_map<char,int> index; //[x,x这个字符对应的下标]for(int i = 0; i<t.size(); i++)index[t[i]] = i; //存[x,x这个字符对应的下标]for(auto ch : croakOfFrogs) //遍历{if(ch == 'c'){//看看有没有青蛙刚才发出了 k 的声音,如果有,那么复用这只青蛙 ,k--,c++;if(hash[4] != 0) hash[4]--; hash[0]++;}else{int i = index[ch];//找出roak对应的下标if(hash[i-1] == 0) return -1; //找到该字母在 croak 的上一个字母的值,非0直接错hash[i-1]--; //不是0就--hash[i]++; //这个字母对应的数++,为了判断下一个字母}}//所有青蛙必须在最后发出 k 的声音。如果有青蛙在最后发出的声音不是 k,那么返回 −1。for(int i = 0; i<t.size()-1; i++) {if(hash[i] != 0)return -1;}return hash[t.size()-1];//返回}
};