LeetCode: Spiral Matrix II 解题报告-三种方法解决旋转矩阵问题

Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

SOLUTION 1:

还是与上一题Spiral Matrix类似的算法，我们使用x1,y1作为左上角的起点，x2,y2记录右下角，这样子旋转时会简单多了。

 1 public int[][] generateMatrix1(int n) {
 2         int[][] ret = new int[n][n];
 3 
 4         if (n == 0) {
 5             // return a [] not a NULL.
 6             return ret;
 7         }
 8         
 9         int number = 0;
10         int rows = n;
11         
12         int x1 = 0;
13         int y1 = 0;
14         
15         while (rows > 0) {
16             int x2 = x1 + rows - 1;
17             int y2 = y1 + rows - 1;
18             
19             // the Whole first row.
20             for (int i = y1; i <= y2; i++) {
21                 number++;
22                 ret[x1][i] = number;
23             }
24             
25             // the right column except the first and last line.
26             for (int i = x1 + 1; i < x2; i++) {
27                 number++;
28                 ret[i][y2] = number;
29             }
30             
31             // This line is very important.
32             if (rows <= 1) {
33                 break;
34             }
35             
36             // the WHOLE last row.
37             for (int i = y2; i >= y1; i--) {
38                 number++;
39                 ret[x2][i] = number;
40             }
41             
42             // the left column. column keep stable
43             // x: x2-1 --> x1 + 1
44             for (int i = x2 - 1; i > x1; i--) {
45                 number++;
46                 ret[i][y1] = number;
47             }
48             
49             // remember this.
50             rows -= 2;
51             x1++;
52             y1++;
53         }
54         
55         return ret;
56     }

View Code

还是与上一题Spiral Matrix类似的算法，使用Direction 数组来定义旋转方向。其实蛮复杂的，也不好记。但是记住了应该是标准的算法。

1 /* 2 Solution 2: use direction. 3 */ 4 public int[][] generateMatrix2(int n) { 5 int[][] ret = new int[n][n]; 6 if (n == 0) { 7 return ret; 8 } 9 10 int[] x = {1, 0, -1, 0}; 11 int[] y = {0, 1, 0, -1}; 12 13 int num = 0; 14 15 int step = 0; 16 int candElements = 0; 17 18 int visitedRows = 0; 19 int visitedCols = 0; 20 21 // 0: right, 1: down, 2: left, 3: up. 22 int direct = 0; 23 24 int startx = 0; 25 int starty = 0; 26 27 while (true) { 28 if (x[direct] == 0) { 29 // visit the Y axis 30 candElements = n - visitedRows; 31 } else { 32 // visit the X axis 33 candElements = n - visitedCols; 34 } 35 36 if (candElements <= 0) { 37 break; 38 } 39 40 // set the cell. 41 ret[startx][starty] = ++num; 42 step++; 43 44 // change the direction. 45 if (step == candElements) { 46 step = 0; 47 visitedRows += x[direct] == 0 ? 0: 1; 48 visitedCols += y[direct] == 0 ? 0: 1; 49 50 // change the direction. 51 direct = (direct + 1) % 4; 52 } 53 54 startx += y[direct]; 55 starty += x[direct]; 56 } 57 58 return ret; 59 }

1 /* 2 Solution 3: 使用四条bound来限制的方法. 3 */ 4 public int[][] generateMatrix(int n) { 5 int[][] ret = new int[n][n]; 6 if (n == 0) { 7 return ret; 8 } 9 10 int top = 0, bottom = n - 1, left = 0, right = n - 1; 11 int num = 1; 12 while (top <= bottom) { 13 if (top == bottom) { 14 ret[top][top] = num++; 15 break; 16 } 17 18 // first line. 19 for (int i = left; i < right; i++) { 20 ret[top][i] = num++; 21 } 22 23 // right line; 24 for (int i = top; i < bottom; i++) { 25 ret[i][right] = num++; 26 } 27 28 // bottom line; 29 for (int i = right; i > left; i--) { 30 ret[bottom][i] = num++; 31 } 32 33 // left line; 34 for (int i = bottom; i > top; i--) { 35 ret[i][left] = num++; 36 } 37 38 top++; 39 bottom--; 40 left++; 41 right--; 42 } 43 44 return ret; 45 }

LeetCode: Spiral Matrix II 解题报告-三种方法解决旋转矩阵问题

相关推荐