数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中青蛙鸣叫的最小数量
假设我们有一个名为 croakOfFrogs 的字符串，它表示来自不同青蛙的“croak”字符串的组合，多只青蛙可以同时鸣叫，因此多个“croak”混合在一起。我们必须找到完成给定字符串中所有“croak”的不同青蛙的最小数量。
这里有效的“croak”表示一只青蛙按顺序发出 5 个字母“c”、“r”、“o”、“a”、“k”。青蛙必须发出所有五个字母才能完成一次鸣叫。如果字符串不是有效的“croak”字符串，则返回 -1。
因此，如果输入类似于“crcoakroak”，则输出将为 2，因为第一只青蛙可以叫“crcoakroak”。第二只青蛙可以在稍后叫“crcoakroak”。
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 m
定义一个大小为 5 的数组 ch，并将其赋值为 {'c', 'r', 'o', 'a', 'k'}
temp := 0, ret := 0
对于 s 中的每个元素 c，执行以下操作：
(将 m[c] 增加 1)
maxVal := m[ch[0]]
初始化 i := 0，当 i < 5 时，更新（将 i 增加 1），执行以下操作：
如果 maxVal < m[ch[i]] 或 m[ch[i]] < 0，则：
返回 -1
maxVal := m[ch[i]]
如果 c 与 'c' 相同，则：
(将 temp 增加 1)
否则，当 c 与 'k' 相同，则：
(将 temp 减少 1)
ret := ret 和 temp 的最大值
初始化 i := 1，当 i < 5 时，更新（将 i 增加 1），执行以下操作：
如果 m[ch[0]] 不等于 m[ch[i]]，则：
返回 -1
返回 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
更新于： 2020-11-17
179 次查看
广告