给定一个长度任意的只包含 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;
};