SpiralMatrixII [source code]
public class SpiralMatrixII {
static
/******************************************************************************/
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
if (n == 0)
return matrix;
int[] dimensions = {n, n - 1};
int x = 0, y = -1;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dimens_idx = 0, val = 0, direction_idx = 0;
while (dimensions[dimens_idx] > 0) {
for (int i = 0; i < dimensions[dimens_idx]; i++) {
int[] direction = directions[direction_idx];
x += direction[0];
y += direction[1];
matrix[x][y] = ++val;
}
dimensions[dimens_idx]--;
dimens_idx = (dimens_idx + 1) % 2;
direction_idx = (direction_idx + 1) % 4;
}
return matrix;
}
}
/******************************************************************************/
public static void main(String[] args) {
SpiralMatrixII.Solution tester = new SpiralMatrixII.Solution();
int[][][] inputs = {
{{3}}, {
{ 1, 2, 3 },
{ 8, 9, 4 },
{ 7, 6, 5 }
},
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = inputs[2 * i][0][0];
String ans_str = Matrix.printMatrix (inputs[2 * i + 1]);
System.out.println (Printer.separator ());
String output_str = Matrix.printMatrix (tester.generateMatrix (n));
System.out.printf ("%d -> \n%s, expected: \n%s",
n, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
);
}
}
}
这次决定用swap row and col那个思路来做一下; 那个思路其实就是一个手动做法, 自己知道手动怎么话spiral, 而不依赖撞墙的时候的自动转向;
还算顺利的写出来了, 速度是2ms (51%); 注意一个dummy start的技巧就行了: 因为你第一行走完, 你在(0, 2)的位置, 你实际上是下一个iteration: (1,2)..(2.2)的dummy start, 所以最开始第一个iteration之前最好有一个dummy start; 然后dimension和direction的state都要设置到对应第一个iteration的状态, 这样进去就可以直接执行; 另外, val的初始值也要注意, 这里因为最后要求print的是1based的, 所以这里的val的dummy start应该是0而不是-1;
没有editorial;
@StefanPochmann said in 4-9 lines Python solutions:
Solution 1: Build it inside-out - 44 ms, 5 lines
Start with the empty matrix, add the numbers in reverse order until we added the number 1. Always rotate the matrix clockwise and add a top row:
|| => |9| => |8| |6 7| |4 5| |1 2 3| |9| => |9 8| => |9 6| => |8 9 4| |8 7| |7 6 5|The code:
def generateMatrix(self, n): A, lo = [], n*n+1 while lo > 1: lo, hi = lo - len(A), lo A = [range(lo, hi)] + zip(*A[::-1]) return AWhile this isn't O(n^2), it's actually quite fast, presumably due to me not doing much in Python but relying on
zipandrangeand+being fast. I got it accepted in 44 ms, matching the fastest time for recent Python submissions (according to the submission detail page).
Solution 2: Ugly inside-out - 48 ms, 4 lines
Same as solution 1, but without helper variables. Saves a line, but makes it ugly. Also, because I access A[0][0], I had to handle the n=0 case differently.
def generateMatrix(self, n): A = [[n*n]] while A[0][0] > 1: A = [range(A[0][0] - len(A), A[0][0])] + zip(*A[::-1]) return A * (n>0)
Solution 3: Walk the spiral - 52 ms, 9 lines
Initialize the matrix with zeros, then walk the spiral path and write the numbers 1 to n*n. Make a right turn when the cell ahead is already non-zero.
def generateMatrix(self, n): A = [[0] * n for _ in range(n)] i, j, di, dj = 0, 0, 0, 1 for k in xrange(n*n): A[i][j] = k + 1 if A[(i+di)%n][(j+dj)%n]: di, dj = dj, -di i += di j += dj return A
可以大概看看, 主要好像还是耍的Python的各种语法;
@qwl5004 said in My Super Simple Solution. Can be used for both Spiral Matrix I and II:
This is my solution for Spiral Matrix I, [https://oj.leetcode.com/discuss/12228/super-simple-and-easy-to-understand-solution][1]. If you can understand that, this one is a no brainer :)
Guess what? I just made several lines of change (with comment "//change") from that and I have the following AC code:
public class Solution {
public int[][] generateMatrix(int n) {
// Declaration
int[][] matrix = new int[n][n];
// Edge Case
if (n == 0) {
return matrix;
}
// Normal Case
int rowStart = 0;
int rowEnd = n-1;
int colStart = 0;
int colEnd = n-1;
int num = 1; //change
while (rowStart <= rowEnd && colStart <= colEnd) {
for (int i = colStart; i <= colEnd; i ++) {
matrix[rowStart][i] = num ++; //change
}
rowStart ++;
for (int i = rowStart; i <= rowEnd; i ++) {
matrix[i][colEnd] = num ++; //change
}
colEnd --;
for (int i = colEnd; i >= colStart; i --) {
if (rowStart <= rowEnd)
matrix[rowEnd][i] = num ++; //change
}
rowEnd --;
for (int i = rowEnd; i >= rowStart; i --) {
if (colStart <= colEnd)
matrix[i][colStart] = num ++; //change
}
colStart ++;
}
return matrix;
}
}
Obviously, you could merge colStart and colEnd into rowStart and rowEnd because it is a square matrix. But this is easily extensible to matrices that are m*n.
Hope this helps :)
[1]: https://oj.leetcode.com/discuss/12228/super-simple-and-easy-to-understand-solution
@lovesly said in My Super Simple Solution. Can be used for both Spiral Matrix I and II:
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int cur = 1;
int rowBegin = 0;
int rowEnd = n - 1;
int colBegin = 0;
int colEnd = n - 1;
while(cur <= n * n) {
int i = rowBegin;
int j = colBegin;
//left to right
for(j = colBegin ; j <= colEnd; j++){
res[rowBegin][j] = cur++;
}
rowBegin++;
//top to bot
for(i = rowBegin ; i <= rowEnd; i++){
res[i][colEnd] = cur++;
}
colEnd--;
//right to left
for(j = colEnd ; j >= colBegin; j--){
res[rowEnd][j] = cur++;
}
rowEnd--;
//bot to top
for(i = rowEnd; i >= rowBegin; i--){
res[i][colBegin] = cur++;
}
colBegin++;
}
return res;
}
Actually you don't need "if condition", because it's n*n matrix.
这个就是上一题见过一次的用result size来terminate的技巧;
discussion基本还是第一题见到过的解法, 所以其实这两题是差不多的; 我上面这个代码已经是submission最优;
Problem Description
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 ]
]
Difficulty:Medium
Total Accepted:95.8K
Total Submissions:235.3K
Contributor:LeetCode
Related Topics
array
Similar Questions
Spiral Matrix