C ++中青蛙鸣叫的最小数量

假设我们有一个名为croakOfFrogs的字符串，它表示来自不同青蛙的字符串“ croak”的组合，多个青蛙可以同时鸣叫，因此多个“ croak”混合在一起。我们必须找到最少数量的不同青蛙，才能完成给定琴弦中所有的叫声。

在这里，有效的“ cro”表示青蛙正在顺序生成5个字母“ c”，“ r”，“ o”，“ a”，“ k”。青蛙必须产生所有五个字母才能发出嘶哑声。如果该字符串不是有效的“ croak”字符串，则返回-1。

因此，如果输入像“ crcoakroak”，则输出将为2，因为第一个青蛙可能会大喊“ crcoakroak”。第二只青蛙以后可能会大喊“ crakakroak”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一张映射

• 定义大小为ch的数组：5为其分配{'c'，'r'，'o'，'a'，'k'}

• 温度：= 0，ret：= 0

• 对于s中的每个元素c，

• （将温度降低1）

• （将温度提高1）

• 如果maxVal <m [ch [i]]或m [ch [i]] <0，则-

• maxVal：= m [ch [i]]

• 返回-1

• （将m [c]增加1）

• maxVal：= m [ch [0]]

• 对于初始化i：= 0，当i <5时，更新（将i增加1），请执行-

• 如果c与'c'相同，则-

• 否则，当c与'k'相同时，则-

• ret：= ret和temp的最大值

• 对于初始化i：= 1，当i <5时，更新（将i增加1），请执行-

• 返回-1

• 如果m [ch [0]]不等于m [ch [i]]，则-

• 返回ret

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minNumberOfFrogs(string s) {
      map<char, int> m;
      char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
      int temp = 0;
      int ret = 0;
      for (auto& c : s) {
         m[c]++;
         int maxVal = m[ch[0]];
         for (int i = 0; i < 5; i++) {
            if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
               return -1;
            }
            maxVal = m[ch[i]];
         }
         if (c == 'c') {
            temp++;
         }
         else if (c == 'k') {
            temp--;
         }
         ret = max(ret, temp);
      }
      for (int i = 1; i < 5; i++) {
         if (m[ch[0]] != m[ch[i]])
            return -1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minNumberOfFrogs("crcoakroak"));
}

输入值

"crcoakroak"

输出结果

2