54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
把矩阵按螺旋形打印出来，很有意思的一道题，我隐隐约约记得本科找工作的时候有这么一道笔试题。中等难度，需要多次调试修改才能AC。
思路是标记矩阵的左上角和右下角两个坐标，分别为sx,sy和tx,ty。然后每次从左上角开始，绕一圈，则起点sx,sy都加1，终点tx,ty都减1。如此循环，直到终点跑到起点上面去了。
需要注意后两个for循环的条件，要依次同时满足上一个条件，因为有可能遇到行向量（第三个for）或者列向量（第四个for）。完整代码如下：
class Solution {
public:
vector<int> spiralOrder(vector<vector<int> >& matrix)
{
vector<int> vSpiralOrder;
if (matrix.size() == 0)
return vSpiralOrder;
int sx = 0, sy = 0, tx = matrix.size(), ty = matrix[0].size();
while (true) {
for (int j = sy; j < ty; j++)
vSpiralOrder.push_back(matrix[sx][j]);
for (int i = sx + 1; i < tx; i++)
vSpiralOrder.push_back(matrix[i][ty – 1]);
for (int j = ty – 2; sx + 1 < tx && j >= sy; j–) // 满足上一个条件sx+1<tx
vSpiralOrder.push_back(matrix[tx – 1][j]);
for (int i = tx – 2; ty – 2 >= sy && i > sx; i–) // 满足上一个条件ty-2>=sy
vSpiralOrder.push_back(matrix[i][sy]);
sx++;
sy++;
tx–;
ty–;
if (sx >= tx || sy >= ty)
break;
}
return vSpiralOrder;
}
};
本代码提交AC，用时0MS。
二刷。更安全的做法（https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution）：
class Solution {
public:
vector<int> spiralOrder(vector<vector<int> >& matrix)
{
vector<int> ans;
if (matrix.empty() || matrix[0].empty())
return ans;
int start_row = 0, start_col = 0, end_row = matrix.size() – 1, end_col = matrix[0].size() – 1;
while (start_row <= end_row && start_col <= end_col) {
for (int j = start_col; j <= end_col; ++j) {
ans.push_back(matrix[start_row][j]);
}
++start_row;
for (int i = start_row; i <= end_row; ++i) {
ans.push_back(matrix[i][end_col]);
}
–end_col;
if (start_row <= end_row) { // 防止行向量
for (int j = end_col; j >= start_col; –j) {
ans.push_back(matrix[end_row][j]);
}
}
–end_row;
if (start_col <= end_col) { // 防止列向量
for (int i = end_row; i >= start_row; –i) {
ans.push_back(matrix[i][start_col]);
}
}
++start_col;
}
return ans;
}
};
本代码提交AC，用时0MS。
三刷。直接模拟，设置left、right、up、down分别表示向左、右、上、下的结束位置，到达该位置需要换方向，同时更新对应的结束位置。完整代码如下：
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if (matrix.size() == 0)return {};
int m = matrix.size(), n = matrix[0].size();
if (m <= 1 || n <= 1) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans.push_back(matrix[i][j]);
}
}
return ans;
}
int left = 0, right = n - 1, up = 1, down = m - 1;
int dir = 0, i = 0, j = 0; // dir: 0: right; 1: down; 2: left; 3:up
int total_num = m * n, cur_num = 0;
while (cur_num < total_num) {
ans.push_back(matrix[i][j]);
++cur_num;
switch (dir) {
case 0:
if (j == right) {
++i;
dir = 1;
--right;
}
else {
++j;
}
break;
case 1:
if (i == down) {
--j;
dir = 2;
--down;
}
else {
++i;
}
break;
case 2:
if (j == left) {
--i;
dir = 3;
++left;
}
else {
--j;
}
break;
case 3:
if (i == up) {
++j;
dir = 0;
++up;
}
else {
--i;
}
break;
}
}
return ans;
}
};
本代码提交AC，用时0MS。
