模拟篇——算法浮世绘，探寻模拟之境的计算艺术（2）

用户11379153

发布于 2025-11-05 15:48:59

870

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

前言

上篇我们介绍了模拟算法的原理概念及部分基础题型，本篇将结合进阶题目，深化对于模拟算法的理解运用。

一. 外观数列

1.1 题目链接：https://leetcode.cn/problems/count-and-say/description/

1.2 题目分析：

题目要求按规则返回字符串，元素n代表需要阐述n次，其中每一次都是对上一次元素内容的说明。例如1->1 2->11 3->21

1.3 思路讲解：

所谓「外观数列」，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。

1.4 代码实现：

class Solution {
public:
    string countAndSay(int n) {
        string ret="1";
        //需要解释n-1次
        for(int i=1;i<n;i++)
        {
            string temp;
            int len=ret.size();
            for(int left=0,right=0;right<len;)
            {
                while(right<len&&ret[left]==ret[right])
                {
                    right++;
                }//相同元素的个数
                temp+=(to_string(right-left))+ret[left];
                left=right;//更新left
            }
            ret=temp;//更新每一次解释结果
        }
        return ret;
        
    }
};

二. 数青蛙

2.1 题目链接：https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/

2.2 题目分析：

croak单词代表蛙鸣，青蛙必须按顺序c,r,o,a,k依次鸣叫，如果字符串不符合鸣叫顺序，则直接返回-1
同一时间可以有多只青蛙鸣叫
单只青蛙完成本次鸣叫后可以继续鸣叫
求取完成鸣叫所需的最少青蛙数目

2.3 思路讲解：

模拟青蛙的叫声：

当遇到 ‘r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有，直接返回 -1 ；
当遇到 ‘c’ 这个字符的时候，我们去看看 ‘k’ 这个字符有没有⻘蛙叫出来。如果有，就让这个⻘蛙继续去喊 ‘c’ 这个字符；如果没有的话，就需要再来⼀个⻘蛙。

具体步骤如下：

创建一个哈希表用来记录字符及其前驱字符的鸣叫情况
利用croak的下标与哈希表映射对应，分情况一一判断

1.4 代码实现：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t="croak";
        int n=t.size();
        vector<int> hash(n);//记录
        unordered_map<char,int> index;//记录字符下标
       for(int i=0;i<n;i++)
       {
         index[t[i]]=i;
       }//index与下标一一对应
       for(auto e:croakOfFrogs)
       {
        if(e=='c')
        {
            if(hash[4]>0)
            {
                hash[0]++;
                hash[4]--;
            }//直接令该青蛙继续鸣叫
            else
            {
                hash[0]++;
            }
        }
        else
        {
            int i=index[e];//该元素下标
            if(hash[i-1]<1)//前方无可继续鸣叫的青蛙
            {
                return -1;
            }
            else
            {
                hash[i-1]--;
                hash[i]++;
            }//更新哈希表
        }
       }
        for(int i=0;i<n-1;i++)
        {
            if(hash[i]!=0)
            {
                return -1;
            }
        }//全部鸣叫后应该只有hash[4]不为0，代表青蛙个数
        return hash[4];
        
    }
};