e208 - 11541 - Decoding

🔗 前往 ZeroJudge 原題

題目描述

題目要求將使用簡單的遊程編碼 (Run-length encoding) 編碼的字串解碼。編碼方式是將連續出現的相同字符替換為單個字符及其出現頻率。例如，"AABBBBDAA" 會被編碼為 "A2B4D1A2"。輸入為多組測試案例，每組案例包含一個編碼後的字串，輸出對應的解碼後的字串，並包含測試案例編號。

解題思路

解題思路是逐個字符地解析輸入字串。如果當前字符是字母，則讀取接下來的數字，表示該字母的重複次數。然後，將該字母重複指定的次數輸出。如果當前字符是換行符，則表示一個測試案例結束，開始處理下一個測試案例。如果當前字符既不是字母也不是換行符，則表示輸入結束。

複雜度分析

• 時間複雜度: O(N)，其中 N 是輸入字串的長度。因為需要遍歷整個輸入字串一次。
• 空間複雜度: O(1)，因為只需要常數級別的額外空間來存儲當前字符和重複次數。

程式碼

#include <iostream>
using namespace std;
int main(){
	int n,t,ca=1;
	char a;
	cin >> n;
	getchar();
	cout << "Case 1: ";
	while(a=getchar()){
		if(a<'A'&&a!='\n')break;
		else if(a=='\n'){
			cout << "\nCase " << ++ca << ": ";
		}
		else{
			cin >> t;
			while(t--){
				cout << a;
			}
		}
	}
}