54. Spiral Matrix

Leetcode link

题目简介

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */

题目给我们一个 m*n 的矩阵，要求我们从左上角开始螺旋向内输出所有元素的值

解题思路

这题的关键是我们要如何让指针按照我们想要的顺序指向各个元素

起始的元素必定是 [0, 0] 我们需要两个变量 [dx, dy] 来决定下一步要去到哪里

dx，dy 的值应该有 4 个状态，且状态之间变化顺序如下

[1, 0] => [0, 1] => [-1, 0] => [0, -1] => [1, 0] => ...

满足状态变化的条件有两个：

1. 当 x+dx 或 y+dy 超过了 matrix 的边界
2. 当 [x+dx, y+dy] 碰到了原来经过的元素

最后我们需要准备一个数组 res 来保存这个遍历过程经过的元素

Javascript

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    const width = matrix[0].length
    const height = matrix.length
    const res = []
    let x = 0
    let y = 0
    // [dx, dy]: [1, 0] => [0, 1] => [-1, 0] => [0, -1]
    let dx = 1
    let dy = 0

    for (let i = 0; i < width * height; i++) {
        res.push(matrix[y][x])
        matrix[y][x] = '.'

        if (!(x + dx >= 0 && x + dx < width && y + dy >= 0 && y + dy < height) || matrix[y + dy][x + dx] === '.') {
            ;[dx, dy] = [-dy, dx]
        }

        x += dx
        y += dy
    }

    return res
};