**54、Spiral Matrix **
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].
或者
**59、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 ]
]
解答技巧：
对付所有的旋转矩阵类的问题，最重要的就是扫描策略，以及判断下一行是否存在。
我们采取的扫描策略是：横向的行所有的都扫描，纵向的行只扫描夹在行中间的。
比如先扫：1 2 3，然后再扫：4，然后再扫：5 6 7，再扫：8
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> rec;
if(matrix.empty()||matrix[0].empty()) //判断矩阵是否为空的方法
return rec;
int m = matrix.size();
int n = matrix[0].size();
int t = (min(m,n)-1)/2;
int k=0;
while(k<=t)
{
for(int j=k;j<n-k;j++)
rec.push_back(matrix[k][j]);
for(int i=k+1;i<m-1-k;i++)
rec.push_back(matrix[i][n-1-k]);
if(m-1-k>k) //必须存在
for(int j=n-1-k;j>=k;j--)
rec.push_back(matrix[m-1-k][j]);
if(k<n-k-1) //必须存在
for(int i=m-2-k;i>k;i--)
rec.push_back(matrix[i][k]);
k++;
}
return rec;
}
};
特别要注意的是下面两行条件判断的代码：
if(m-1-k>k) //必须存在
for(int j=n-1-k;j>=k;j--)
rec.push_back(matrix[m-1-k][j]);
if(k<n-k-1) //必须存在
for(int i=m-2-k;i>k;i--)
rec.push_back(matrix[i][k]);
如果存在第三次扫描，则最下面一行必须要存在，也就是说：m-1-k>k，这样才能说下一行存在，必须判断矩阵的行数是否足够
比如说对于矩阵：
1 2 3
6 5 4
如果存在第四次扫描，则最后一行即最左边的一行必须存在，也就是说：k<n-1-k，这样才能说最后一行存在，必须判断矩阵的列数是否足够
比如说对于矩阵：
1 2
6 3
5 4
总之，就是要判断矩阵的行数必须大于两行，列数必须大于两列，才会有第三和第四次扫描的存在。
算法：
- Spiral Matrix
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> rec;
if(matrix.empty()||matrix[0].empty()) //判断矩阵是否为空的方法
return rec;
int m = matrix.size();
int n = matrix[0].size();
int t = (min(m,n)-1)/2;
int k=0;
while(k<=t)
{
for(int j=k;j<n-k;j++)
rec.push_back(matrix[k][j]);
for(int i=k+1;i<m-1-k;i++)
rec.push_back(matrix[i][n-1-k]);
if(m-1-k>k) //行必须存在
for(int j=n-1-k;j>=k;j--)
rec.push_back(matrix[m-1-k][j]);
if(k<n-k-1) //列必须存在
for(int i=m-2-k;i>k;i--)
rec.push_back(matrix[i][k]);
k++;
}
return rec;
}
};
- Spiral Matrix II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<int> temp(n,0);
vector<vector<int>> rec(n,temp);
if(n<=0)
return rec;
int t= (n-1)/2;
int k = 0;
int N = 0;
while(k<=t)
{
for(int j=k;j<=n-1-k;j++)
rec[k][j] = ++N;
for(int i=k+1;i<=n-2-k;i++)
rec[i][n-1-k] = ++N;
if(n-1-k>k)
for(int j=n-1-k;j>=k;j--)
rec[n-1-k][j] = ++N;
if(k<n-1-k)
for(int i=n-2-k;i>=k+1;i--)
rec[i][k] = ++N;
k++;
}
return rec;
}
};
剑指offer
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> rec;
if(matrix.empty()||matrix[0].empty())
return rec;
int m = matrix.size();
int n = matrix[0].size();
int k = 0;
while(2*k<min(m,n)){
for(int j=k;j<n-k;j++){
rec.push_back(matrix[k][j]);
}
for(int i=k+1;i<m-k;i++){
rec.push_back(matrix[i][n-k-1]);
}
if(m-k-1>k){
for(int j=n-k-2;j>=k;j--){
rec.push_back(matrix[m-k-1][j]);
}
}
if(k<n-k-1){
for(int i=m-k-2;i>k;i--){
rec.push_back(matrix[i][k]);
}
}
k++;
}
return rec;
}
};
