时间戳

首页 > 解决方案 > How to determine if chunks of a value could fit into an array

javascript - How to determine if chunks of a value could fit into an array

问题描述

Given an input array of 1s and 0s of arbitrary length, such as:

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

How can I (most efficiently) calculate a new array detailing if chunks of size n 0s which can fit into the input?

Examples

Where output now means

I'm using ES6, so any language features are fine.

EDIT:

The output shouldn't just be a 'yes'/'no' a chunk of size 'n' can fit in this array. More specifically, it needs to be an array of the same length, where a '1' / 'true' array value represents either:

On that second point, this would mean for chunk size 3:

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

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

Edit 2:

This is the function I came up with but it seems very inefficient:

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;
};

标签： javascriptarraysalgorithmecmascript-6

解决方案

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

最终映射之前和之后的数组，具体取决于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));

用于最终映射。

推荐阅读