首页 > 代码库 > LeetCode: Spiral Matrix II 解题报告-三种方法解决旋转矩阵问题
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 stable43 // x: x2-1 --> x1 + 144 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 }
SOLUTION 2:
还是与上一题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 axis30 candElements = n - visitedRows;31 } else {32 // visit the X axis33 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 }
SOLUTION 3:
无比巧妙的办法，某人的男朋友可真是牛逼啊！[leetcode] Spiral Matrix | 把一个2D matrix用螺旋方式打印
此方法的巧妙之处是使用TOP,BOOTOM, LEFT, RIGHT 四个边界条件来限制访问。其实和第一个算法类似，但是更加简洁易懂。10分钟内AC!
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 }
GitHub Code:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/array/GenerateMatrix1.java
LeetCode: Spiral Matrix II 解题报告-三种方法解决旋转矩阵问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。