题目描述

题目链接：1419.数青蛙

算法原理

解法（模拟 + 分情况讨论）

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

代码实现

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {const string croak = "croak";int n = croak.size();vector<int> hash(n);//用数组来模拟哈希表unordered_map<char,int> index;//[x,x所对应的下标]for(int i = 0;i < n;i++){index[croak[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];}
};