題目:
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。
輸入說明:
輸入為多筆測試資料,每一行輸入皆由大小寫英文字母所組成的字串。此字串長度最長為1000 個字元。
輸出說明:
每一行輸出為相對應輸入字串編碼後的結果。
範例輸入:
aaaabbcdeeeeefghhhij
範例輸出:
aa2bb0cdee3fghh1ij
==============================P.S
剛開始想錯 有點被搞混 後來想清楚了 ((頭腦真差= =
畫流程圖我真的不會畫 == 目前都直接想一下就開始摳丁
以後如果要開發大型專案不知道該怎辦= =
============================
import java.util.ArrayList; import java.util.Scanner; public class RLE { //存放經過RLE轉換後的字串 static ArrayList<String> arrayStr =new ArrayList<String>(); public static void main(String[] args) { RLE rle=new RLE(); Scanner scan =new Scanner(System.in); String str; System.out.println("Please enter String:"); str=scan.next(); rle.Judge(str); for(int x=0;x<arrayStr.size();x++) System.out.print(arrayStr.get(x)); } //判斷哪時要傳給rleStr去整理字串 public void Judge(String input){ int length=-1; RLE rle=new RLE(); for(int x=1;x<input.length();x++){ //如果此字元與前一個相同,length++ if(input.charAt(x)==input.charAt(x-1)){ length++; }else{ //把rleStr傳回來的字串add進arrayStr arrayStr.add(rle.rleStr(Character.toString(input.charAt(x-1)),length)); length=-1; } if(x==input.length()-1){//以防全部為同一字母的話 arrayStr.add(rle.rleStr(Character.toString(input.charAt(x-1)),length)); } } } //把Judge傳進來的字串與長度去做整理,回傳String public String rleStr(String str,int len){ if(len==-1){//如果只有一個字母直接回傳 return str; }else{ return str+""+str+""+len; } } }
留言列表