刷题训练之模拟

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

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

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

> 专栏选自：刷题训练营

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

🌟前言分析

最早博主续写了牛客网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 > d
			else 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];
	}
};