BFE.devAI解答 - JavaScript 代码题
174. CSS Grid Layout auto-placement algorithm - sparse

这道题要求实现一个自动对齐算法，其工作方式受 grid-auto-flow 属性的控制，而默认的对齐模式是 sparse。因此我们需要实现一个函数，可以接收一个符合要求的输入并返回一个二维数组，用于表示每个格子所占的元素的编号。

在默认的情况下，自动对齐算法会使所有元素自动放置。因此我们可以从这种情况开始，尝试在二维数组中添加元素。具体而言，我们可以在二维数组中遍历每个单元格，并判断该单元格是否已经被占用。如果没有，我们就可以尝试在其中放置元素。

针对每个元素，我们需要先处理它的 CSS 样式，确定它应该占据哪些行列。同时，我们需要记录这个元素在所占用的行列上的最大值。这样就可以根据上面的方法遍历每个单元格，判断某个元素是否可以放置在某个单元格。

如果一个元素不能被放置在任何单元格上，那么就说明这个输入是无效的。在循环结束后，我们可以返回被填充的二维数组。

实现如下：

type Grid = Array<Array<number>>
type Item = {
  id: number,
  style?: {
    gridRowStart?: number | string,
    gridRowEnd?: number | string,
    gridColumnStart?: number | string
    gridColumnEnd?: number | string
  }
}

function layout(rows: number, columns: number, items: Array<Item>): Grid {
  const grid: Grid = new Array(rows).fill(null).map(() => new Array(columns).fill(0))
  for (let i = 0; i < items.length; i++) {
    const item = items[i]
    let [xStart, xEnd, yStart, yEnd] = [0, 0, 0, 0]
    if (item.style && item.style.gridColumnStart) {
      xStart = parseGridLine(item.style.gridColumnStart)
      xEnd = item.style.gridColumnEnd ? parseGridLine(item.style.gridColumnEnd) : xStart + 1
    } else {
      [xStart, xEnd] = [0, columns]
    }
    if (item.style && item.style.gridRowStart) {
      yStart = parseGridLine(item.style.gridRowStart)
      yEnd = item.style.gridRowEnd ? parseGridLine(item.style.gridRowEnd) : yStart + 1
    } else {
      [yStart, yEnd] = [0, rows]
    }
    let success = false
    for (let y = yStart; y < yEnd; y++) {
      for (let x = xStart; x < xEnd; x++) {
        if (grid[y][x] === 0) {
          grid[y][x] = item.id
          success = true
          break
        }
      }
      if (success) {
        break
      }
    }
    if (!success) {
      throw new Error(`Item ${item.id} cannot be placed`)
    }
  }
  return grid
}

// 解析网格线，例如 "span 2" 或 3
function parseGridLine(line: number | string): number {
  if (typeof line === 'number') {
    return line - 1
  }
  const [type, spanString] = line.split(' ')
  const span = parseInt(spanString || '1')
  if (type === 'span') {
    return span - 1
  }
  return parseInt(line) - 1
}

其中，我们添加了一个 parseGridLine 函数，用于解析 gridRowStart、gridRowEnd、gridColumnStart、gridColumnEnd 这些字符串格式的 CSS 值。函数会解析出字符串中的网格线索引，例如 "span 2" 或 3。

最后，我们可以用两个示例来验证我们的代码是否正确：

console.log(layout(3, 3, [
  {
    id: 1,
    style: {
      gridColumnStart: 'span 2'
    }
  },
  {
    id: 2,
    style: {
      gridColumnStart: 'span 2'
    }
  },
  {
    id: 3
  },
  {
    id: 4
  },
  {
    id: 5
  }
]))
// 打印：[[1, 1, 0], [2, 2, 3], [4, 5, 0]]

console.log(layout(3, 3, [
  {
    id: 1,
    style: {
      gridColumnStart: 'span 2',
      gridRowStart: 2
    }
  },
  {
    id: 2,
    style: {
      gridColumnStart: 2,
      gridColumnEnd: 'span 2'
    }
  },
  {
    id: 3
  },
  {
    id: 4
  },
  {
    id: 5
  }
]))
// 打印：[[0, 2, 2], [1, 1, 3], [4, 5, 0]]

第一个例子应该对应着下图的布局：

1 1 _
2 2 3
4 5 _

第二个例子则对应下图的布局：

_ 2 2
1 1 3
4 5 _

所以我们的代码是正确的。