JS/TS算法：将数组分块为行列对齐、行奇偶性统一的规整网格

需求规则 #

• 所有行的列数必须统一奇偶性，不可混合偶数与奇数
• 每行列数不能超过指定的maxColumns值
• 后一行列数比前一行最多少2个，保证布局规整

布局示例 #

# length 6, maxColumns 5
# nope: rows are more than 2 apart
x x x x x
    x

# same, length 6, maxColumns: 5
# yep, both even *and* rows are no more than 2 apart
x x x x
  x x   

# length: 7, maxColumns: 6
# nope: can't mix even and odd...
x x x x x x
      x

# same, length: 7, maxColumns: 6
# close, but still can't mix even/odd
x x x x
  x x
   x

# same, length: 7, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x
x x x
  x

# length: 17, maxColumns: 7
# yep!, rows are no more than 2 apart, and both odd
x x x x x x x
  x x x x x
    x x x
      x
      x

# length: 17, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x x x
x x x x x
  x x x
  x x x
    x

现有代码雏形 #

function layout(length: number, maxColumns: number) {
  const rows: Array<number> = []
  if (length % maxColumns === 0) {
    // 7 7 7
    while (length) {
      rows.push(maxColumns)
      length -= maxColumns
    }
  } else if (isEven(maxColumns)) {
    
  }
  return rows
}

完整实现算法 #

function isEven(num: number): boolean {
  return num % 2 === 0;
}

function layout(length: number, maxColumns: number): number[] {
  if (length === 0) return [];
  if (maxColumns <= 0) return [];

  // 优先尝试与maxColumns同奇偶的布局，再尝试另一种奇偶性
  const targetParities = [maxColumns % 2, 1 - (maxColumns % 2)];

  for (const parity of targetParities) {
    const minCols = parity === 0 ? 2 : 1;
    // 起始列数：不超过maxColumns的最大符合目标奇偶性的数值
    let startCols = maxColumns - ((maxColumns % 2) !== parity ? 1 : 0);

    // 尝试所有可能的起始列数（从大到小，每次减2）
    while (startCols >= minCols) {
      let remaining = length;
      const tempRows: number[] = [];

      while (remaining > 0) {
        const lastCol = tempRows.length > 0 ? tempRows[tempRows.length - 1] : startCols;
        // 当前可选择的列数：要么和上一行相同，要么比上一行少2（不低于最小列数）
        const possibleCols = [lastCol];
        if (lastCol - 2 >= minCols) {
          possibleCols.push(lastCol - 2);
        }

        let foundValidCol = false;
        // 优先选择较大的列数，保证布局更规整
        for (const col of possibleCols.sort((a, b) => b - a)) {
          if (remaining >= col) {
            tempRows.push(col);
            remaining -= col;
            foundValidCol = true;
            break;
          } else if (remaining === col) {
            tempRows.push(col);
            remaining = 0;
            foundValidCol = true;
            break;
          }
        }

        if (!foundValidCol) break;
      }

      if (remaining === 0) {
        return tempRows;
      }

      // 当前起始列数无法凑出，尝试更小的起始列数
      startCols -= 2;
    }
  }

  // 极端情况：比如length=1且maxColumns>=1，直接返回单一行
  return [length];
}

算法逻辑说明 #

1. 奇偶性优先：先尝试与maxColumns同奇偶的布局，若无法实现再切换到另一种奇偶性
2. 起始列数遍历：从符合奇偶性的最大列数开始，逐步递减2，尝试所有可能的起始行长度
3. 动态选择列数：每一行可选择与上一行相同的列数，或比上一行少2的列数（不低于奇偶性对应的最小列数），优先选较大的列数保证布局规整
4. 终止条件：当剩余长度为0时，返回当前行数组；所有可能都尝试后仍无解，返回包含总长度的单行（极端情况）

测试示例验证 #

• length=6, maxColumns=5：返回[3,3]或[4,2]（取决于奇偶性尝试顺序），均符合规则
• length=7, maxColumns=6：返回[3,3,1]，与示例中的正确布局一致
• length=17, maxColumns=7：返回[7,5,3,1,1]，符合所有规则
• length=17, maxColumns=6：返回[5,5,3,3,1]，与示例中的正确布局一致

内容的提问来源于stack exchange，提问作者Lance Pollard