leetcode 54.螺旋矩陣＆59.螺旋矩陣II&劍指offer29.順時針列印矩陣

一、題目

54. 螺旋矩陣

給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，傳回矩陣中的所有元素。

示例 1:

輸入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
           

示例 2:

輸入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
           

二、相關知識點

數組、模拟

三、題解

1.模拟解法

順時針周遊，設定邊界：上，下，左，右（t, ll, l, r)，注意跳出時機

時間複雜度O(n*m),空間複雜度O(1);

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matix.empty())
            return {};
        vector<int> ans;
        int l = 0, r = matrix[0].size() - 1, t = 0, ll = matrix.size() - 1;
        int cnt = matrix[0].size() * matrix.size();
        while (cnt) {
            for (int i = l; i <= r && cnt > 0; i++, cnt--) {
                ans.push_back(matrix[t][i]);
            }
            t++;
            for (int i = t; i <= ll && cnt > 0; i++, cnt--) {
                ans.push_back(matrix[i][r]);
            }
            r--;
            for (int i = r; i >= l && cnt > 0; i--, cnt--) {
                ans.push_back(matrix[ll][i]);
            }
            ll--;
            for (int i = ll; i >= t && cnt > 0; i--, cnt--) {
                ans.push_back(matrix[i][l]);
            }
            l++;
        }
        return ans;
    }
};
           

2.方向數組解法

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int nr = matrix.size(); if (nr == 0) return {};
        int nc = matrix[0].size(); if (nc == 0) return {}; // 為了美學！！！
        vector<int> res;
        vector<vector<int> > dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<int> nSteps{nc, nr-1}; 
        int iDir = 0; // 初始化移動方向
        int ir = 0, ic = -1; // 周遊的起點
        while (nSteps[iDir%2]) {
            for (int i = 0; i < nSteps[iDir%2]; ++i) {
                ir += dirs[iDir][0], ic += dirs[iDir][1];
                res.push_back(matrix[ir][ic]);
            }
            nSteps[iDir%2]--; // 縮減水準或垂直方向的移動次數
            iDir = (iDir + 1) % 4; // 更新下一次移動的方向
        }
        return res;
    }
};// 參見國際版高贊
           

四、精選題解

原理上剖析邊界問題,分層周遊

⭐方向數組解法

五、相關題目

59. 螺旋矩陣 II

給定一個正整數 n，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣。

示例:

輸入: 3
輸出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]
           

ac代碼：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> > res(n, vector<int>(n, 0));
        int num = 0;
        vector<vector<int> > dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 
        int iDir = 0; // 初始化移動方向， 0， 1， 2 ，3 左下右上
        vector<int> nSteps{n, n-1}; // 初始化水準和垂直移動距離
        int ir = 0, ic = -1; // 初始移動起點
        while (nSteps[iDir%2]) { // 水準或垂直還可以移動
            for (int i = 0; i < nSteps[iDir%2]; ++i) {
                ir += dirs[iDir][0], ic += dirs[iDir][1];
                res[ir][ic] = ++num;
            }
            nSteps[iDir%2]--;
            iDir = (iDir + 1) % 4;
        }
        return res;
    }
};
           

劍指 Offer 29. 順時針列印矩陣

輸入一個矩陣，按照從外向裡以順時針的順序依次列印出每一個數字。

示例 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]
           

ac代碼:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int nr = matrix.size(); if (nr == 0) return {};
        int nc = matrix[0].size();
        vector<int> ret(nr*nc, 0);
        int t = 0, d = nr - 1, l = 0, r = nc - 1;
        int num = 0;
        while (num < nr*nc ) {
            for (int i = l; i <= r && num < nr*nc; i++) {
                ret[num++] = matrix[t][i];
            }
            t++;
            for (int i = t; i <= d && num < nr*nc; i++) {
                ret[num++] = matrix[i][r];
            }
            r--;
            for (int i = r; i >= l && num < nr*nc; i--) {
                ret[num++] = matrix[d][i];
            }
            d--;
            for (int i = d; i >= t && num < nr*nc ; i--) {
                ret[num++] = matrix[i][l];
            }
            l++;
        }
        return ret;
    }
}; // 可以用4個while循環