当前位置：首页 > article >正文

LeetCode54. 螺旋矩阵（2024秋季每日一题 21）

article 2024/9/24 10:29:14

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1：
在这里插入图片描述

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：
在这里插入图片描述

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

$m == ma t r i x . l e n g t h$
$n == ma t r i x [i] . l e n g t h$
$1 <= m, n <= 10$
$- 100 <= ma t r i x [i] [j] <= 100$

思路：

1. 将右、下、左、上分别映射为 0～3 个方向
1. 刚开始从 (0, 0) 坐标位置开始出发，从 0 方向（右方向）开始走
1. 当此时的坐标越界，或者已经访问过元素，开始转换方向 (t + 1) % 4
1. 直到遍历的元素等于原数组元素的个数，则返回

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        bool st[n][m];
        memset(st, 0, sizeof st);
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        int t = 0, cnt = n * m;
        vector<int> res;
        int x = 0, y = 0;
        st[0][0] = true;
        res.push_back(matrix[0][0]);
        while(res.size() != cnt){
            int a = x + dx[t], b = y + dy[t];
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
                t = (t + 1) % 4;
                continue;
            }
            x = a, y = b;
            st[a][b] = true;
            res.push_back(matrix[x][y]);
        }
        return res;
    }
};