【算法题攻略】模拟
文章目录
- 一、模拟类算法题的特征
- 二、习题解析
- 1. Z 字形变换
- 2. 外观数列
- 3. 数青蛙（hard）
一、模拟类算法题的特征
题目描述直观
模拟题通常直接描述一个现实场景 或 规则系统，要求用代码还原过程。例如棋类游戏规则、物理运动轨迹、自动机行为等。流程明确
题目会给出明确的步骤或状态转移规则，例如：
（1）每一步如何更新数据
（2）终止条件是什么
（3）输入输出格式固定边界条件多
需要处理大量特殊情况，例如：
（1）数值溢出
（2）初始状态和终止状态
（3）无效输入的处理
二、习题解析
1. Z 字形变换
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”
- 示例演示：
classSolution{public:stringconvert(string s,intnumRows){if(numRows==1)// 特殊情况处理returns;intcvt=2*numRows-2;string tmp;for(introw=0;row<numRows;row++){if((row==0)||(row==numRows-1))// 处理第一行 和 末尾行的情况{for(inti=row;i<s.size();i+=cvt){tmp+=s[i];}}else// 处理中间行的情况{if(row<s.size()&&numRows>2)tmp+=s[row];inti=cvt;for(;i<s.size();i+=cvt){tmp+=s[i-row];if(i+row<s.size())tmp+=s[i+row];}if(i-row<s.size())tmp+=s[i-row];}}returntmp;}};2. 外观数列
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
- 示例演示：
classSolution{public:stringcountAndSay(intn){string count_str="1";while(n>1)// 迭代 n 轮生成第 n 个外观数列{string temp;// 使用双指针统计连续且相同的字符个数intleft=0,right=1;while(right<count_str.size()){if(count_str[left]!=count_str[right]){temp+=right-left+'0';temp+=count_str[left];left=right;}right++;}temp+=right-left+'0';temp+=count_str[left];count_str=temp;n--;}returncount_str;}};3. 数青蛙（hard）
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 <= 10^5
- 字符串中的字符只有 ‘c’, ‘r’, ‘o’, ‘a’ 或者 ‘k’
- 代码演示：
classSolution{public:intminNumberOfFrogs(string croakOfFrogs){if(croakOfFrogs.size()%5!=0)return-1;unordered_map<char,int>hash;// 创建哈希表hash['c']=0;hash['r']=0;hash['o']=0;hash['a']=0;hash['k']=0;for(autoit:croakOfFrogs){if(it=='c'){if(hash['k']>0)hash['k']--;hash['c']+=1;}if(it=='r'){if(hash['c']>0){hash['c']--;hash['r']+=1;}elsereturn-1;}if(it=='o'){if(hash['r']>0){hash['r']--;hash['o']+=1;}elsereturn-1;}if(it=='a'){if(hash['o']>0){hash['o']--;hash['a']+=1;}elsereturn-1;}if(it=='k'){if(hash['a']>0){hash['a']--;hash['k']+=1;}elsereturn-1;}}for(autoit:"croa")// 检查哈希表其它位置是否大于0{if(hash[it]>0)return-1;}returnhash['k'];// 返回哈希表中 'k' 字符位置的个数}};