【LeetCode】59. 螺旋矩阵II（中等）——代码随想录算法训练营Day02

题解1：模拟

思路：模拟螺旋矩阵的填充顺序，进行越界判断和是否已填充判断，当即将越界或下个位置已填充时顺时针改变填充方向。

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const res = new Array(n).fill(0).map(() => new Array(n).fill(0)); // 生成n*n的二维数组
  let dir = 0; // 方向 0右 1下 2左 3上
  let i = 0, j = 0; // 当前位置
  let dirNotChange = true; // 方向是否不变
  for (let k = 1; k <= n * n; ) {
    // 如果方向不变，则给当前位置赋值
    if (dirNotChange) {
      res[i][j] = k++;
    }
    switch (dir) {
      case 0:
        dirNotChange = j + 1 < n && res[i][j + 1] === 0; // 如果右边的位置没越界且没有赋值，则方向不变
        dirNotChange ? j++ : dir++; // 如果方向不变，则向右走，否则方向改为向下
        break;
      case 1:
        dirNotChange = i + 1 < n && res[i + 1][j] === 0; // 如果下边的位置没越界且没有赋值，则方向不变
        dirNotChange ? i++ : dir++; // 如果方向不变，则向下走，否则方向改为向左
        break;
      case 2:
        dirNotChange = j - 1 >= 0 && res[i][j - 1] === 0; // 如果左边的位置没越界且没有赋值，则方向不变
        dirNotChange ? j-- : dir++; // 如果方向不变，则向左走，否则方向改为向上
        break;
      case 3:
        dirNotChange = i - 1 >= 0 && res[i - 1][j] === 0; // 如果上边的位置没越界且没有赋值，则方向不变
        dirNotChange ? i-- : dir = 0; // 如果方向不变，则向上走，否则方向改为向右
        break;
    }
  }
  return res;
};

分析：通过边界值判定，当越界或下个位置已经填充过时，改变填充方向。由于此方法处理每条边是左闭右闭的方式，一次操作是继续填充或者改变方向，因此需记录下当前操作是否为改变方向操作，没有改变操作时再进行填充。时间复杂度为 O(n2)，空间复杂度为 O(1)。

题解2：模拟&计算

思路：模拟螺旋矩阵的填充顺序，每条边按左闭右开的规则来处理，即每条边的最后一个点当作下一条边的起点，留给下一条边去处理。定义变量 offset 记录边的偏移量，计算出每条边的长度，按顺序填充这些边。

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    const res = new Array(n).fill(0).map(() => new Array(n).fill(0));
    let count = 1;
    let startX = 0, startY = 0; // 每次转圈初始的位置
    let offset = 1; // 控制每一条边遍历的长度，每次循环右边界收缩一位
    let mid = n >> 1; // 中心元素的位置（n 为奇数）
    for (let k = 0; k < n >> 1; k++) {
        let i = startX, j = startY;
        // 上行从左向右填充（左闭右开）
        for ( ; j < n - offset; j++) {
            res[i][j] = count++;
        }
        // 右列从上向下填充
        for ( ; i < n - offset; i++) {
            res[i][j] = count++;
        }
        // 下列从右向左填充
        for ( ; j > startY; j--) {
            res[i][j] = count++;
        }
        // 左列从下向上填充
        for ( ; i > startX; i--) {
            res[i][j] = count++;
        }
        // 起始位置右下移动一格，右界收缩一位，接着进行下一圈填充
        startX++;
        startY++;
        offset++;
    }
    // 如果 n 为奇数，处理最中心元素
    if (n % 2 === 1) {
        res[mid][mid] = count;
    }
    return res;
};

分析：对比于题解1，题解1是通过边界判定来实现填充转向，而此解法直接计算出了每次在每个方向填充多少个位置。时间复杂度为 O(n2)，空间复杂度为 O(1)。

收获

在处理这种模拟类问题时，要注意循环不变量，本例中处理每条边的规则就是循环不变量。

如题解1中，每条边的边界值处理都是左闭右闭，顶点少执行一次赋值；题解2中每条边都按照左闭右开的规则来处理边界值，就不会有大问题。