刷题训练之模拟

news/2024/5/20 8:27:27

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握模拟算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：
模拟算法 == 依葫芦画瓢解题思维要么通俗易懂，要么就是找规律，主要难度在于将思路转换为代码。

特点：

相对于其他算法思维，思路比较简单（没有很多的弯弯绕绕，考察的是代码能力）。
大致做题流程：

模拟算法流程（一定要在演草纸上过一遍 - 容易忽略细节），把流程转换为代码

🌙topic-->1

题目链接：1.模拟-->力扣（LeetCode）

题目分析：

给一个字符串，替换该字符串全部的？字符，把该？修改成若干个小写字母，但是这个字符串不能有重复的小写字母。

算法原理：

解法：采用模拟是的思路讲解

图解：

代码演示：

class Solution
{
public:string modifyString(string s){int n = s.size();for (int i = 0; i < n; i++){if (s[i] == '?') // 替换{for (char ch = 'a'; ch <= 'z'; ch++) // 修改成小写字母{// 细节问题if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1])){s[i] = ch;break;}}}}return s;}
};

🌙topic-->2

题目链接：2.模拟 - 力扣（LeetCode）

题目分析：

题目说的是：给一个数组（这个数组的元素说明了在第几秒发出攻击），给一个 duration ，这个变量是攻击时产生被毒的时间，统计该人物被中毒的时间是多少。

算法原理：

解法：采用模拟是的思路讲解

图解：

代码演示：

class Solution 
{
public: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; // x > delse ret += tmp; // x < d}return ret + duration; // 最后一个元素加上 d}
};

🌙topic-->3

题目链接：3.模拟 - 力扣（LeetCode）

题目分析：

给一个字符串，根据给定的行数numRows，从上往下，从左到右 Z 字形排列。

算法原理：

解法一：创建一个二维数组，之后遍历字符串，时间复杂度为O(N²)，空间复杂度为O(N²)
解法二：采用模拟算法（本质上找规律，减少时间复杂度和空间复杂度）

图解：

代码演示：

class Solution 
{
public:string convert(string s, int numRows) {// 处理边界情况(只有一行)if(numRows == 1)return s;string ret;int d = 2 * numRows - 2;// 公差int n = s.size();// 字符个数// 处理第一行for(int i = 0;i < n;i += d)ret += s[i];// 处理 K 行for(int k = 1;k < numRows - 1;k++) // 枚举 k 行{for(int i = k,j = d - k; i < n || j < n;i += d,j +=d)// 两个元素{if(i < n)// 细节ret += s[i];if(j < n)// 细节ret += s[j];}}// 处理最后一行for(int i = numRows - 1;i < n;i += d)ret += s[i];// 返回return ret;}
};

🌙topic-->4

题目链接：4.模拟 - 力扣（LeetCode）

题目分析：

这个题目可能有点抽象，简单来说就是一个读数问题，如何读呢？

第一项：1

第二项我们就需要读第一项数字：一个一，简化为 11

第三项我们就需要读第二项数字：两个一，简化为21

第四项我们就需要读第三项数字：一个二，一个一，简化为：1211

.....

算法原理：

解法：采用模拟的算法 + 双指针算法

图解：

代码演示：

class Solution {
public:string countAndSay(int n) {// 初始字符串为 1 string ret = "1";// 循环 n-1 就可以了for(int i = 1;i < n;i++){string tmp; // 交换变量int len = ret.size(); // 计算当前字符串长度for(int left = 0,right = 0;right < len;) // 双指针算法{while(right < len && ret[left] == ret[right]) // 找到没有相同就可以追加了right++;tmp += to_string(right - left) + ret[left];// 不要忘记把自己追加上 ret[left]left = right;}ret = tmp;// 迭代}return ret;}
};

🌙topic-->5

题目链接：5.模拟 - 力扣（LeetCode）

题目分析：

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

算法原理：

解法：采用模拟的算法 + 哈希桶

图解：

代码演示：

class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs){string t = "croak";int n = t.size();vector<int> hash(n); // ⽤数组来模拟哈希表unordered_map<char, int> index; //[x, x这个字符对应的下标]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[0]++;}else{int i = index[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];}
};