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。