LeetCode: Spiral Matrix 解题报告

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].

Solution 1:

使用递归，一次扫描一整圈，然后用x,y记录这个圈的左上角，递归完了都+1。rows, cols记录还没扫的有多少。思想比较简单，但相当容易出错。起码提交了5次才最后过。

注意：1. 扫描第一行跟最后一行要扫到底部为止，而扫描左列和右列只需要扫中间的。

1 2 3 4

5 6 7 8

9 10 11 12

例如以上例子：你要先扫1234, 然后是8，然后是12 11 10 9 然后是 5.

不能这样：123, 4 8, 12 11 10 , 9 5。用后者的方法在只有一个数字 1的时候就完全不会扫到它。

 1 public List<Integer> spiralOrder1(int[][] matrix) {
 2         List<Integer> ret = new ArrayList<Integer>();
 3         if (matrix == null || matrix.length == 0 
 4             || matrix[0].length == 0) {
 5             return ret;   
 6         }
 7         
 8         rec(matrix, 0, 0, matrix.length, matrix[0].length, ret);
 9         
10         return ret;
11     }
12     
13     public static void rec(int[][] matrix, int x, int y, int rows, int cols, List<Integer> ret) {
14         if (rows <= 0 || cols <= 0) {
15             return;
16         }
17         
18         // first line
19         for (int i = 0; i < cols; i++) {
20             ret.add(matrix[x][y + i]);
21         }
22         
23         // right column
24         for (int i = 1; i < rows - 1; i++) {
25             ret.add(matrix[x + i][y + cols - 1]);
26         }
27         
28         // down row
29         if (rows > 1) {
30             for (int i = cols - 1; i >= 0; i--) {
31                 ret.add(matrix[x + rows - 1][y + i]);
32             }    
33         }
34         
35         // left column. GO UP.
36         if (cols > 1) {
37             for (int i = rows - 2; i > 0; i--) {
38                 ret.add(matrix[x + i][y]);
39             }    
40         }
41         
42         rec (matrix, x + 1, y + 1, rows - 2, cols - 2, ret);
43     }

View Code

感谢以上文章作者提供的思路，我们可以用x1,y1记录左上角，x2,y2记录右下角，这样子我们算各种边界值会方便好多。也不容易出错。

1 /* 2 Solution 2: 3 REF: http://blog.csdn.net/fightforyourdream/article/details/16876107?reload 4 此算法比较不容易算错 5 */ 6 public List<Integer> spiralOrder2(int[][] matrix) { 7 List<Integer> ret = new ArrayList<Integer>(); 8 if (matrix == null || matrix.length == 0 9 || matrix[0].length == 0) { 10 return ret; 11 } 12 13 int x1 = 0; 14 int y1 = 0; 15 16 int rows = matrix.length; 17 int cols = matrix[0].length; 18 19 while (rows >= 1 && cols >= 1) { 20 // Record the right down corner of the matrix. 21 int x2 = x1 + rows - 1; 22 int y2 = y1 + cols - 1; 23 24 // go through the WHOLE first line. 25 for (int i = y1; i <= y2; i++) { 26 ret.add(matrix[x1][i]); 27 } 28 29 // go through the right column. 30 for (int i = x1 + 1; i < x2; i++) { 31 ret.add(matrix[i][y2]); 32 } 33 34 // go through the WHOLE last row. 35 if (rows > 1) { 36 for (int i = y2; i >= y1; i--) { 37 ret.add(matrix[x2][i]); 38 } 39 } 40 41 // the left column. 42 if (cols > 1) { 43 for (int i = x2 - 1; i > x1; i--) { 44 ret.add(matrix[i][y1]); 45 } 46 } 47 48 // in one loop we deal with 2 rows and 2 cols. 49 rows -= 2; 50 cols -= 2; 51 x1++; 52 y1++; 53 } 54 55 return ret; 56 }

1 /* 2 Solution 3: 3 使用方向矩阵来求解 4 */ 5 6 public List<Integer> spiralOrder(int[][] matrix) { 7 List<Integer> ret = new ArrayList<Integer>(); 8 if (matrix == null || matrix.length == 0 9 || matrix[0].length == 0) { 10 return ret; 11 } 12 13 int rows = matrix.length; 14 int cols = matrix[0].length; 15 16 int visitedRows = 0; 17 int visitedCols = 0; 18 19 // indicate the direction of x 20 21 // 1: means we are visiting the row by the right direction. 22 // -1: means we are visiting the row by the left direction. 23 int[] x = {1, 0, -1, 0}; 24 25 // 1: means we are visiting the colum by the down direction. 26 // -1: means we are visiting the colum by the up direction. 27 int[] y = {0, 1, 0, -1}; 28 29 // 0: right, 1: down, 2: left, 3: up. 30 int direct = 0; 31 32 int startx = 0; 33 int starty = 0; 34 35 int candidateNum = 0; 36 int step = 0; 37 while (true) { 38 if (x[direct] == 0) { 39 // visit Y axis. 40 candidateNum = rows - visitedRows; 41 } else { 42 // visit X axis 43 candidateNum = cols - visitedCols; 44 } 45 46 if (candidateNum <= 0) { 47 break; 48 } 49 50 ret.add(matrix[startx][starty]); 51 step++; 52 53 if (step == candidateNum) { 54 step = 0; 55 visitedRows += x[direct] == 0 ? 0: 1; 56 visitedCols += y[direct] == 0 ? 0: 1; 57 58 // move forward the direction. 59 direct ++; 60 direct = direct%4; 61 } 62 63 // 根据方向来移动横坐标和纵坐标。 64 startx += y[direct]; 65 starty += x[direct]; 66 } 67 68 return ret; 69 }

1 public class Solution { 2 public List<Integer> spiralOrder(int[][] matrix) { 3 List<Integer> ret = new ArrayList<Integer>(); 4 if (matrix == null ||matrix.length == 0) { 5 // 注意在非法的时候，应该返回空解，而不是一个NULL值 6 return ret; 7 } 8 9 // Record how many rows and cols we still have. 10 int rows = matrix.length; 11 int cols = matrix[0].length; 12 13 // The four coners. 14 int top = 0; 15 int left = 0; 16 int bottom = rows - 1; 17 int right = cols - 1; 18 19 // every time we go through two rows and two cols. 20 for (; rows > 0 && cols > 0; rows -= 2, cols -= 2, top++, left++, bottom--, right--) { 21 // the first line. 22 for (int i = left; i <= right; i++) { 23 ret.add(matrix[top][i]); 24 } 25 26 // the right column. 27 for (int i = top + 1; i < bottom; i++) { 28 ret.add(matrix[i][right]); 29 } 30 31 // the down line; 32 if (rows > 1) { 33 for (int j = right; j >= left; j--) { 34 ret.add(matrix[bottom][j]); 35 } 36 } 37 38 // the left column. 39 if (cols > 1) { 40 for (int i = bottom - 1; i > top; i --) { 41 ret.add(matrix[i][left]); 42 } 43 } 44 } 45 46 return ret; 47 } 48 }

1 public List<Integer> spiralOrder3(int[][] matrix) { 2 List<Integer> ret = new ArrayList<Integer>(); 3 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 4 return ret; 5 } 6 7 int rows = matrix.length; 8 int cols = matrix[0].length; 9 10 int left = 0; 11 int right = cols - 1; 12 int top = 0; 13 int bottom = rows - 1; 14 15 while (left <= right && top <= bottom) { 16 // line top. 17 for (int i = left; i <= right; i++) { 18 ret.add(matrix[top][i]); 19 } 20 21 // line right; 22 for (int i = top + 1; i <= bottom - 1; i++) { 23 ret.add(matrix[i][right]); 24 } 25 26 // line bottom. 27 if (top != bottom) { 28 for (int i = right; i >= left; i--) { 29 ret.add(matrix[bottom][i]); 30 } 31 } 32 33 // line left; 34 if (left != right) { 35 for (int i = bottom - 1; i >= top + 1; i--) { 36 ret.add(matrix[i][left]); 37 } 38 } 39 40 left++; 41 right--; 42 top++; 43 bottom--; 44 } 45 46 return ret; 47 }

LeetCode: Spiral Matrix 解题报告

相关推荐