【算法题攻略】模拟

文章目录一、模拟类算法题的特征二、习题解析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(numRows1)// 特殊情况处理returns;intcvt2*numRows-2;string tmp;for(introw0;rownumRows;row){if((row0)||(rownumRows-1))// 处理第一行 和 末尾行的情况{for(intirow;is.size();icvt){tmps[i];}}else// 处理中间行的情况{if(rows.size()numRows2)tmps[row];inticvt;for(;is.size();icvt){tmps[i-row];if(irows.size())tmps[irow];}if(i-rows.size())tmps[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_str1;while(n1)// 迭代 n 轮生成第 n 个外观数列{string temp;// 使用双指针统计连续且相同的字符个数intleft0,right1;while(rightcount_str.size()){if(count_str[left]!count_str[right]){tempright-left0;tempcount_str[left];leftright;}right;}tempright-left0;tempcount_str[left];count_strtemp;n--;}returncount_str;}};3. 数青蛙hard1419. 数青蛙题目描述给你一个字符串 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_mapchar,inthash;// 创建哈希表hash[c]0;hash[r]0;hash[o]0;hash[a]0;hash[k]0;for(autoit:croakOfFrogs){if(itc){if(hash[k]0)hash[k]--;hash[c]1;}if(itr){if(hash[c]0){hash[c]--;hash[r]1;}elsereturn-1;}if(ito){if(hash[r]0){hash[r]--;hash[o]1;}elsereturn-1;}if(ita){if(hash[o]0){hash[o]--;hash[a]1;}elsereturn-1;}if(itk){if(hash[a]0){hash[a]--;hash[k]1;}elsereturn-1;}}for(autoit:croa)// 检查哈希表其它位置是否大于0{if(hash[it]0)return-1;}returnhash[k];// 返回哈希表中 k 字符位置的个数}};