54. Spiral Matrix

source: https://leetcode.com/problems/spiral-matrix/

Question

Given an m x n matrix, return all elements of the matrix in spiral order.

思路1

这题的思路其实很直接，就是改变方向：

• 方向顺序是：right => down => left => up
• 排除已经遍历过的行列

稍微注意的是，matrix的取数据是matrix[y][x].

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  const m = matrix.length,
    n = matrix[0].length,
    ret = [],
    // 已遍历的x轴
    passX = [],
    // 已遍历的y轴
    passY = [];
  let order = 0,
    x = 0,
    y = 0;
  while (ret.length !== m * n) {
    if (matrix[y]?.[x] !== undefined) ret.push(matrix[y][x]);
    // 下一个点
    switch (order) {
      // right
      case 0:
        if (x === n - 1 || passX.includes(x + 1)) {
          passY.push(y);
          order = (order + 1) % 4;
          y += 1;
        } else {
          x += 1;
        }
        break;
      // down
      case 1:
        if (y === m - 1 || passY.includes(y + 1)) {
          passX.push(x);
          order = (order + 1) % 4;
          x -= 1;
        } else {
          y += 1;
        }
        break;
      // left
      case 2:
        if (x === 0 || passX.includes(x - 1)) {
          passY.push(y);
          order = (order + 1) % 4;
          y -= 1;
        } else {
          x -= 1;
        }
        break;
      // up
      case 3:
        if (y === 0 || passY.includes(y - 1)) {
          passX.push(x);
          order = (order + 1) % 4;
          x += 1;
        } else {
          y -= 1;
        }
        break;
      default:
        break;
    }
  }
  return ret;
};

思路2

也是改变方向，但是细节上稍有不同。

• 把已经遍历过的位置置空
• 如果是遍历到了空的位置，退回一步

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    const ret = [];
    const totalLength =  matrix[0].length * matrix.length;
    // 顺时针方向
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let x = 0;
    let y = 0;
    let directionIndex = 0;
    let [offsetY, offsetX] = directions[directionIndex % 4];
    while (ret.length !== totalLength) {
        const v = matrix[y]?.[x];
        if (v === undefined) {
            // 撤销上一步的移动
            x = x - offsetX;
            y = y - offsetY;
            // 改变方向
            directionIndex += 1;
            [offsetY, offsetX] = directions[directionIndex % 4];
        } else {
            // 置空这个位置，防止重复遍历
            matrix[y][x] = undefined;
            ret.push(v);
        }
        // 下一步操作的位置
        x = x + offsetX;
        y = y + offsetY;
    }
    return ret;
};

End

做题目要有耐心，做复杂的题目要注意细节。