LeetCode模拟算法精解II：外观数列与数青蛙

上篇文章LeetCode模拟算法精解I替换问号提莫攻击与Z字形变换目录1.外观数列理解题意算法原理2.数青蛙理解题意算法原理1.外观数列https://leetcode.cn/problems/count-and-say/description/理解题意给一个数这个数是1描述上一步的数这个数是 1 即一个1故写作11描述上一步的数这个数是11即两个1故写作21描述上一步的数这个数是21即一个2一个1故写作12-11描述上一步的数这个数是1211即一个1一个2两个1故写作11-12-21算法原理通过模拟和双指针对给定的数字进行解释。class Solution { public: string countAndSay(int n) { string ret 1; for(int i 1; i n; i) // 遍历 { string tmp; int len ret.size(); for(int left 0, right 0; right len; ) // 解释ret { while(right len ret[left] ret[right]) { right; } tmp to_string(right - left) ret[left]; left right; } ret tmp; } return ret; } };2.数青蛙https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/理解题意计算在字符串中字符c,r,o,a,k出现的次数只要顺序不变出现次数合理哪怕有若干个随意穿插也属于有效字符。算法原理本题要求出现次数以及确定顺序和重复度所以使用哈希表(数组模拟实现)进行判断。基本判断如下class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string t croak; int n t.size(); vectorint hash(n); // 数组模拟哈希表 unordered_mapchar, int index; // 字符对应下标 for(int i 0; i n; i) { index[t[i]] i; } for(auto ch : croakOfFrogs) { if(ch c) { if(hash[n - 1] ! 0) hash[n - 1]--; hash[0]; } else { int i index[ch]; if(hash[i - 1] 0) return -1; hash[i - 1]--; hash[i]; } } for(int i 0; i n - 1; i) { if(hash[i] ! 0) return -1; } return hash[n - 1]; } };本章完。