螺旋矩阵I、II

54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 :::info 示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7] :::

思路

方法一

记录一个数组，按照右、下、左、上的方向不断从(0,0)前进。
当遇到边界或者已经访问过的元素时，切换方向，每访问一个元素就把结果放入res中，直到res数组长度与矩阵大小一致时，就返回结果。
这里方向用 dirs 表示 4 个方向对应的偏移坐标，通过 currentIndex 指针不断递增来维护当前的方向，由于可能会超出方向数组的长度，所以每次取值都对 4 取余即可。

var spiralOrder = function(matrix) {
    const m = matrix.length;
    if (!m) return [];
    const n = matrix[0].length;
    // 遍历方向
    const dirs = [
        [0, 1],  // 右
        [1, 0],  // 下
        [0, -1], // 左
        [-1, 0]  // 上
    ]
    // 记录被访问过的元素
    let visited = [];
    for (let i = 0; i < m; i++) {
        visited[i] = [];
    }
    // 结果数组
    const res = [];
    // 矩阵长度
    const matrixLen = m * n;
    let curIndex = 0;
    // 确定当前遍历元素是否到达边界或者已经遍历过
    const isValid = (x, y) => {
        return x >= 0 && x < m && y >= 0 && y < n && !visited[x][y];
    }
    const helper = (x, y) => {
        res.push(matrix[x][y]);
        if (res.length === matrixLen) return res;
        visited[x][y] = true;
        let [diffX, diffY] = dirs[curIndex % 4];
        let [nextX, nextY] = [x + diffX, y + diffY];
        if (!isValid(nextX, nextY)) {
            [diffX, diffY] = dirs[++curIndex % 4];
            nextX = x + diffX;
            nextY = y + diffY;
        }
        helper(nextX, nextY);
    }
    helper(0, 0);
    return res;
};

方法二

直接遍历，每遍历完一层后，将对应方向的位置缩小或增大即可。

var spiralOrder = function(matrix) {
    if(!matrix.length) return []
    let n = matrix.length
    let m = matrix[0].length
    let total = n*m
    let top = 0,bottom = n-1
    let left = 0,right = m-1
    let res = []
    while(res.length < total){
        for(let i=left;i<=right;i++) res.push(matrix[top][i]) // 从左到右
        top++
        for(let i=top;i<=bottom;i++) res.push(matrix[i][right]) // 从上到下
        right--
        /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
        if(res.length === total) break
        for(let i=right;i>=left;i--) res.push(matrix[bottom][i]) // 从右到左
        bottom--
        for(let i=bottom;i>=top;i--) res.push(matrix[i][left]) // 从下到上
        left++
    }
    return res
};

59. 螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 :::info 示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
] :::

思路

先生成nn矩阵并将元素置为0，剩下按照 *螺旋矩阵I 的解题思路去做即可。

var generateMatrix = function(n) {
    if (!n) return [];
    // 创建矩阵
    const res = new Array(n).fill(0).map(() => new Array(n).fill(0));
    // 当前元素值
    let curValue = 1;
    // 当前边界
    let top = 0, bottom = n - 1;
    let left = 0, right = n - 1;
    // 矩阵长度
    let total = n * n;
    while (curValue <= total) {
        for (let i = left; i <= right; i++) {
            res[top][i] = curValue;
            curValue++;
        }
        top++; 
        for (let i = top; i <= bottom; i++) {
            res[i][right] = curValue;
            curValue++;
        }
        right--;
        for (let i = right; i >= left; i--) {
            res[bottom][i] = curValue;
            curValue++;
        }
        bottom--;
        for (let i = bottom; i >= top; i--) {
            res[i][left] = curValue;
            curValue++
        }
        left++;
    }
    return res
};