2

2 進数の桁数が n で、最大連続出現数が m の場合、考えられるさまざまな 2 進数の数を見つけます。また、左端と右端のビットは 1 でなければなりません。

たとえば、n = 5、m = 3 です。

カウントは 7: 10001 10011 10101 10111 11001 11011 11101

11111 は、連続する 1 が多すぎるため除外したことに注意してください。

これは私が最近受けたインタビューの質問であり、私を悩ませてきました. n が 32 を超える可能性があるため、各数値の正当性を力ずくでチェックしたくありません。

4

2 に答える 2

3

「1」で始まり、最大で「1」の数字が連続するバイナリシーケンスをほぼ有効と呼びましょう。m

i = 1, ..., nとは、正確に連続した「1」の数字で終わるj = 0, ..., m長さa(i, j)のほぼ有効なシーケンスの数です。ij

それで

  • a(1, 1) = 1およびa(1, j) = 0 for j != 1、長さ 1 のほぼ有効なシーケンスは「1」だけだからです。
  • なぜならn >= 2、ほぼ有効な長さのシーケンスに「0」j = 0をa(i, 0) = a(i-1, 0) + a(i-1, 1) + ... + a(i-1, m)追加すると、「0」で終わるi-1ほぼ有効な長さのシーケンスが得られるからです。i
  • なぜならn >= 2、後続のものj > 0を持つほぼ有効a(i, j) = a(i-1, j-1)なシーケンスに「1」を追加すると、後続のものを持つi-1ほぼ有効な長さのシーケンスが得られるからです。ji

最後に、必要な数はn、末尾に「1」がある、長さのあるほぼ有効なシーケンスの数であるため、これは

f(n, m) = a(n, 1) + a(n, 2) + ... + a(n, m)

C関数として書かれています：

int a[NMAX+1][MMAX+1];
int f(int n, int m)
{
    int i, j, s;

    // compute a(1, j):
    for (j = 0; j <= m; j++)
        a[1][j] = (j == 1);

    for (i = 2; i <= n; i++) {
        // compute a(i, 0):
        s = 0;
        for (j = 0; j <= m; j++)
            s += a[i-1][j];
        a[i][0] = s;

        // compute a(i, j):
        for (j = 1; j <= m; j++)
            a[i][j] = a[i-1][j-1];
    }

    // final result:
    s = 0;
    for (j = 1; j <= m; j++)
        s += a[n][j];
    return s;
}

行列の最後の列のみaが必要なため、ストレージ要件はさらに改善される可能性があります。ランタイムの複雑さはO(n*m).

于 2013-02-01T09:59:10.593 に答える
2

組み合わせに関する洞察があまりなくても、DP でこれに取り組むことができます。left # n,m rightを長さ n のバイナリ文字列の数と呼びましょう。連続する 1 の部分文字列は m より長くなく、文字列 left で始まり、文字列 right で終わります。明らかに、 1 # n-2,m 1を見つけたいと思っています。

重要な観察は単純に、left # n,m right = left+'1' # n-1,m right + left+'0' # n-1,m right

js での単純化された実装 (小さな m で機能するかどうかは不明で、一般的にはテストされていません):

function hash(n,m) {

   return _('1',n-2);

   function _(left,n){
      if (m+1 <= left.length && left.lastIndexOf('0') <= left.length-m-2)
         return 0;
      if (n==0)
         return (m <= left.length &&
                 left.lastIndexOf('0') <= left.length-m-1 ? 0:1);
      return _(left+'1',n-1) + _(left+'0',n-1);
   }

}

hash(5,3); // 7

もちろん、これはブルート フォースよりも効率的ですが、実行時の複雑さは依然として指数関数的であるため、n の値が大きい場合は実用的ではありません。

于 2013-02-01T09:00:15.173 に答える