11

私は、interviewstreet.com で「文字列削減」の問題を解決するためのさまざまな議論やコードの試みを見てきましたが、動的プログラミングを介してそれを行うものはありません。

動的プログラミングセクションの下にリストされている問題は、次のように説明されています。

a、b、c で​​構成される文字列が与えられた場合、次の操作を実行できます。隣接する 2 つの異なる文字を取り、3 番目の文字に置き換えます。たとえば、「a」と「c」が隣接している場合、「b」に置き換えることができます。

この操作を繰り返し適用して得られる最小の文字列は?

この問題は、徹底的な総当り検索を使用して解決でき、可能なすべての置換のツリーを効果的に作成できます。

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if (next < min) min = next;
        }
    }
}

Nこれは大きな( ) では明らかに失敗するためN <= 100、小さなサブ問題に分割し、それらをメモして、結果をマージしようとしています。

問題は、動的計画法を適用するために必要な「最適なサブ構造」を持つ状態を判断できないことです (つまり、サブ問題からの結果を「マージ」するために)。文字列の一部を最小化しても、最終的な文字列が実際に最小のソリューションになるとは限りません。

この場合、最終的な解決策にマージできる副問題の「状態」は何でしょうか?

4

3 に答える 3

1

これを難しくしているのは、これを 2 つの動的計画法の問題として連続して扱う必要があることです。

  1. 巻き上げたキャラクターごとに、開始位置ごとに、そのキャラクターに縮小できるブロックである可能性のあるすべての終了位置の表を作成します。
  2. 文字列の最後iの文字を短縮できる最小の長さ。(手順 1 で作成したテーブルを使用して、この問題を再帰的に解決済みのサブ問題に減らすことができます。)

2 番目は、答えを提供します。最初の問題をすでに解決している場合は、はるかに簡単です。

于 2012-06-28T14:49:33.257 に答える
1

スポイラー アラート コード:

public static int findMinReduction(String line){
    //Pseudocode:
    //Count the number of occurences of each letter in the input string.
    //If two of these counts are 0, then return string.length
    //Else if (all counts are even) or (all counts are odd), then return 2
    //Else, then return 1

    int len = line.length();
    String a_reduce = line.replaceAll("c", "").replaceAll("b", "");
    String b_reduce = line.replaceAll("a", "").replaceAll("c", "");
    String c_reduce = line.replaceAll("a", "").replaceAll("b", "");

    int a_occurances = a_reduce.length();
    int b_occurances = b_reduce.length();
    int c_occurances = c_reduce.length();

    if ((a_occurances == b_occurances && a_occurances == 0) || 
       (a_occurances == c_occurances && a_occurances == 0) || 
       (b_occurances == c_occurances && b_occurances == 0)){
        return len;
    }
    else{
        if (a_occurances % 2 == 0 && 
            b_occurances % 2 == 0 && 
            c_occurances % 2 == 0){
            return 2;
        }
        if (a_occurances % 2 != 0 
            && b_occurances % 2 != 0 && 
            c_occurances % 2 != 0){
            return 2;
        }
    }
    return 1;
}

複雑：

これは O(n) 時間の複雑な操作です。入力サイズが大きくなると、実行される作業量は入力サイズに比例します。これは非常に高速で、メガバイト サイズの文字列を処理することができ、それでも数分の 1 秒で処理できます。

このアルゴリズムが機能する理由を完全に分析したアルゴリズムがここにあります。

Java のインタビューで困っているので、ヒントが必要です

于 2015-09-30T21:50:08.850 に答える
0

ソリューション理論を説明する構造を作成することから始めます。これには、考慮された文字数、これまでにエンコードされた文字列、および理論の最悪のケースと最良のケースが含まれます。

最初はただ 1 つの理論があります。つまり、文字は処理されません。最良のケースは長さ 1 の文字列です (たとえば、ルールは常に適用され、文字列は 1 文字に減らすことができ、最悪のケースはルールが適用されない N です)。

encoded string = "";
encoded index = 0;
worst case = N; 
best case = 1;

次に、インデックスを 1 ずつインクリメントし、エンコードされた文字列に文字を追加します。ルールが適用されない場合は、その理論をそのままにしておきます。ルールが適用される場合は、ルールを適用するか適用しないかを決定する必要があります。したがって、キャラクターを追加するときは、最後のキャラクターに適用される可能性のある各ルールの理論を複製し、ルールが適用されないバージョンを 1 つ保持します。そして、各理論の最良のケースと最悪のケースを更新します。

最初は、理論の数が急速に増えます。しかし最終的には、いくつかの理論の最悪のケースが他の理論の最良のケースよりも優れているという状況に陥ります。

したがって、インデックスを進めるときはいつでも、最良のケースが最良の最悪のケースの理論よりも悪い理論を削除します。指数が N に近づくと、ほとんどの理論は脱落します。

于 2012-06-28T18:09:51.330 に答える