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" 或 3function 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 _

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