這可以只用遞歸完成嗎？

給定一個字符串，返回遞歸一個「乾淨」的字符串，其中屬於同一相鄰字符已經減少爲單個字符。所以「yyzzza」產生「yza」。

stringClean("yyzzza") → "yza" 
stringClean("abbbcdd") → "abcd" 
stringClean("Hello") → "Helo"

我可以使用循環解決這個問題，但這是不允許的，因爲這個問題應該這樣來使用遞歸解決。有沒有辦法解決這個問題，而不使用循環，只使用遞歸？沒有全局變量，沒有循環。我甚至想過在參數中編碼一些信息，但我認爲這也會作弊。

我以前的程序沒有while循環，我只能得到一半的答案。基本上，當我用字符串參數調用我的函數時，我檢查了前兩個字符。如果它們是相同的，我會返回字符並再次用一個小於兩個字符的字符串調用該函數。然而，一串3或4個相同的連續字符總是會擊敗我的算法。

public String stringClean(String str) { 

    if (str.length() == 0) 
     return ""; 

    if (str.length() > 1) { 

    int counter = 1; 


     char a = str.charAt(0); 
     char b = str.charAt(1); 

     if (a == b) 
     { 
      while (str.length() > 1) 
      { 
      a = str.charAt(0); 
      b = str.charAt(1); 

      if (a != b) break; 

      counter++; 
      str = str.substring(1); 


      } 

      return a + stringClean(str.substring(1)) ; 
     } 

    } 

    return str.charAt(0) + stringClean (str.substring(1)); 

}

來源

2012-12-01 toto

是的，只用遞歸就可以解決這個問題。我會給你提示，你應該創建一個輔助方法，它有兩個參數：前一個字符和剩餘的字符串。 –

我的問題是下面的，有沒有什麼辦法來解決這個問題，而無需使用一個循環，並只使用遞歸。沒有全局變量，沒有循環。

答：是的。這很簡單。試試下面：

public String stringClean(String str) { 
     if (str.length() == 0) 
      return ""; 
     if (str.length() == 1) 
      return str; 

     if(str.charAt(0) == str.charAt(1)){ 
     return stringClean(str.substring(1)); 
     }else{ 
     return str.charAt(0)+ stringClean(str.substring(1)); 
     }  
    }

你CodingBat結果如下：

stringClean（「yyzzza」）→ 「YZA」「YZA」 OK
stringClean（「abbbcdd」）→ 「ABCD」「ABCD」 OK
stringClean（「你好」）→ 「直升機」，「直升機」 OK
stringClean（「XXabcYY」）→ 「XabcY」「XabcY」 OK
stringClean（「112ab445」）→ 「12ab45」「12ab45」 OK
stringClean（「你好簿記員」）→ 「直升機Bokeper」「直升機Bokeper」 OK
其他測試OK

來源

2012-12-01 23:48:34

當然，最後發送字符。這就是我應該做的。非常感謝！ – toto

我的問題是下面的，有沒有什麼辦法來解決這個問題，而無需使用一個循環，並只使用遞歸。沒有全局變量，沒有循環。

答案是「是的，這是可能的」。

提示：

最喜歡的「刁鑽」問題遞歸這需要一個額外的參數。
將問題看作是在每個階段過濾字符串的第一個字符。
輸入字符串的第一個字符是一個特殊情況...

來源

2012-12-01 23:40:59

public String stringClean(String str) { 
    if (str == null) { 
     return null; 
    } else if (str.length() > 1) { 
     String k = str.substring(0, 1); 
     if (str.charAt(0) == str.charAt(1)) { 
      String tmp = stringClean(str.substring(2)); 
      return k + stringClean(tmp); 
     } else { 
      return k + stringClean(stringClean(str.substring(1))); 
     } 
    } else { 
     return str; 
    } 
}

來源

2013-10-26 15:46:15 Sarath

這可以只用遞歸完成嗎？

回答

相關問題