e522 - 106 彰雲嘉區複賽 - Q2 跑長編碼與資料壓縮
題目描述
題目要求實作跑長編碼 (Run-Length Coding) 演算法，對輸入的二進位字串進行壓縮，並計算壓縮比率。壓縮比率定義為壓縮後位元數除以原始位元數，以百分比表示。如果輸入字串包含非二進位字元，則輸出 -1。
解題思路
程式使用貪婪演算法來實現跑長編碼。它遍歷輸入字串，統計連續出現的 '0' 和 '1' 的數量。當連續出現的數量達到 7 時，或者遇到與之前不同的字元時，就輸出一個 4 位元的碼字，表示該字元及其連續出現的次數。碼字格式為 "0" 或 "1" 後面跟著 3 位元的二進位表示的次數。最後，計算壓縮比率並輸出。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。程式需要遍歷字串一次來進行編碼和計算壓縮比率。
- 空間複雜度: O(1)。程式使用的額外空間是固定的，不隨輸入字串的長度而變化。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
int t,al,ans,buf0,buf1;
string a,buf[8]={"000","001","010","011","100","101","110","111"};
void io(bool p){
if(p){
cout << "1" << buf[buf1] << " ";
buf1=0;
}
else{
cout << "0" << buf[buf0] << " ";
buf0=0;
}
ans+=4;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
getline(cin,a);
while(t--){
getline(cin,a);
al=a.length();
ans=buf0=buf1=0;
int s=1;
for(int i=0;i<al;++i){
if(a[i]!='0'&&a[i]!='1'){
cout << "-1\n";
s=0;
break;
}
}
for(int i=0;i<al&&s;++i){
if(a[i]=='0'){
++buf0;
if(buf0==7)
io(0);
else if(buf1)
io(1);
}
else if(a[i]=='1'){
++buf1;
if(buf0)
io(0);
else if(buf1==7)
io(1);
}
}
if(buf0)
io(0);
if(buf1)
io(1);
if(s)cout << fixed << setprecision(0) << (double)ans*100/(double)al << "%\n";
}
}