• LeetCode-剑指29-顺时针打印矩阵


    在这里插入图片描述

    1、模拟移动

    我们可以模拟按顺序移动的过程来输出每一个位置上的数字。为了方便移动我们可以定义一个二维数组directions用于记录每次移动之后当前的具体位置,并利用一个二维数组visited来记录哪些位置已经被访问过了。当下一步的位置超出当前的矩形范围或者已经被访问过时,我们需要改变前进的方向,使用 ( d i r e c t i o n I n d e x + 1 ) % 4 (directionIndex + 1) \% 4 (directionIndex+1)%4来控制具体应该加上哪一位。

    class Solution {
    public:
        vector<vector<int>> directions{{0,  1},
                                    {1,  0},
                                    {0,  -1},
                                    {-1, 0}};
    
        vector<int> spiralOrder(vector<vector<int>> &matrix) {
            if (matrix.size() == 0) {
                return {};
            }
    
            int rows = matrix.size(), columns = matrix[0].size();
            vector<vector<bool>> visited(rows, vector<bool>(columns));
            int total = rows * columns;
            vector<int> order(total);
    
            int row = 0, column = 0;
            int directionIndex = 0;
            for (int i = 0; i < total; i++) {
                order[i] = matrix[row][column];
                visited[row][column] = true;
                int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                    directionIndex = (directionIndex + 1) % 4;
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return order;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2、模拟遍历

    我们可以通过记录剩余矩形可访问区域的长宽坐标来进行后续的访问。我们可以假设当前可访问区域左上角的位置是 ( t o p , l e f t ) (top,left) (top,left),右下角的位置是 ( b o t t o m , r i g h t ) (bottom,right) (bottom,right)。我们可以按照这样的顺序进行依次访问:
    1、从左到右遍历最上一行,从 ( t o p , l e f t ) (top,left) (top,left) ( t o p , r i g h t ) (top,right) (top,right)
    2、从上到下遍历最右列,从 ( t o p + 1 , r i g h t ) (top+1,right) (top+1,right) ( b o t t o m , r i g h t ) (bottom,right) (bottom,right)
    3、若 l e f t < r i g h t leftleft<right t o p < b o t t o m toptop<bottom,从右到左遍历最下一行,从 ( b o t t o m , r i g h t − 1 ) (bottom,right-1) (bottom,right1) ( b o t t o m , l e f t + 1 ) (bottom,left+1) (bottom,left+1)
    4、从下到上遍历最左一行,从 ( b o t t o m , l e f t ) (bottom,left) (bottom,left) ( t o p + 1 , l e f t ) (top+1,left) (top+1,left)
    5、遍历完一层之后我们将 l e f t left left t o p top top加一,将 b o t t o m bottom bottom r i g h t right right减一。

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            if (matrix.size() == 0 || matrix[0].size() == 0) {
                return {};
            }
    
            int rows = matrix.size(), columns = matrix[0].size();
            vector<int> order;
            int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
            while (left <= right && top <= bottom) {
                for (int column = left; column <= right; column++) {
                    order.push_back(matrix[top][column]);
                }
                for (int row = top + 1; row <= bottom; row++) {
                    order.push_back(matrix[row][right]);
                }
                if (left < right && top < bottom) {
                    for (int column = right - 1; column > left; column--) {
                        order.push_back(matrix[bottom][column]);
                    }
                    for (int row = bottom; row > top; row--) {
                        order.push_back(matrix[row][left]);
                    }
                }
                left++;
                right--;
                top++;
                bottom--;
            }
            return order;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
  • 相关阅读:
    设备远程维护与人工现场维护相比优势在哪?
    linux系统资源监控和找最耗资源的进程
    【Pinia和Vuex区别】
    【稳定性】秘密武器--功能开关技术
    Go 语言学习总结(9)—— Go 与 Java 全面对比总结
    2022年最新宁夏道路运输安全员模拟真题题库及答案
    IOday7
    【无标题】
    【C语言】内存泄漏调试方式
    Jenkins 安装BlueOcean
  • 原文地址:https://blog.csdn.net/weixin_43825194/article/details/127739606