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记录右下角，这样子旋转时会简单多了。
public int[][] generateMatrix1(int n) {
int[][] ret = new int[n][n];
if (n == ) {
// return a [] not a NULL.
return ret;
}
int number = ;
int rows = n;
int x1 = ;
int y1 = ;
while (rows > ) {
int x2 = x1 + rows - ;
int y2 = y1 + rows - ;
// the Whole first row.
for (int i = y1; i <= y2; i++) {
number++;
ret[x1][i] = number;
}
// the right column except the first and last line.
for (int i = x1 + ; i < x2; i++) {
number++;
ret[i][y2] = number;
}
// This line is very important.
if (rows <= ) {
break;
}
// the WHOLE last row.
for (int i = y2; i >= y1; i--) {
number++;
ret[x2][i] = number;
}
// the left column. column keep stable
// x: x2-1 --> x1 + 1
for (int i = x2 - ; i > x1; i--) {
number++;
ret[i][y1] = number;
}
// remember this.
rows -= ;
x1++;
y1++;
}
return ret;
}
SOLUTION 2:
还是与上一题Spiral Matrix类似的算法，使用Direction 数组来定义旋转方向。其实蛮复杂的，也不好记。但是记住了应该是标准的算法。
/*
Solution 2: use direction.
*/
public int[][] generateMatrix2(int n) {
int[][] ret = new int[n][n];
if (n == ) {
return ret;
} int[] x = {, , -, };
int[] y = {, , , -}; int num = ; int step = ;
int candElements = ; int visitedRows = ;
int visitedCols = ; // 0: right, 1: down, 2: left, 3: up.
int direct = ; int startx = ;
int starty = ; while (true) {
if (x[direct] == ) {
// visit the Y axis
candElements = n - visitedRows;
} else {
// visit the X axis
candElements = n - visitedCols;
} if (candElements <= ) {
break;
} // set the cell.
ret[startx][starty] = ++num;
step++; // change the direction.
if (step == candElements) {
step = ;
visitedRows += x[direct] == ? : ;
visitedCols += y[direct] == ? : ; // change the direction.
direct = (direct + ) % ;
} startx += y[direct];
starty += x[direct];
} return ret;
}
SOLUTION 3:
无比巧妙的办法，某人的男朋友可真是牛逼啊！[leetcode] Spiral Matrix | 把一个2D matrix用螺旋方式打印
此方法的巧妙之处是使用TOP,BOOTOM, LEFT, RIGHT 四个边界条件来限制访问。其实和第一个算法类似，但是更加简洁易懂。10分钟内AC!
/*
Solution 3: 使用四条bound来限制的方法.
*/
public int[][] generateMatrix(int n) {
int[][] ret = new int[n][n];
if (n == ) {
return ret;
} int top = , bottom = n - , left = , right = n - ;
int num = ;
while (top <= bottom) {
if (top == bottom) {
ret[top][top] = num++;
break;
} // first line.
for (int i = left; i < right; i++) {
ret[top][i] = num++;
} // right line;
for (int i = top; i < bottom; i++) {
ret[i][right] = num++;
} // bottom line;
for (int i = right; i > left; i--) {
ret[bottom][i] = num++;
} // left line;
for (int i = bottom; i > top; i--) {
ret[i][left] = num++;
} top++;
bottom--;
left++;
right--;
} return ret;
}
GitHub Code:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/array/GenerateMatrix1.java