模拟 - #介绍 #题解
系列文章目录
- leetcode - 双指针问题_leetcode双指针题目-CSDN博客
- leetcode - 滑动窗口问题集_leetcode 滑动窗口-CSDN博客
- 高效掌握二分查找：从基础到进阶-CSDN博客
- leetcode - 前缀和_前缀和的题目-CSDN博客
- 动态规划 - 斐波那契数列模型-CSDN博客
- 位运算 #常见位运算总结 #题解-CSDN博客
文章目录
目录
系列文章目录
文章目录
前言
一、什么是模拟
二、题解
1、题1 替换所有的问号：
解法：模拟
参考代码1：
参考代码2：
2、题目2 提莫攻击：
解法：模拟
参考代码：
3、题3 Z 字形变换 ：
解法一：模拟
参考代码：
解法二：找规律
参考代码：
4、题4 外观数列 ：
解法：模拟实现
参考代码：
5、题五 数青蛙 ：
解法：模拟
参考代码：
总结
前言
路漫漫其修远兮，吾将上下而求索；
大家可以自己先做一下喔~
1576. 替换所有的问号 - 力扣（LeetCode）
495. 提莫攻击 - 力扣（LeetCode）
6. Z 字形变换 - 力扣（LeetCode）
38. 外观数列 - 力扣（LeetCode）
1419. 数青蛙 - 力扣（LeetCode）
一、什么是模拟
通俗来讲，模拟就是照葫芦画瓢；即根据题干已经告诉我们的思路来转换成代码来解决这些问题；
模拟题的特点：这类题比较简单，考察的就是我们的代码能力
做模拟题的一般过程：
- 1、先模拟算法流程；千万不能凭空想象，需要实际在草稿纸上过一遍思路，不然容易忽略细节问题；
- 2、将思路流程转换成代码；
二、题解
1、题1 替换所有的问号：
1576. 替换所有的问号 - 力扣（LeetCode）
解法：模拟
题意：将字符串中所有为 '?' 的字符转换成小写字母，并且还需要保证字符串中没有连续重复的字符；
遍历 + 替换 ： 从前往后扫描该数组，如若遇到问号则从 'a' 到 'z' 依次尝试放在该位置是否合适（不与相邻的字符相同）
细节处理：当问号在第一个的时候，只需要与其后一个字符进行比较；当问号在最后一个的时候，只需要与其一个字符进行比较；
参考代码1：
string modifyString(string s) {//遍历+替换int n = s.size();for(int i = 0;i<n;i++){if(s[i]=='?'){//替换for(int j = 'a';j<='z';j++){//判断//细节处理，第一个以及最后一个if(i==0 || i==n-1) {if((i==0 && s[i+1]!=j) || (i==n-1 && s[i-1]!=j)){ s[i] = j;break;}}else//中间的{if(s[i-1]!=j && s[i+1]!=j){s[i] = j;break;}}}}}return s;}代码1有点冗余，我们可以巧妙利用 && 与 || 的逻辑进行优化；
参考代码2：
string modifyString(string s) {//遍历+替换int n = s.size();for(int i = 0;i<n;i++){if(s[i]=='?'){//替换for(int j = 'a';j<='z';j++){//判断if((i==0 || s[i-1]!=j) && (i==n-1 || s[i+1]!=j)){ s[i] = j;break;}}}}return s;}2、题目2 提莫攻击：
495. 提莫攻击 - 力扣（LeetCode）
解法：模拟
讲解算法原理：当两个时间点（假设为a、b点）的差值大于等于中毒时间（假设中毒实现为d）的时候，说明在 a 点受到攻击之后，接下来在 b 前中毒之前可以恢复，那么中毒状态为 d秒；
而当两个时间点的查找小于 d 的时候，说明在a 点受到攻击之后接下来在 b 点中毒之前不可以恢复，那么此时中毒状态为 b-a ；
细节处理：如果最后一次中毒，直接加上 d 秒即可；
参考代码：
int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ret = 0;for(int i = 1;i<timeSeries.size();i++){int tmp = timeSeries[i]-timeSeries[i-1];if(tmp >= duration) ret += duration;else ret+=tmp;}//处理最后一次中毒return ret + duration;}3、题3 Z 字形变换 ：
6. Z 字形变换 - 力扣（LeetCode）
解法一：模拟
首先将字符串按照题干中的要求放入矩阵之中，然后再一行一行地从矩阵中读取数据；
Q：矩阵地大小如何确定？
- 行，开辟字符串的长度肯定是没有问题的；列，题干中会给；
参考代码：
string convert(string s, int numRows) {//完全按照题干的思路来实现vector<vector<char>> nums(numRows,vector<char>(s.size() ,' '));//char 类型的二维数组。用空格初始化//将数据放入nums 中//先放第一列int i = 0, j = 0;//nums 中的指针int sz = 0;//s 中的指针while(s[sz]!='\0' && i < numRows){nums[i][j] = s[sz++];i++;}j++;//第二列while(s[sz]!='\0' ){//判断是需要填一列，还是填一个//numRows 可能为1，需要先判断一下int n = numRows-1;if(n==0)//填一列，即nusRows 个{i = 0;while(s[sz]!='\0' && i<numRows){nums[i++][j] = s[sz];sz++;}j++;}while(n--){if(n==0)//填一列{i = 0;while(s[sz]!='\0' && i<numRows){nums[i++][j] = s[sz];sz++;}j++;}else//填一个{if(s[sz]!='\0') nums[n][j++] = s[sz++];}}}//读取nums 中的数据string ret;for(int x = 0;x < numRows;x++){for(int y = 0;y<s.size();y++){if(nums[x][y] !=' ') ret += nums[x][y];}}return ret;}这种解法的时间、空间复杂度为：O(N*len);效率不太好；
如何在模拟的策略上进行优化？
- 大多数的模拟题的优化策略均是找规律!
Q:如何找规律？
- 最好将原始的模型结果画出来，然后根据画出来的最终结果来反推规律；当推出来的一个规律的时候，再换一种规律来验证我们的这个规律是否正确；当我们通过了两个例子来验证我们的规律是否正确的时候，此时便可以上手写代码了；
解法二：找规律
eg. n = 4;
第一行： 0 -> d+0 -> d+d+0 -> ...
假设公差为d:
显然d = 2*n -2 = 6;所以 d 的计算公式为 2*n -2;
第二行：
第三行：
假设第一个数为k;
第1~n-2 行 ：两两向后递进：(k,d-k) -> (k+d,d-k+d) -> (k+d+d, d-k+d+d) -> (k+d+d+d,d-k+d+d+d) -> ...
简化一下： (k,d-k) -> (k+d,2d-k) -> (k+2d,3d-k) -> (k+3d,4d-k) -> ...
第四行：
第 n 行：n-1 -> n-1 + d -> n-1 + 2d -> ... n-1+xd
需要确保 n-1 + xd < s.size() 就可以了；
找到规律之后，我们需要验证一下：当 n 为3 ， 是否还符合此规律：
我们再思考一下比较特殊的情况，是否会符合上述的规律：而当 n 为 1 的时候， d = 0; 不符合上述逻辑，需要特殊处理；
参考代码：
string convert(string s, int n) {//边界情况处理if(n==1) return s;//根据规律进行优化string ret;int d = 2*n - 2;//第一行 for(int i =0;i<s.size();i+=d) ret+=s[i];//中间行 1~n-2 行for(int k = 1;k<=n-2;k++)//枚举每一行{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 = n-1;i<s.size();i+=d) ret+=s[i];return ret; }4、题4 外观数列 ：
38. 外观数列 - 力扣（LeetCode）
解法：模拟实现
Q：如何“解释”字符串？
- 找到一个连续的字符串部分就需要进行解释，找到相同的字符串部分就进行解释……
利用双指针；
参考代码：
string countAndSay(int n) {//个数+字符，模拟实现string ret = "1";for(int i = 1;i<n;i++)//执行n-1 次{string tmp;int len = ret.size();//双指针for(int left = 0, right = 0; right < len; ){//left 和 right 锁定区间while(right < len && ret[right]==ret[left]) right++;//走到此处就说明，right - left 的结果是 ret[left]字符的个数tmp+=to_string(right-left) + ret[left];left = right;//继续迭代}ret = tmp;//继续迭代}return ret;}5、题五 数青蛙 ：
1419. 数青蛙 - 力扣（LeetCode）
解法：模拟
当遍历到 r 字符的时候，仅需要看前面是否有青蛙叫出 'c' 这个字符……同理，遍历到 'o' 字符，仅需要看前面是否有青蛙叫出 'r' 这个字符……
显然，本题在模拟的过程之中需要时刻统计出来前面的这些字符出现的情况；为了提高效率，我们可以借助于哈希表来实现；
思路总结：
参考代码：
int minNumberOfFrogs(string croakOfFrogs) {//利用hash 来统计，提高效率int hash[5] = {0};//下标映射对应 c r o a k //再使用unordered_map 来记录下标与字符的映射关系unordered_map<char,int> index;string t = "croak";//将“croak” 放入hash 中int n = t.size();for(int i = 0;i<n;i++) index[t[i]] = i;//遍历目标字符串for(auto ch : croakOfFrogs){if(ch == 'c') //先看是否有青蛙刚好叫完{if(hash[n-1] != 0) hash[n-1]--;hash[index[ch]]++;}else// r o a k{//判断前驱字符是否存在int i = index[ch];if(hash[i-1] == 0) return -1;//没有前驱字符直接返回 -1else{hash[i-1]--;hash[i]++;}}}//走完了，还需要判断hash 中 'k' 前面的是否均为0for(int i = 0;i<n-1;i++){if(hash[i]) return -1;}return hash[n-1];}总结
模拟题的关键在于：
1. 先在草稿纸上模拟算法流程
2. 注意边界条件处理
3. 寻找优化规律
4. 将思路转换为代码