博文中会简要介绍Leetcode P0054题目分析及解题思路。
“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]
这道题使用访问数组来标记已经访问过的元素，再用方向数组来表示当前前进的方向，一旦碰到已经访问过的元素或者方阵边界，即改变方向，也就是将方向数组里的方向指针前移，如此循环即可。
以下是Java的题解代码实现。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> spiralSequence = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return spiralSequence;
int height = matrix.length, width = matrix[0].length;
boolean[][] visited = new boolean[height][width];
int row = 0, col = 0, count = height*width, d = 0;
while (count > 0) {
spiralSequence.add(matrix[row][col]);
visited[row][col] = true;
--count;
boolean turn = this.isRequiredToTurn(row+di[d][0], col+di[d][1], height, width, visited);
d = (turn)? (d+1)%4: d;
row += di[d][0];
col += di[d][1];
}
return spiralSequence;
}
// Directions Mapping
// private int[][] di= new int[][]
// {0,1}, {1,0}, {0,-1}, {-1,0};
private boolean isRequiredToTurn(int nextRow, int nextCol, int height, int width, boolean[][] visited) {
if (nextRow < 0 || nextRow >= height
|| nextCol < 0 || nextCol >= width)
return true;
if (visited[nextRow][nextCol])
return true;
return false;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> spiral_seq;
if (matrix.size() == 0 || matrix[0].size() == 0)
return spiral_seq;
int row = matrix.size(), col = matrix[0].size();
int count = row*col, d = 0, r = 0, c = 0;
vector<vector<bool>> visited(row, vector<bool>(col, false));
while (count > 0) {
spiral_seq.push_back(matrix[r][c]);
--count;
visited[r][c] = true;
if (this->NeedToTurn(r+dr[d], c+dc[d], row, col, visited)) {
d = (d+1)%4;
}
r += dr[d];
c += dc[d];
}
return spiral_seq;
}
private:
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
bool NeedToTurn(int r, int c, int row, int col, const vector<vector<bool>> &visited) {
if (r >= 0 && r < row
&& c >= 0 && c < col
&& !visited[r][c]) {
return false;
}
return true;
}
};