回分類題庫
d021: 2007 程式達人 D - Run Length Encoding
出處:

Difficulity : 1
Accepted : 132 Times | Submit :371 Times | Clicks : 7864
Accepted : 119 Users | Submit : 134 Users | Accepted rate : 89%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 08:53

Content :

Run Length Encoding (RLE)編碼方式是多媒體資料壓縮常用的方法之一(例如與Huffman Code 並用),RLE 的作法是於將一連串相同的資料改以兩個部分來表示, 前面一部分是資料本身(symbol),後面部分代表該串資料的長度(也就是重複次數, run length)。例如:輸入字串為 “aaaabbcdeeeeefghhhij”,經過RLE 編碼後結果為"a4b2c1d1e5f1g1h3i1j1"。

當然,上面的例子其實沒有達到壓縮檔案的目的,有部分的原因是出現一次的字元卻得用字元+次數(1)來表示,為了節省空間,有人提議出現一次的字元長度就無須紀錄,因此將表示方法改為: 字元+後續出現次數,例如 “aaaa”經過編碼後為”a3” (a 出現一次後又再出現三次),因此輸入字串 “aaaabbcdeeeeefghhhij”的編碼就變為:"a3b1cde4fgh2ij"。

但是上面表示方法仍有問題,因為symbol 後有可能接的是symbol,也有可能是run-length,造成混淆,因此又有一個解決方案如下:若出現次數大於一,重複該字元兩次,並接上剩餘重複次數,例如: “aaaa”經過編碼後為”aa2”,”bbb”經過編碼後為”bb1”,所以只要字元重複,表示後面接的是數字,若未重複,則該字元僅出現一次且其後也緊接另一個字元。依此原則,"aaaabbcdeeeeefghhhij" 將被編碼為"aa2bb0cdee3fghh1ij"。請參照以上說明,編寫 RLE encoder。

Input :

輸入為多筆測試資料,每一行輸入皆由大小寫英文字母所組成的字串。此字串長度最長為1000 個字元。

Output :

每一行輸出為相對應輸入字串編碼後的結果。

Sample Input :

aaaabbcdeeeeefghhhij

Sample Output :

aa2bb0cdee3fghh1ij

Hint :

解題率:18/21

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (0)

C++
C
JAVA
40358. staycalm (4 ms , 212KB)
39073. johnny (4 ms , 368KB)
36710. NoisyBoy (4 ms , 428KB)
24858. nthuskate (4 ms , 210KB)
23615. henryokc (4 ms , 340KB)
53536. ag100 (2 ms , 228KB)
35103. cp100703029 (2 ms , 214KB)
35093. cp100703009 (2 ms , 222KB)
35069. cp100703044 (2 ms , 234KB)
34951. cp100703042 (2 ms , 220KB)
63282. dumbo423 (102 ms , 918KB)
50632. nwgs524513cja (104 ms , 170KB)
87400. a6205 (120 ms , 900KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡