如何确定一个值的块是否能适配到一个数组中。

Question

给定一个长度任意的只包含 1 和 0 的输入数组，例如：

[0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

如何（最有效地）计算一个新数组，详细说明能否放入大小为n的0块到输入中？

示例：

output现在表示

1 == 'Yes a zero chunk that size could go here' 0 == 'Couldn't fit a chunk that size there'

Chunk size = 1 ([0]): [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]

Chunk size = 2 ([0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]

Chunk size = 3 ([0,0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]

Chunk size = 4 ([0,0,0,0]): [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

我正在使用ES6，因此任何语言特性都可以。

编辑：

输出不应只是“yes”/“no”块大小为“n”的块是否适合这里。更具体地说，它需要是相同长度的数组，其中“1”/“true”数组值表示以下内容之一：

是的，大小为'n'的块可以在此处开始并适合，或

是的，此槽可包含在其之前启动的大小为'n'的块

对于第二点，这意味着对于块大小3：

input = [1, 0, 0, 0, 0, 1];

output = [0, 1, 1, 1, 1, 0];

编辑2：

这是我想出的函数，但似乎效率很低：

const calculateOutput = (input, chunkSize) => {
  const output = input.map((value, index) => {
    let chunkFitsHere = false;

    const start = (index - (chunkSize) >= 0) ? index - (chunkSize) : 0;
    const possibleValues = input.slice(start, index + chunkSize);
    possibleValues.forEach((pValue, pIndex) => {
      let consecutives = 0;
      for (let i = 0; i < possibleValues.length - 1; i += 1) {
        if (consecutives === chunkSize) {
          break;
        }
        if (possibleValues[i+1] === 0) {
          consecutives += 1;
        } else {
          consecutives = 0;
        }
      }
      if (consecutives === chunkSize) {
        chunkFitsHere = true;
      }
    });
    return chunkFitsHere ? 1 : 0;
  });
  return output;
};

- Sarreph

---

请添加块大小如何影响结果的说明，除此之外，请添加您尝试过的代码。 - Nina Scholz

我很快会澄清上面的内容，并添加一个我尝试过的适当示例 - （必须为问题抽象出原始问题） - Sarreph

Answer 1

你可以通过反转数组并为映射的最后一个返回值设置标志来计算连接的空闲位置。

Array before final mapping and after, depending on n

 1  0  4  3  2  1  0  0  2  1  0  0  0  3  2  1  0  2  1  array with counter
 1  0  4  4  4  4  0  0  2  2  0  0  0  3  3  3  0  2  2  array same counter
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --  ------------------
 1  0  1  1  1  1  0  0  1  1  0  0  0  1  1  1  0  1  1  n = 1
 0  0  1  1  1  1  0  0  1  1  0  0  0  1  1  1  0  1  1  n = 2
 0  0  1  1  1  1  0  0  0  0  0  0  0  1  1  1  0  0  0  n = 3
 0  0  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  n = 4

function chunk(array, n) {
    return array
        .slice()
        .reverse()
        .map((c => v => v ? c = 0 : ++c)(0))
        .reverse()
        .map((l => v => l = v && (l || v))(0))
        .map(v => +(v >= n));
}

var array = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0];

console.log(chunk(array, 1).join(' '));
console.log(chunk(array, 2).join(' '));
console.log(chunk(array, 3).join(' '));
console.log(chunk(array, 4).join(' '));

如果你只想在最后保留一个映射，那么请移除最后两个 map 并使用。

.map((l => v => l = +(v && (v >= n || l)))(0));

用于最终映射。

- Nina Scholz

---

这个解决方案很漂亮，而且教会了我 Array.prototype.reverse() 的存在！计数器也非常有帮助，可以说明它是如何检查周围的空格的。 - Sarreph

Answer 2

你可以遍历数组一次，计算连续的0的长度。如果长度足够长，则用相同长度的1填充输出。

请注意，您可以同时为不同的块长度填充输出（在2d数组的行中填充块，行索引不超过zerolen）。

Python代码：

def zerochunks(a, n):
    l = len(a)
    result = [0] * l   #list of l zeros

    zerolen = 0
    for i in range(l + 1):
        ### Short circuit evaluation to shorten code
        if (i==l) or (a[i] != 0):   
            if (zerolen >= n):   #series of zeros is finished here
                for j in range(i - zerolen, i):
                    result[j] = 1
            zerolen  = 0
        else:
            zerolen += 1

    return result

print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 1))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 2))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 3))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 4))
print(zerochunks([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 5))

>>> 
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

获取所有在maxn范围内的数组块的函数：

def zerochunksall(a, maxn):
    l = len(a)
    result = [[0] * l for i in range(maxn)]

    zerolen = 0
    for i in range(l + 1):
        if (i==l) or (a[i] != 0):
            for k in range(0, zerolen):
                for j in range(i - zerolen, i):
                    result[k][j] = 1
            zerolen  = 0
        else:
            zerolen += 1

    return result

print(zerochunksall([0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0], 5))
 >>
[[1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1],
 [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1], 
 [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0], 
 [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

- MBo

---

谢谢您的回复 - 理想情况下，解决方案需要使用JS来帮助其他人。虽然算法很有趣，但我会考虑将其移植到JS中！ - Sarreph

我不知道如何正确组织JS数组/列表，所以决定用Python演示工作代码。希望移植很简单。 - MBo

Answer 3

function fit(input, n) {
    var output = [];
    for(var i = 0; i < input.length; i++) {
        var fit = true;
        for(var j = i; j < i + n; j++) {
            if(j >= input.length || input[j]) {  // either over the array size or occupied
                fit = false;
                break;
            }
        }
        output.push(fit);
    }
    return output;
}

var input = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0];
console.log(fit(input, 1).map(v => +v));
console.log(fit(input, 2).map(v => +v));
console.log(fit(input, 3).map(v => +v));
console.log(fit(input, 4).map(v => +v));

输出

[ 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
[ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 ]
[ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

这些似乎并不完全符合您的预期输出，但这可能是因为我假设数组中的标志应该标记块的开始（即您能够从该位置开始在数组中放置N个真值）。

（请参见下面，其中e = 您的预期结果，n = 我的算法的输出。）

input = [ 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 ]
e = 2 = [ 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
n = 2 = [ 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 ]
                         ====  ====  ====              ====

- AKX

---

谢谢你，这很接近我想要的输出数组，就像我在问题示例中所描述的。不过我需要在我的问题中澄清一下，因为输出中的1可能意味着“是的，这个位置可以是一个块的开头，也可以是一个可行块的一部分”。 - Sarreph

Answer 4

您可以使用 array.prototype.some 检查块是否适合从输入数组的某个索引开始。要检查具有实际长度的块是否适合，您可以使用 array.prototype.every：

var input = [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0];
var chunk = [0,0,0];
var res = input.some((e, i) => chunk.every((c, j) => input[i + j] === c));
console.log(res);

var input = [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0];
var chunk = [0, 0, 0, 0, 0, 0, 0, 0];
var res = input.some((e, i) => chunk.every((c, j) => input[i + j] === c));
console.log(res);

- Faly

Answer 5

你可以使用 some 方法，然后如果当前元素是 0，你可以从当前索引处切割数组的一部分，并检查它是否全部为零。

const data = [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

function check(arr, n) {
  let chunk = Array(n).fill(0).join('');
  return arr.some((e, i) => e === 0 && arr.slice(i, i + n).join('') == chunk)
}

console.log(check(data, 3))
console.log(check(data, 4))
console.log(check(data, 5))

- Nenad Vracar