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

leetcode之hot100---54螺旋矩阵（C++）

article 2024/12/22 19:42:13

思路一：模拟

模拟螺旋矩阵的路径，路径超出界限，顺时针旋转，使用一个数组记录当前数字是否被访问到，直到所有的数字全部被访问

class Solution {
    //一个静态的常量数组，用于标记螺旋矩阵的移动方向(行列变化)
    //{0, 1}：表示向右移动一格（x 不变，y+1）。
    //{1, 0}：表示向下移动一格（x+1，y 不变）。
    //{0, -1}：表示向左移动一格（x 不变，y-1）。
    //{-1, 0}：表示向上移动一格（x-1，y 不变）
    static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //判断矩阵行列是否为空，如果为空则返回空值
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return {};
        }
        vector<int> ans;
        int m = matrix.size();//行最大
        int n = matrix[0].size();//列最大
        
        
        //数字是否已经被访问的标签数组
        vector<vector<bool>> visited(m, vector<bool>(n，false));
        //记录存入答案数组中的个数
        int col = 0, row = 0;//螺旋矩阵的起始路径
        //当前方向的索引，可以取0-3,分别对应directions数组中的四个方位
        int direction_index = 0;
        for(int count = 0; count < m * n; count++){
            ans.push_back(matrix[row][col]);//将矩阵中的数字存入结果中
            visited[row][col] = true;//标记已访问的数字
            //计算下一位置
            //行变化列不动，取directions数组中的x坐标
            //列变化行不动，取directions数组中的y坐标
            int next_row = row + directions[direction_index][0];
            int next_col = col + directions[direction_index][1];
            // 判断是否需要改变移动方向（越界或已访问）
            if(next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || visited[next_row][next_col]){
                direction_index = (direction_index + 1) % 4;
            }
            //根据判断的方向进行移动
            row += directions[direction_index][0];
            col += directions[direction_index][1];
        }
        return ans;
    }
};

constexpr的使用是告诉大家该数组为一个常量表达式，在编译的过程中其值不会改变

这个方法的关键在于写出这个方向数组，我们平时做的题目中如果涉及到处理二维网格上的移动问题，例如：遍历上下左右四个方向；执行 BFS/DFS 等搜索算法；模拟迷宫、棋盘等问题中的移动逻辑，都可以使用这个方向数组

时间复杂度：O(mn)
空间复杂度：O(mn)

思路二：按层模拟

与上述方法不同的是，这个方法更像是分治的思路，将顺时针矩阵分解成不同层的矩阵，然后又把不同层分解成从左至右、从上至下、从右至左、从下至上四个方向，详解如图所示：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //矩阵行或者列为空，说明矩阵为空，则返回空值
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return {};
        }
        vector<int> ans;
        int m = matrix.size();//行最大
        int n = matrix[0].size();//列最大
                
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        while(left <= right && top <= bottom){
            //把每一层的数从左至右放入结果数组中
            for(int col = left; col <= right; col++){
                ans.push_back(matrix[top][col]);//将矩阵中的数字存入结果中
            }
            
            //把每一层的数从上至下放入结果数组中
            for(int row = top + 1; row <= bottom; row++){
                ans.push_back(matrix[row][right]);//将矩阵中的数字存入结果中
            }
            
            if(left < right && top < bottom){
                //把每一层的数从右至左放入结果数组中
                for(int col = right - 1; col > left; col--){
                    ans.push_back(matrix[bottom][col]);//将矩阵中的数字存入结果中
                }
                
                //把每一层的数从下至上放入结果数组中
                for(int row = bottom; row > top; row--){
                    ans.push_back(matrix[row][left]);//将矩阵中的数字存入结果中
                }
                
            }
            top++;
            right--;
            bottom--;
            left++;
        }
       
        return ans;
    }
};

基于上述思想，可以自行选择每一层四个方向的截止位置（也就是每一方向存入数组的最后一个数）和起始位置（也就是每一方向存入数组的第一个数），比如从左至右的截止点可以是[top, right]，也可以是[top,right - 1]，同时，从上至下的起始点也可以是[top + 1, right]，也可以是[top, right]。只要每一方向的起始点和上一方向的截止点保证连续即可