壓縮一個字符串「aaabbccccd」爲「a3b2c4d」

Question

我想壓縮一個字符串。例如，如果用戶輸入是「aaabbcccd」 - 輸出應計數字母，如果count超過1，則打印該字母，然後輸入數字：a3b2c3d。

這就是我想到的，但我在控制檯中的輸出仍然不正確。

public class Compress { 
public static void main(String[] args) { 

    String a = IO.readString(); 
    int aLength = aLength.length(); 
    int repeatedStart = 0; 
    int repeatedLength = 1; 
    int currentStart = 0; 
    int currentLength = 1; 

    for(int i = 1; i < aLength; i++) { 
     if(a.charAt(i) == a.charAt(i-1)) { 
      currentLength+=1; 
      if(currentLength > repeatedLength) { 
       repeatedStart = currentStart; 
       repeatedLength = currentLength; 
       IO.outputStringAnswer(repeatedLength+""+a.charAt(repeatedStart)); 
      } 
     } else { 
      currentStart = i; 
      currentLength = 1; 
      IO.outputStringAnswer(currentLength+""+a.charAt(currentStart)); 
     } 
    } 
} 
} 

我在控制檯輸出爲：

--------MacBook-Pro:cs ----------$ java Compress 
aaaabbcc 
RESULT: "2a" 
RESULT: "3a" 
RESULT: "4a" 
RESULT: "1b" 
RESULT: "1c" 

我知道我的outputStringAnswer肯定是放錯了地方。任何幫助將不勝感激。

謝謝

Answer 1

你的算法不太對。你需要兩個嵌套for循環。其基本做法是：

對於字符串中的每個字符，計算有多少字符後，立即在它的右邊是相同的字符，並打破了，一旦你找到一個差異

//basic pseudo-code, untested 
for(int i = 0; i < someString.length() - 1; i++) { 
    char next = someString.charAt(i+1); 
    int counter = 1; 
    while(next == c) { 
     //increment counter, etc 
    } 
} 

沒有必要的如果/其他特殊情況下的長度== 1

Answer 2

簡化代碼的版本，實際工作：

public static void main(String... args) { 
    String a = "aaabbccccd"; 
    int currentLength = 1; 

    StringBuilder result = new StringBuilder(); // empty string 
    for (int i = 1; i < aLength; i++) { 
     if (a.charAt(i) == a.charAt(i - 1)) { 
      currentLength++; 
     } else { 
      System.out.println(currentLength + "" + a.charAt(i - 1)); 
      result.append(a.charAt(i - 1)) 
       .append(currentLength > 1 ? currentLength : ""); 
      currentLength = 1; // reset the length 
     } 
    } 

    // print last one 
    System.out.println(currentLength + "" + a.charAt(a.length() - 1)); 
    result.append(a.charAt(a.length() - 1)) 
     .append(currentLength > 1 ? currentLength : ""); 
    System.out.println("result = " + result.toString()); 
} 

輸出：

3A
2B
4C
1D

結果= a3b2c4d

Answer 3

if-else語句需要稍加修改你的。嘗試運行以下代碼。

public static void main(String[] args) { 
    String a="aaaaaaaabbbbbbcccccccccccccd"; 
    char first=a.charAt(0); 
    int recur=0; 

    StringBuilder res=new StringBuilder(); 
    for (int i = 1; i <a.length(); i++) { 
     if(first==a.charAt(i)){ 
      recur++; 
     } 
     else{ 
     if (recur>0) 
     res.append(first).append(recur); 
     recur=0; 
     first=a.charAt(i); 
     } 
    } 
    if (recur>0) 
     res.append(first).append(recur); 
    else 
     res.append(first); 
    System.out.println(res); 
} 

Answer 4

你在這裏有一些正確的想法，但算法有錯誤。

我想教你用循環不變式來思考：對於每個循環迭代總是對的語句，當循環退出時也是如此。如果你選擇不變的話，退出條件也是答案，或者也許只是遠離答案的微不足道的一步。

通過這種方式，您可以在代碼運行之前獲得一個您確信可以使用的循環。如果某些事情沒有按照預期發揮作用，那麼你就有了一個嚴謹的方法來思考發生了什麼問題。發佈到這不是這個！

E.g.你的代碼被破壞的一個很好的線索是給它一個長度爲1的字符串。你的代碼什麼都不輸出。如果你正在考慮循環不變量，那麼你不可能以這個問題結束。

這裏是你的代碼的循環不變的建議：

Assume: a[0] exists 
For the substring that starts at 0 and ends at k, 
    runLen is the length of the final run ending at k 
    Any runs prior to final have been output. 
    runChar is the character of the run 

我是怎麼想出這個？所需的輸出是運行長度和運行字符。這使得這些數量成爲您程序中變量的最佳候選對象。輸入的前綴是經常出現在好的不變中的另一個想法。當你猜錯數量放入不變量時，它會顯示爲無法在初始時或在每次循環迭代之後使其成爲真，或者過於複雜的推理使其成爲真。你能做出真實的東西與不變的東西之間的差距通常會指向某些要添加或改變的東西。選擇不變式的唯一方法是練習。由於良好的不變性相當於編寫一個良好的循環，因此這是集中編程技術研究的好地方。

回到不變量，當k達到a.length - 1且不變量仍然爲真時，我們需要做的就是輸出最後一次運行，並且我們有答案。

現在想想如何建立與k在0不變量。在這種情況下，他當前的運行僅僅是第一個字符：

runLen = 1 // the single character a[0] 
runChar = a[0] 

現在想想如何重新建立k已增加了1井後的不變，有兩種情況。新的a[k]匹配runChar或者它不匹配。我們需要重新確定每個案例的不變量。所以對於循環中，我們結束了：

for k = 1 to a.length - 1 

    // Here the k'th character has violated the invariant 

    if a[k] == runChar 
    // new k'th character matches the run character 
    ++runLen // run has grown by one. 
    // run char has not changed 
    else 
    // new k'th character starts a new run 
    Output runLen, runChar // re-establish invariant that previous runs are output 
    runLen = 1 // re-establish invariant about run length 
    runChar = a[k] // re-establish invariant about the run character 

    // Here the invariant is correct again! 

如上所述，循環退出後，唯一的工作，剩下的工作就是從不變的k == a.length - 1得到你需要的結果。所有缺少的是輸出最終的運行：

Output runLen, runChar 

在Java中編寫此代碼非常簡單。

public class RLE { 

    public static void main(String [] args) { 
     String a = "aaabbcccd"; 
     StringBuilder sb = new StringBuilder(); 

     // Establish invariant for k == 0. 
     int runLen = 1; 
     char runChar = a.charAt(0); 

     // Advance k, re-establishing invariant for each step. 
     for (int k = 1; k < a.length(); k++) { 
      if (a.charAt(k) == runChar) { 
       ++runLen; 
      } else { 
       sb.append(runChar).append(runLen); 
       runLen = 1; 
       runChar = a.charAt(k); 
      } 
     } 
     // Output the final run to get from invariant to required answer. 
     sb.append(runChar).append(runLen);  
     System.out.println(sb.toString()); 
    } 
}