d574 - 節約符咒
題目描述
題目要求將輸入的字串進行壓縮，將連續重複的字元以其個數和字元本身表示。例如，"aaabb" 壓縮後變成 "3a2b"。如果壓縮後的字串長度不小於原始字串，則輸出原始字串。
解題思路
程式碼遍歷輸入字串，統計連續重複字元的個數。當遇到不同的字元時，將前一個字元的個數和字元本身轉換為字串，並添加到結果字串中。最後處理字串末尾的字元。比較壓縮後字串和原始字串的長度，輸出較短的字串。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。程式碼遍歷字串一次。
- 空間複雜度: O(n)，最壞情況下，壓縮後的字串長度可能與原始字串相同，因此需要額外的空間來儲存壓縮後的字串。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int aa;
while(cin >> aa){
int a=aa;
string ans,ans2;
int con=1;
char b,c;
bool f=0;
while(a--){
cin >> b;
ans2+=b;
if(f==0){
f=1;
c=b;
continue;
}
if(b==c)
++con;
else{
string tmp;
while(con>0){
tmp+=con%10+48;
con/=10;
}
reverse(tmp.begin(),tmp.end());
ans+=tmp;
ans+=c;
c=b;
con=1;
}
}
string tmp;
while(con>0){
tmp+=con%10+48;
con/=10;
}
reverse(tmp.begin(),tmp.end());
ans+=tmp;
ans+=c;
con=1;
if(aa>ans.length()){
cout << ans << "\n";
}
else{
cout << ans2 << "\n";
}
}
}