【算法学习】模拟篇：模拟算法的原理和习题讲解

GG Bond1

发布于 2025-03-25 13:31:08

6800

代码可运行

文章被收录于专栏：C/C++葵花宝典C/C++葵花宝典

运行总次数：0

代码可运行

1. 模拟题做法

就如我们前言中所讲的那样，模拟题对算法的考察并不太深，更多的考察我们对题意的理解，所以我们在写模拟类的题时，我们可以把模拟流程画在草稿纸上，同时我们需要熟练使用各种STL容器及一些常用的容器适配器

2. 经典模拟题

下面的题都是leetcode上的经典题，各位看完题解后可以自己去尝试尝试后再来看代码

2.1 替代所有的问号

1576. 替换所有的问号

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你不能修改非 '?' 字符。

题目测试用例保证除 '?' 字符之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符

解法：

这个就非常简单，我们只需要遍历这个字符串，当遇到 '?' 时，让这个字符变成一个小写字母，且不能与前面和后面的相等，要注意边界问题，比如当i==0时或i位于字符串最后一个位置时

代码实现：

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;
                }
            }
        }
        return s;
    }
};

2.2 Z字形变换

6. Z 字形变换

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

解法：

解释:我们可以将下标多列出来找规律，然后我们就会发现字符串中的字符实际上在Z字形中是每过2n-2个为一轮的，首行和尾行都是每过d个才会出现一次，但是中间行在一个周期中会出现两次，且这两次出现的顺序相加为d的倍速

代码实现：

class Solution {
public:
    string convert(string s, int numRows) {
        string ret;
        int n=s.size();
        if(numRows==1) return s;
        int d=2*(numRows-1);
        for(int i=0;i<n;i+=d)
        {
            ret+=s[i];
        }
        for(int i=1;i<numRows-1;i++)
        {
            for(int k1=i,k2=d-k1;k1<n||k2<n;k1+=d,k2+=d)
            {
                if(k1<n) ret+=s[k1];
                if(k2<n) ret+=s[k2];
            }
        }
        for(int i=numRows-1;i<n;i+=d)
        {
            ret+=s[i];
        }
        return ret;
    }
};

2.3 外观数列

38. 外观数列

「外观数列」是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

输入：n = 4

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

示例 2：

输入：n = 1

输出："1"

解释：

这是基本情况。

提示：

1 <= n <= 30

解法：

解释：本题我们可以采用双指针的做法，让left和right都先从头开始，当后面几个数字都相同时，让right一直++，直到遇到另一个数字为止，然后计算一下有相同的数字后，让left也来到right的位置

代码实现：

class Solution {
public:
    string countAndSay(int n) {
        string ret="1";
        for(int i=0;i<n-1;i++)
        {
            string tmp;
            for(int j=0;j<ret.size();)
            {
                int count=1;
                while(j+1<ret.size()&&ret[j]==ret[j+1])
                {
                    count++;
                    j++;
                }
                tmp=tmp+to_string(count)+ret[j];
                j++;
            }
            ret=tmp;
        }
        return ret;
    }
};

2.4 数青蛙

1419. 数青蛙

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

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 "croak"，青蛙必须依序输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

提示：

1 <= croakOfFrogs.length <= 105
字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

解法：

本题就需要我们借助哈希表来实现，我们按照上面总结的那样，每遇到一个字符时，我们要先判断它前面字符存不存在以及个数，从而判断是否是合规的蛙叫，同时我们要注意到题目中要求的是求最少的青蛙数量，一个青蛙在完成一次蛙叫之后是可以继续叫的

代码实现：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s="croak";
        int n1=croakOfFrogs.size();
        int n2=s.size();
        vector<int> hash(n2);
        unordered_map<char,int> mp;
        for(int i=0;i<n2;i++)
        {
            mp[s[i]]=i;
        }
        for(auto e:croakOfFrogs)
        {
            if(e=='c')
            {
                if(hash[n2-1]!=0) hash[n2-1]--;
                hash[0]++;
            }
            else
            {
                int index=mp[e];
                if(hash[index-1]==0) return -1;
                hash[index-1]--;
                hash[index]++;
            }
        }
        for(int i=0;i<n2-1;i++)
        if(hash[i]!=0) return -1;
        return hash[n2-1];
    }
};