首页 > 代码库 > LeetCode: Spiral Matrix 解题报告
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 line19 for (int i = 0; i < cols; i++) {20 ret.add(matrix[x][y + i]);21 }22 23 // right column24 for (int i = 1; i < rows - 1; i++) {25 ret.add(matrix[x + i][y + cols - 1]);26 }27 28 // down row29 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 }
Solution 2:
http://blog.csdn.net/fightforyourdream/article/details/16876107?reload
感谢以上文章作者提供的思路，我们可以用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 }
Solution 3:
http://fisherlei.blogspot.com/2013/01/leetcode-spiral-matrix.html
感谢水中的鱼大神。这是一种相当巧妙的思路，我们这次可以用Iterator来实现了，记录2个方向数组，分别表示在x方向，y方向的前进方向。1表示右或是下，-1表示左或是向上，0表示不动作。
// 1: means we are visiting the row by the right direction.
// -1: means we are visiting the row by the left direction.
int[] x = {1, 0, -1, 0};
// 1: means we are visiting the colum by the down direction.
// -1: means we are visiting the colum by the up direction.
int[] y = {0, 1, 0, -1};
这种方向矩阵将会很常用在各种旋转数组上。
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 axis43 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 }
GitHub CODE:
spiralOrder.java
LeetCode: Spiral Matrix 解题报告