c621 - Reverse this and that !!
題目描述
題目要求將輸入字串中的字母部分原地反轉，並將數字部分依據數字在字串中的位置反轉後輸出。例如，輸入 "123abc456de7fgh890i"，輸出應為 "098cba765ed4hgf321i"。
解題思路
程式使用一個堆疊 (stack) 來儲存字串中的數字。遍歷輸入字串，如果遇到數字，則將其推入堆疊。如果遇到字母，則將字母添加到一個臨時字串中。當遇到數字時，或者到達字串末尾時，將臨時字串反轉並輸出，然後從堆疊中彈出一個數字並輸出。最後，如果臨時字串不為空，則反轉並輸出它。這種方法有效地將數字和字母分開處理，並按照題目要求進行反轉。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。遍歷字串一次，堆疊操作和字串反轉操作在最壞情況下也是線性時間。
- 空間複雜度: O(n)，其中 n 是輸入字串的長度。堆疊在最壞情況下可能需要儲存所有數字，臨時字串也可能需要儲存所有字母。
程式碼
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
while(cin >> a){
int al=a.length();
stack <char> n;
string tmp;
for(int i=0;i<al;++i)
if(a[i]<='9')
n.push(a[i]);
for(int i=0;i<al;++i){
if(a[i]<='9'){
if(!tmp.empty()){
reverse(tmp.begin(),tmp.end());
cout << tmp;
tmp.clear();
}
cout << n.top();
n.pop();
}
else
tmp+=a[i];
}
if(!tmp.empty()){
reverse(tmp.begin(),tmp.end());
cout << tmp;
tmp.clear();
}
cout << "\n";
}
}