1

文字が [0 - 9] の範囲の数字に過ぎない文字列があるとします。例: 「2486」。ここで、桁の合計が 6 で割り切れるすべてのサブシーケンスを見つけたいと思います。例: "2486" では、サブシーケンスは - "6"、"246" (2+ 4 + 6 = 12 は 6 で割り切れます)、 "486" (4 + 8 + 6 = 18 は 6 で割り切れる) など。これを実行できるすべての 2^n の組み合わせを生成することがわかっています。しかし、それは非常に費用がかかります。これを行う最も効率的な方法は何ですか?

編集：

Quoraのどこかに次の解決策が見つかりました。

int len,ar[MAXLEN],dp[MAXLEN][MAXN];

int fun(int idx,int m)

{

    if(idx==len)

        return (m==0);

    if(dp[idx][m]!=-1)

        return dp[idx][m];

    int ans=fun(idx+1,m);

    ans+=fun(idx+1,(m*10+ar[idx])%n);

    return dp[idx][m]=ans;

}

int main()

{

    // input len , n , array

    memset(dp,-1,sizeof(dp));

    printf("%d\n",fun(0,0));            

    return 0;

}

誰かがコードの背後にあるロジックを説明できますか - 'm*10+ar[idx])%n' ? ここで m に 10 を掛けるのはなぜですか?

4

3 に答える 3

1

16 桁のシーケンスがあるとします。2 16 個のサブシーケンスをすべて生成してテストできます。これは 65536 操作です。

または、最初の 8 桁を取得して 2 8の可能な部分列を生成し、6 を法とする合計の結果に基づいてそれらを並べ替え、最後の 8 桁について同じことを行うことができます。これはわずか 512 回の操作です。

次に、モジュロ値が 0 の最初のリストの各サブシーケンス (空のサブシーケンスを含む) を取得し、それを最後のリストの各サブシーケンスと0 に等しいモジュロ値。

次に、モジュロ値が 1 に等しい最初のリストの各サブシーケンスを取得し、それをモジュロ値が 5 に等しい最後のリストの各サブシーケンスと連結します。次に、2 と 4、3 と 3、4 と 2、5 と 1 を連結します。

したがって、512 回の操作の初期コストの後、合計が 6 で割り切れるサブシーケンスのみを生成できます。このアルゴリズムは、より大きなシーケンスに再帰的に適用できます。

于 2015-07-08T04:14:57.107 に答える
0

文字列内の位置ごとに 6 ビットのビットマップを持つ配列を作成します。右から左に作業し、ビットマップの配列を設定して、ビットマップのその位置に合計される配列の直後から始まるいくつかのサブシーケンスがある場合に、ビットマップが配列にビットを設定するようにします。現在の位置の直後のビットマップを使用して、右から左にこれを​​行うことができます。3 が表示され、現在の位置の直後のビットマップが 010001 である場合、3 をスキップするだけで合計 1 と 5 にアクセスできます。3 を使用すると、合計 4 と 2 が使用可能になり、新しいビットマップは 011011 になります。

ここで、サブシーケンスの深さ優先検索を左から右に実行します。各文字で、その文字を取得するかどうかを選択します。これを行うと、これまでに取得した文字の mod 6 の合計を追跡します。ビットマップを使用して、その位置の右側に、これまでの合計に追加されてゼロになるサブシーケンスがあるかどうかを調べます。現在の合計が合計ゼロのサブシーケンスにつながることがわかる限り続行し、そうでない場合は停止して再帰します。

最初のステージのコストは、入力のサイズに比例します (固定値 6 の場合)。第 2 段階では、生成されるサブシーケンスの数に比例してコストがかかります。実際、アクセスしたサブシーケンスを実際に書き出す必要がある場合 (たとえば、明示的なスタックを維持し、スタックの内容を書き出すことによって)、それはプログラムの中で最もコストのかかる部分になります。

最悪のケースはもちろん、すべての 2^n サブシーケンスが有効な場合に 000000...0000 を入力することです。

于 2015-07-08T04:47:57.687 に答える
0

amitという名前のユーザーが最近、除数が4のサブシーケンスではなく組み合わせについて同様の質問に答えたと確信していますが、今は見つけられません. 彼の答えは、この場合、5 つの配列 (と呼びますArray_i)を作成することでしたO(n)。各配列には、6 とのモジュラー関係iを持つ配列要素が含まれています。サブシーケンスでは、要素の順序を記録する方法も必要です。たとえば、 の場合、2486配列は次のようになります。

Array_0 = [null,null,null,6]
Array_1 = []
Array_2 = [null,4,null,null]
Array_3 = []
Array_4 = [2,null,8,null]
Array_5 = []

次に、要素の順序を維持しながら、適切な配列をクロス結合します: Array_0、Array_2 & Array_4、Array_0 & その他の配列の組み合わせ:

6, 24, 48, 246, 486
于 2015-07-08T17:05:29.260 に答える