2

给定二进制数 n 和最大连续出现数 m，求不同可能二进制数的个数。此外，最左边和最右边的位必须为 1。

例如 n = 5，m = 3。

计数为7：10001 10011 10101 10111 11001 11011 11101

请注意，我们排除了 11111，因为其中存在太多连续的 1。

这是我最近遇到的一个面试问题，一直困扰着我。我不想暴力检查每个数字的合法性，因为 n 可以大于 32。

4

2 回答 2

3

如果二进制序列以“1”开头并且最多有连续的“1”位，我们就称它为几乎有效的二进制序列。m

Fori = 1, ..., n和j = 0, ..., mlet是长度以完全连续的“1”数字结尾a(i, j)的几乎有效序列的数量。ij

然后

  • a(1, 1) = 1和a(1, j) = 0 for j != 1，因为“1”是唯一几乎有效的长度为 1 的序列。
  • 因为我们有n >= 2，因为将“0”附加到任何几乎有效的长度序列都会给出一个几乎有效的以“0”结尾的长度序列。j = 0a(i, 0) = a(i-1, 0) + a(i-1, 1) + ... + a(i-1, m)i-1i
  • 因为我们有n >= 2，因为将“1”附加到带有尾随的几乎有效的序列会给出一个几乎有效的长度序列和尾随的序列。j > 0a(i, j) = a(i-1, j-1)i-1ji

最后，想要的数字是长度几乎有效且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 回答