a565 - 2.p&q的邂逅
題目描述
題目要求計算在一組字串中，'p' 和 'q' 可以成功配對的最大數量。配對的條件是 'p' 和 'q' 必須以 "pq" 的順序出現，且中間可以包含任意數量的其他字符（例如 'p.q'、'p...q' 都可以）。
解題思路
這題可以使用堆疊 (Stack) 來解決。遍歷字串，如果遇到 'p'，則將其放入堆疊中。如果遇到 'q' 且堆疊不為空，則將堆疊中的 'p' 彈出，配對數量加一。最後，配對數量就是答案。這個方法利用了堆疊的先進後出特性，確保 'p' 和 'q' 的配對順序是正確的。這是一種貪婪算法，因為我們盡可能地在遇到 'q' 時立即配對。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。因為我們需要遍歷字串一次。
- 空間複雜度: O(n)，在最壞的情況下，字串可能只包含 'p'，那麼堆疊的大小將會是 n。
程式碼
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
string a;
getline(cin,a);
while(getline(cin,a)){
int ans=0;
stack<int> s;
for(int i=0;i<a.length();i++){
if(a[i]=='p'){
s.push(a[i]);
}
else if(a[i]=='q'&&s.empty()==0){
s.pop();
ans++;
}
}
cout << ans << endl;
}
}