题解：模拟算法——数青蛙(medium)
1.题目
题目链接：LINK
2.题解
用循环进行遍历，
- 如果该字符为o\o\a\k 找一下前驱字符是否存在
- 如果存在，前驱字符–，该字符++
- 如果不存在，返回-1
- 如果该字符为c，找一下最后一个字符是否有数
- 如果最后一个数非0，最后一个字符–，当前字符++
- 最后一个数是0，当前字符++
3.参考代码
不用哈希表，缺点是这个字符串字符种类太多时会不适用。
class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { //哈希数组 int arr[5] = {0};//c r o a k //0标识c，1标识r，2标识o，3标识a，4标识k for(auto& ch: croakOfFrogs) { if(ch == 'c') { if(arr[4] == 0) arr[0]++; else arr[4]--,arr[0]++; } else if(ch == 'r') { if(arr[0] != 0) arr[0]--,arr[1]++; else return -1; } else if(ch == 'o') { if(arr[1] != 0) arr[1]--,arr[2]++; else return -1; } else if(ch == 'a') { if(arr[2] != 0) arr[2]--,arr[3]++; else return -1; } else if(ch == 'k') { if(arr[3] != 0) arr[3]--,arr[4]++; else return -1; } } if((arr[0] + arr[1] + arr[2] + arr[3]) != 0) return -1; return arr[4]; } };
用哈希表，好处是可以适用字符串字符种类很大的时候
class Solution { public: int minNumberOfFrogs(string croakOfFrogs) { string s = "croak"; int n = s.size(); //哈希数组 int hash[5] = {0};//c r o a k //0标识c，1标识r，2标识o，3标识a，4标识k //为了方便找到前一个字母的下标，我们用哈希表来记录一下 unordered_map<char,int> index; for(int i = 0; i < n; i++) { index[s[i]] = i; } for(auto& ch: croakOfFrogs) { if(ch == 'c') { if(hash[n-1] == 0) hash[0]++; else hash[n-1]--,hash[0]++; } else { int i = index[ch];//取到该字符对应的下标 if(hash[i-1] != 0) hash[i-1]--,hash[i]++; else return -1; } } for(int i = 0; i < n-1; i++) if(hash[i]!=0) return -1; return hash[n-1]; } };
这个地方为什么用哈希表呢？主要是为了方便找到对应字符的下标。
4.总结
这个题的解题思路挺好，然后用哈希表存下标写代码是一个不错的选择。
EOF
