[LeetCode] Spiral Matrix I, II

Spiral Matrix I

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路：Spiral Matrix I

与Rotate Image那题类似，一层一层处理。但这题有两个注意点：

1. m和n可以不同，所以对于第i层来说，最后一行为lastRow = m-1-i，而最后一列为lastCol = n-1-i。所以层数由min(m,n)决定。

2. 当min(m,n)为奇数时，最后一层为一行或一列，需要特殊处理。

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

class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> ret; if(matrix.empty() || matrix[0].empty()) return ret; int m = matrix.size(), n = matrix[0].size(); int nlvl = (min(m,n)+1)/2; for(int i=0; i<nlvl; i++) { int lastRow = m-1-i; int lastCol = n-1-i; if(lastRow==i) { // one row remain for(int j=i; j<=lastCol; j++) ret.push_back(matrix[i][j]); } else if(lastCol==i) { // one col remain for(int j=i; j<=lastRow; j++) ret.push_back(matrix[j][i]); } else { for(int j=i; j<lastCol; j++) ret.push_back(matrix[i][j]); for(int j=i; j<lastRow; j++) ret.push_back(matrix[j][lastCol]); for(int j=lastCol; j>i; j--) ret.push_back(matrix[lastRow][j]); for(int j=lastRow; j>i; j--) ret.push_back(matrix[j][i]); } } return ret; } };

思路：Spiral Matrix II

II比I简单，一样的按层访问法。由于是正方形矩阵，当n为奇数时，最后只会剩下一个数字即matrix[n/2][n/2]，最后不要忘记补填上这个数字。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: vector<vector<int> > generateMatrix(int n) { vector<vector<int>> ret(n,vector<int>(n,0)); int nlvl = n/2; int val = 1; for(int i=0; i<nlvl; i++) { int last = n-1-i; for(int j=i; j<last; j++) ret[i][j] = val++; for(int j=i; j<last; j++) ret[j][last] = val++; for(int j=last; j>i; j--) ret[last][j] = val++; for(int j=last; j>i; j--) ret[j][i] = val++; } if(n%2==1) ret[n/2][n/2] = val; return ret; } };