-5

文字列を受け取り、文字列内の文字の繰り返しシーケンスごとに、1 つを除いてすべてを削除する次のメソッドを完成させます。たとえば、入力文字列が「AAAABCCDDDDAACCCCCC」の場合、メソッドは「ABCDAC」を返す必要があります。

コードは再帰的でなければなりません。ループ (while、do/while、または for) を使用しないでください。メソッドの外で変数を宣言しないでください。メソッド内でローカル変数を宣言できます。

public static String eliminateRepeats (String s)
{
4

3 に答える 3

1 
public class Recurse
{
    public static void main( String args[] )
    {
        System.out.println( recurse( "AAAABCCDDDDAACCCCCC" ) );
    }

    private static String recurse( String s )
    {
        if ( s == null || s.equalsIgnoreCase("") )
        {
            return "";
        }
        else if ( s.length() > 1 )
        {
            if ( !s.substring( 0 , 1 ).equalsIgnoreCase( s.substring( 1 , 2 ) ) )
            {
                return s.substring( 0 , 1 ) + recurse( s.substring( 1 ) );
            }

            return recurse( s.substring( 1 ) );
        }
        else
        {
            return s.substring( 0 , 1 );
        }
    }
}
于 2012-04-30T15:55:18.790 に答える
1

ここでの秘訣は、これを解決するにはループが必要であるため、文字列の小さな部分を使用してメソッドを再帰的に呼び出してループを偽造するだけです。

再帰を使用するときに通常行うように、作業をより小さな部分に分割する方法はありません (たとえば、文字列を半分に分割するなど)。一度に 1 文字ずつ処理し、残りの文字列でメソッドを呼び出すだけです。

C# での例:

public static string EliminateRepeats(string s) {
  return
    s.Length == 1 ?
      s
    :
      (s[0] != s[1] ? s.Substring(0, 1) : "")
      + EliminateRepeats(s.Substring(1));
}

(Jonathan Paynes のコードに触発されたコード。)

于 2012-04-30T16:23:52.567 に答える
0 
// use a default value for the lastchar for the first char, 
// which is impossible to meet in an regular string
def concentrate (s: String, lastchar: Char = 0) : String = {
    // recursive methods always need to know when it is enough
    if (s.length == 0) s else 
    if (s(0) == lastchar) concentrate (s.substring (1), lastchar) else 
    s(0) +  concentrate (s.substring (1), s(0)) }

concentrate ("AAAABCCDDDDAACCCCCC")

以下は末尾再帰のバリエーションです。

@tailrec 
def concentrate (s: String, carry:String = "", lastchar: Char = 0) : String = {
    if (s.length == 0) carry else 
    if (s(0) == lastchar) concentrate (s.substring (1), carry, lastchar) else 
    concentrate (s.substring (1), carry + s(0), s(0)) }

結果の文字列がその場で一緒に接着され、パラメーターとして渡されるため、最後の位置に再帰呼び出しがあります。Scala では、これはコンパイラによって最適化され、変更可能な変数を使用したループとほぼ同じ速度で実行され、スタックが爆発することはありません (非常に長い文字列の場合でも)。

于 2012-05-01T20:44:39.153 に答える