javascript - 长度为 n 且 k 连续为 1 的二进制数组的数量

Question

Input: N = 4, K = 3 
Output: 3 // "111", "1110", "1111"

我用这段代码解决了这个问题：

function getQuantity(n, k) {
  const nums = [];
  const re = new RegExp(`^.*[1]{${k}}.*?$`, "m");

  // Convert to decimal
  var maxDecimal = Math.pow(2, n) - 1;

  // For every number between 0->decimal
  for (let i = 0; i <= maxDecimal; i++) {
    if (re.test(i.toString(2))) {
      nums.push(i.toString(2));
    }
  }

  return nums.length;
}

但我想这是开销解决方案。也许有更好的方法来解决这个问题？

标签： javascriptalgorithm

Answer 1

您的方法的复杂度为 O(2^N)。使用递归或迭代方法会产生 O(N) 复杂度。

关系是这样的：f(n+1, k) = 2*f(n, k) + 2^{n-k} - f (n-k, k)

f(n, k) = 0如果 (n < k)和f(k, k) = 1

最后一项2^{n-k} - f (n-1-k)对应于新解的附加数量，当 a1被添加到第 (n+1) 个位置时，一个0和 (k-1)1就在前面。然后还有一些n-k需要设置的位，即潜在2^{n-k}的新解决方案。但是，该术语- f(n-k, k)不需要计算已包含在该f(n, k)术语中的解决方案。