[LeetCode] Spiral Matrix

这个题目的意思比较简单,就是螺旋式的输出数组的数据,[[

[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]You should return [1,2,3,6,9,8,7,4,5].我自己的解法比较直接,就是从最外层向内层逐步递归这种方式不需要额外的存储空间,但是边界控制比较繁琐,代码如下: public List<Integer> spiralOrder(int[][] matrix) {List<Integer> rs = new LinkedList<Integer>();int m, n;//row and columnif(matrix == null || matrix.length == 0)return rs;else {m = matrix.length;n = matrix[0].length;getSpiralData(matrix, 0, 0, m, n, rs);}return rs;}/*** 循环获取数据* @param matrix data matrix* @param startX 起始位置* @param startY* @param maxM max row* @param maxN max column* @param rs result list*/public void getSpiralData(int[][] matrix, int startX, int startY, int maxM, int maxN, List<Integer> rs){if(maxM <= 0 || maxN <= 0){return;} else {int x= startX, y = startY;if(maxM ==1){while (y < startY + maxN){rs.add(matrix[x][y]);y++;}return;}if(maxN ==1){while (x < startX + maxM){rs.add(matrix[x][y]);x++;}return;}while (y <= startY + maxN-1){rs.add(matrix[x][y]);y++;}x = x + 1;y = startY + maxN -1;while (x <= startX + maxM-1){rs.add(matrix[x][y]);x++;}y = y-1;x = startX + maxM -1;while (y >= startY){rs.add(matrix[x][y]);y–;}x = x-1;y = startY;while (x > startX){rs.add(matrix[x][y]);x–;}getSpiralData(matrix,startX+1, startY+1, maxM-2, maxN-2, rs);}}此外看到网上别的一种解法也蛮直观的,通过控制每一步的方向,然后用额外的数组保存是否访问过,代码如下:

class Solution {private:int step[4][2];vector<int> ret;bool canUse[100][100];public:void dfs(vector<vector<int> > &matrix, int direct, int x, int y){for(int i = 0; i < 4; i++){int j = (direct + i) % 4;int tx = x + step[j][0];int ty = y + step[j][1];if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty]){canUse[tx][ty] = false;ret.push_back(matrix[tx][ty]);dfs(matrix, j, tx, ty);}}}vector<int> spiralOrder(vector<vector<int> > &matrix) {// Start typing your C/C++ solution below// DO NOT write int main() functionstep[0][0] = 0;step[0][1] = 1;step[1][0] = 1;step[1][1] = 0;step[2][0] = 0;step[2][1] = -1;step[3][0] = -1;step[3][1] = 0;ret.clear();memset(canUse, true, sizeof(canUse));dfs(matrix, 0, 0, -1);return ret;}};

，贪婪是最真实的贫穷，满足是最真实的财富