h034 - 宴會 (Banquet)
題目描述
題目給定 n 個字串，要求從每個字串中依序取出大寫字母，直到所有字串都已取出完畢，並將取出的字母連接成一個字串作為答案。
解題思路
這題的解題思路是貪婪演算法。我們從每個字串的起始位置開始，依序檢查每個字串的當前字符是否為大寫字母。如果是，則將該字符添加到答案字串中，並將該字串的指針前進一位。重複此過程，直到所有字串都已處理完畢。由於題目要求依序從每個字串中取出字母，因此我們需要使用迴圈來遍歷所有字串，並在每個字串中遍歷其字符。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是字串的數量，M 是字串的平均長度。
- 空間複雜度: O(M)，其中 M 是答案字串的最大長度。
程式碼
#include <iostream>
using namespace std;
int n,a[205],d=1;
string s[205],k,ans;
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> s[i];
}
while(d){
d=0;
for(int i=0;i<n;++i){
if(a[i]<s[i].size()){
if(s[i][a[i]]>='A'&&s[i][a[i]]<='Z'){
ans+=s[i][a[i]];
}
++a[i];
d=1;
}
}
}
cout << ans;
}