[LC优选算法#14] 模拟 | 外观数列 | 数青蛙

1. 外观数列外观数列这道题本质上是统计字符串中连续且相同的字符个数依据题意模拟即可。解题思路模拟 双指针用双指针标记相同连续字符的区间遍历字符串拼接区间的结果即可。classSolution{public:stringcountAndSay(intn){string ret1;for(inti1;in;i){string s;intlenret.size();for(intleft0,right0;rightlen;){while(rightlenret[left]ret[right]){right;}sto_string(right-left)ret[left];//注意两个字符串的作用leftright;}rets;}returnret;}};2. 数青蛙数青蛙解题思路模拟模拟青蛙的叫声假设青蛙的叫声是一个持续的croak当遇到r, o, a, k这四个字符的时候去看每一个字符对应的前驱字符看是否可以和之前的叫声拼接如果有则继续向后直至末尾如果没有直接返回-1。当遇到c字符的时候由于题目要求青蛙的数目最少因此在开始记录叫声前先看看k字符是否存在青蛙如果有则让这个青蛙继续从c开始向后持续叫如果没有则添加一只新青蛙再开始。小巧思在判断字符时可以使用哈希映射的方法使用unordered_map存储croak字符的下标为key字符为value这样就避免重复写if-else了。classSolution{public:intminNumberOfFrogs(string croakOfFrogs){string tcroak;intnt.size();unordered_mapchar,inthash;vectorintpos(t.size(),0);//哈希表存下标for(inti0;in;i){hash[t[i]]i;}for(autoch:croakOfFrogs){//c字符if(chc){if(pos[n-1]!0){pos[n-1]--;}pos[0];}//其他字符else{if(pos[hash[ch]-1]!0){pos[hash[ch]-1]--;pos[hash[ch]];}else{return-1;}}}for(inti0;in-1;i){if(pos[i]!0){return-1;}}returnpos[n-1];}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~