資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告