剑指29：顺时针打印矩阵

传送门

nowcoder
leetcode

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
例如，如果输入如下4 X 4矩阵：

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

C++ 代码 - nowcoder

/*
    模拟：按层遍历
*/
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};

        int rows = matrix.size(), cols = matrix[0].size();
        int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
        vector<int> res;
        res.reserve(rows * cols);
        while (left <= right && top <= bottom) {
            for (int col = left; col <= right; col ++) {
                res.push_back(matrix[top][col]);
            }
            for (int row = top + 1; row <= bottom; row ++) {
                res.push_back(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int col = right - 1; col > left; col --) {
                    res.push_back(matrix[bottom][col]);
                }
                for (int row = bottom; row > top; row --) {
                    res.push_back(matrix[row][left]);
                }
            }
            left ++, right --, top ++, bottom --;
        }

        return res;
    }
};

/*
    模拟打印矩阵的路径。
    初始位置是矩阵的左上角，初始方向是向右。
    当路径超出界限或进入之前访问过的位置时，顺时针旋转，进入下一个方向。
*/
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return vector<int>();

        int rows = matrix.size(), cols = matrix[0].size();
        int total = rows * cols;
        vector<int> res(total);
        vector<vector<bool>> visited(rows, vector<bool>(cols));
        
        int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
        int r = 0, c = 0, d = 1;
        for (int i = 0; i < total; i ++) {
            res[i] = matrix[r][c];
            visited[r][c] = true;
            int a = r + dx[d], b = c + dy[d];
            if (a < 0 || a >= rows || b < 0 || b >= cols || visited[a][b]) {
                d = (d + 1) % 4;
                a = r + dx[d], b = c + dy[d];
            }
            r = a, c = b;
        }

        return res;
    }
};

C++ 代码 - leetcode

/*
    模拟：按层遍历
*/
class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if (array.size() == 0 || array[0].size() == 0) return {};

        int rows = array.size(), cols = array[0].size();
        int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
        vector<int> res;
        while (left <= right && top <= bottom) {
            for (int col = left; col <= right; col ++) {
                res.push_back(array[top][col]);
            }
            for (int row = top + 1; row <= bottom; row ++) {
                res.push_back(array[row][right]);
            }
            if (left < right && top < bottom) {
                for (int col = right - 1; col > left; col --) {
                    res.push_back(array[bottom][col]);
                }
                for (int row = bottom; row > top; row --) {
                    res.push_back(array[row][left]);
                }
            }
            left ++, right --, top ++, bottom --;
        }

        return res;
    }
};

/*
    模拟打印矩阵的路径
*/
class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if (array.size() == 0 || array[0].size() == 0) return {};

        int rows = array.size(), cols = array[0].size();
        vector<int> res(rows * cols);
        vector<vector<bool>> st(rows, vector<bool>(cols, false));
        
        int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
        int x = 0, y = 0; // 起点(x, y)
        int d = 1; // 初始方向：向右
        for (int i = 0; i < rows * cols; i ++) {
            res[i] = array[x][y];
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= rows || b < 0 || b >= cols || st[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }

        return res;
    }
};